Gridspeed

Acity is laid out as a six-by-six grid of intersections, ten miles apart, and its streets have wildly different speed limits. The north-south streets, the columns, run faster as one moves east; the east-west streets, the rows, run faster as one moves south. Concretely, crossing one block down column $c$ takes $60/c$ minutes and crossing one block along row $r$ takes $60/r$ minutes, so the slow streets, the first row and first column, cost a full hour a block while the fast ones cost ten minutes. Dennis Shasha’s question: starting at the top-left intersection and ending at the bottom-left, what is the quickest route that visits every intersection exactly once?

An open tour, and a closed one

This is a travelling-salesman problem with two twists. The route is a path, not a loop, pinned at both ends, and the cost of a step depends not on its length, always ten miles, but on which street it uses. Number the intersections $1$ to $36$ across the rows, so the start is node $1$ and the finish node $31$, and the task is the shortest Hamiltonian path between them.

The model leans on one constraint that does the hard part by itself. A circuit constraint asserts that a chosen set of arcs forms a single tour through all the nodes, with no detours and, crucially, no separate little loops; the subtours that plague a naive formulation are ruled out inside the constraint rather than by a cloud of inequalities bolted on outside. An open path from node $1$ to node $31$ is then just a circuit with one free, cost-free arc joining the finish back to the start: forced into the tour, that arc turns the loop into a path between its ends.

from ortools.sat.python import cp_model

R = C = 6
def node(r, c): return r * C + c

# directed grid arcs; a block down column c costs 60/c, along row r costs 60/r
ARCS = []
for r in range(R):
    for c in range(C):
        u = node(r, c)
        if c + 1 < C:
            h = 60 // (r + 1)
            ARCS += [(u, u + 1, h), (u + 1, u, h)]
        if r + 1 < R:
            v = 60 // (c + 1)
            ARCS += [(u, u + C, v), (u + C, u, v)]

def fastest_tour(closed):
    m = cp_model.CpModel()
    lit = {}
    circuit = []
    for u, v, t in ARCS:
        b = m.NewBoolVar("")
        lit[u, v] = (b, t)
        circuit.append((u, v, b))
    if not closed:                       # free closure from node 31 to node 1
        b = m.NewBoolVar("")
        m.Add(b == 1)
        circuit.append((node(5, 0), node(0, 0), b))
    m.AddCircuit(circuit)
    m.Minimize(sum(t * b for b, t in lit.values()))
    s = cp_model.CpSolver()
    s.Solve(m)
    return int(s.ObjectiveValue())

The open tour comes back at $726$ minutes, the route of Figure 42.1: it dives down the slow left column only when it must and spends its length on the fast lower rows and right columns. Drop the free closure arc and ask instead for a true loop, a tour that returns to its start, and the answer is $834$ minutes, Figure 42.2.

The closed tour is worth a word. When Shasha’s puzzle was first put to a general-purpose integer-programming solver with the subtours forbidden in the usual way, by position variables and a thicket of order inequalities, the open tour solved but the closed tour ran for two hours and gave nothing, the weak relaxation leaving the solver adrift. The circuit constraint above is the difference. It is the travelling-salesman structure expressed directly to the solver rather than approximated by inequalities, and with it the loop that once defeated the machine is found in a moment. The lesson is not that hardware improved but that the right constraint carries the reasoning the wrong one only gestures at.

Sources. The Gridspeed puzzle is from Dennis E. Shasha, Puzzling Adventures (W. W. Norton, New York and London, $2005$), pages $68$–$70$. The integer-programming treatment, the open and closed tours and their times of $726$ and $834$ minutes, and the observation that a general-purpose solver with position-variable subtour elimination solves the open tour but stalls for hours on the closed one, are from Martin J. Chlond, Puzzle—Shasha’s Gridspeed Puzzle, INFORMS Transactions on Education volume $9$, number $1$ ($2008$), pages $46$–$52$. The model here instead uses a circuit constraint, which encodes the single-tour requirement directly; the two tours drawn are produced by it and re-checked, step by step, to be Hamiltonian routes on the grid totalling the stated times.