Can You Race Across the Chess Board?

A very tiny Alice races across a $2 \times 2$ chessboard whose small squares have side $1$ cm. She starts at the bottom-left corner of the bottom-left square, which is black, and must reach the top-right corner of the top-right square, also black. She moves at $1$ cm per minute on white squares but only $0.9$ cm per minute on black ones. What is the least time in which she can reach the finish?

The Fiddler, Zach Wissner-Gross, January 26, 2024(original post)

The official solution appeared in the post of February 2, 2024 and gives $\sqrt{238}/9 + \sqrt2 \approx 3.128$ minutes for the main puzzle, agreeing with the answer below. The Extra Credit half of that post is paywalled, so the $8 \times 8$ time of about $11.788$ minutes is my own and has not been checked against it.

Solution

Put the start at $(0, 0)$ and the finish at $(2, 2)$. The black squares are $[0,1]^2$ and $[1,2]^2$, and they touch only at the centre point $(1, 1)$.

Two simple routes set the scene. Straight along the diagonal, Alice stays on black the whole way: $2\sqrt2/0.9 \approx 3.143$ minutes. Going one centimetre up to the white square, across its diagonal and one centimetre along the far black square costs $2/0.9 + \sqrt2 \approx 3.636$ minutes, much worse. The best route is a compromise: cut a little way into the white square, where travel is cheaper, without making the black legs much longer.

Inside any one square the speed is constant, so the fastest way between two points of the same square is a straight line. A fastest route is therefore a chain of straight pieces that bends only where it crosses from one square to another. Suppose it uses the top-left white square $[0,1] \times [1,2]$ (the bottom-right one is its mirror image). It enters across the white square’s bottom edge at $(1 - a, 1)$ and leaves across its right edge at $(1, 1 + b)$, with $a, b$ between $0$ and $1$. Its time is $$T(a, b) = \frac{\sqrt{1 + (1 - a)^2}}{0.9} + \sqrt{a^2 + b^2} + \frac{\sqrt{1 + (1 - b)^2}}{0.9} .$$ Taking $a = b = 0$ gives the straight diagonal, so this family includes it.

Each term is the length of a vector that depends on $a$ and $b$ in a straight-line way, so each term, and hence $T$, curves upward like a bowl (it is convex). The formula is unchanged when $a$ and $b$ are swapped. So if $(a, b)$ were best, so would be $(b, a)$, and by convexity their midpoint would be at least as good. We may therefore take $a = b$: $$T(a) = \frac{2\sqrt{1 + (1 - a)^2}}{0.9} + a\sqrt2 .$$ Write $u = 1 - a$. Setting the rate of change to zero, $$\frac{2u}{0.9\sqrt{1 + u^2}} = \sqrt2 \quad\Longleftrightarrow\quad \frac{u^2}{1 + u^2} = \frac{0.81}{2} \quad\Longleftrightarrow\quad u^2 = \frac{81}{119}.$$ So $u = 9/\sqrt{119}$ and $a = 1 - 9/\sqrt{119} \approx 0.175$. Then $\sqrt{1 + u^2} = \sqrt{200/119} = 10\sqrt2/\sqrt{119}$, and $$T = \frac{200\sqrt2}{9\sqrt{119}} + \sqrt2 - \frac{9\sqrt2}{\sqrt{119}} = \sqrt2 + \frac{119\sqrt2}{9\sqrt{119}} = \sqrt2 + \frac{\sqrt{238}}{9}.$$ $$\boxed{\ T_{\min} \;=\; \sqrt2 + \frac{\sqrt{238}}{9} \;\approx\; 3.128 \text{ minutes}. \ }$$ That beats the straight diagonal by about half a percent. The condition on $u$ is Snell’s law of refraction in disguise: the black leg meets the white square at an angle whose sine is $0.9$ times the sine of the $45^\circ$ angle inside it, exactly as light bends between two media.

The computation

The program does not assume the shape of the route. It marks points spaced $1/n$ cm apart along every edge of every square, joins every pair of marked points on the boundary of the same square by a straight segment timed at that square’s speed (or the faster neighbour’s, for a segment running along an edge), and finds the quickest chain of segments from corner to corner with Dijkstra’s algorithm. Any such chain is a real route, so its time is never below the true minimum, and it closes in as the spacing shrinks.

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

def fastest(N, n):
    def speed(i, j):
        if 0 <= i < N and 0 <= j < N:
            return 0.9 if (i + j) % 2 == 0 else 1.0
        return 0.0                       # off the board
    ids, rows, cols, cost = {}, [], [], []
    node = lambda p: ids.setdefault(p, len(ids))
    for i, j in np.ndindex(N, N):
        x, y = i * n, j * n              # in units of 1/n cm
        side = range(n + 1)
        pts = sorted({(x + k, y + e) for k in side
                      for e in (0, n)} |
                     {(x + e, y + k) for k in side
                      for e in (0, n)})
        P = np.array(pts)
        I, J = np.triu_indices(len(pts), 1)   # every pair
        p, q = P[I], P[J]
        v = np.full(len(I), speed(i, j))
        # a segment along an edge may use the faster side
        edges = ((0, x, i - 1, j), (0, x + n, i + 1, j),
                 (1, y, i, j - 1), (1, y + n, i, j + 1))
        for ax, line, a, b in edges:
            on = (p[:, ax] == line) & (q[:, ax] == line)
            v[on] = max(speed(i, j), speed(a, b))
        u = np.array([node(t) for t in pts])
        rows.append(u[I])
        cols.append(u[J])
        cost.append(np.hypot(*(p - q).T) / n / v)
    rows, cols, cost = map(np.concatenate,
                           (rows, cols, cost))
    m = len(ids)
    G = coo_matrix((cost, (rows, cols)), shape=(m, m))
    t = dijkstra(G.tocsr(), directed=False,
                 indices=node((0, 0)))
    return t[node((N * n, N * n))]

print(f"2x2 board: {fastest(2, 40):.3f} minutes")

It prints

2x2 board: 3.128 minutes

Extra Credit

Alice now crosses a full $8 \times 8$ chessboard, again from the bottom-left corner of the bottom-left black square to the top-right corner of the top-right black square, at the same speeds. What is the least time?

Solution

The straight diagonal is all black: $8\sqrt2/0.9 \approx 12.571$ minutes. But the $8 \times 8$ board offers something the small board did not: a white highway. The white squares just above the main diagonal, from $[0,1] \times [1,2]$ up to $[6,7] \times [7,8]$, touch corner to corner along the line $y = x + 1$, and that line runs along the diagonal of each of them. Alice can travel that line at full speed, slipping through the corner points $(1, 2), (2, 3), \dots, (6, 7)$ from one white square to the next. (The squares just below the diagonal form a mirror image highway.)

The first idea is to get onto the highway as in the main puzzle and ride it to the end: from the start, cross the black square into the first white square, head for the corner $(1, 2)$, follow the highway to $(6, 7)$ and leave symmetrically. If the black leg crosses $y = 1$ at $(t, 1)$, half the trip costs $$\frac{\sqrt{1 + t^2}}{0.9} + \sqrt{(1 - t)^2 + 1} ,$$ minimised at $t \approx 0.467$, and the whole route takes about $11.790$ minutes including the $5\sqrt2$ of highway between $(1,2)$ and $(6,7)$.

The computation below finds something slightly better. At the corner $(1, 2)$ the route bends from its approach direction onto the $45^\circ$ highway, and a bend is wasteful. Rounding it off means clipping the corner of the black square $[1,2]^2$: a short stretch at the slow speed buys a straighter line. The best route crosses $y = 1$ at $t \approx 0.4857$, enters the black square on $x = 1$ at height $1.9262$, leaves it on $y = 2$ at $x \approx 1.0579$, joins the highway at the next corner $(2, 3)$, and mirrors all this at the far end. At each of these crossings the route bends exactly as Snell’s law requires. The three crossing positions satisfy three equations of this kind with no neat closed form, so the value is numerical: $$\boxed{\ T_{\min} \;\approx\; 11.788 \text{ minutes}. \ }$$ That is about $6$ percent faster than the straight diagonal.

The computation

The search from The computation above covers the whole $8 \times 8$ board and every possible route through it. With crossing points every $1/120$ cm it finds the route described above.

print(f"8x8 board: {fastest(8, 120):.3f} minutes")

It prints

8x8 board: 11.788 minutes