Can You Solve The Chess Mystery?

The Riddler for April 17, 2020. The Express is a chess retrograde-analysis puzzle, which hinges on the colour a knight lands on after an even number of moves; it depends on the board diagram and we defer it with the key insight recorded. The Classic plays Conway’s Game of Life on a narrow toroidal grid and asks how wide it must be to hold an oscillator.

Riddler Express

In a legal game of chess, the white knight that captured the black queen has moved exactly eight times. The naive reading of the position makes this look impossible. Construct a legal game history showing how it happened.

The Riddler, FiveThirtyEight, April 17, 2020(original post)

Deferred (board-diagram retrograde analysis)

The heart of the puzzle is a clean parity fact: a knight changes the colour of its square on every move, so after an even number of moves, eight here, it returns to the colour it started on. The black queen sat on a dark square; the white knight that looks like the culprit, the one from the corner that starts on a light square, could only ever reach a dark square in an odd number of moves. So that knight cannot have made the capture in eight. By elimination the capture was made by the other white knight, the one whose home square is dark, and the knight now sitting where the queen died is the corner knight, which arrived in an odd number of moves.

We defer the full write-up because the remaining task, constructing an explicit legal move-by-move game reaching the shown position, depends on the exact board diagram (which pieces stand where), and the answer is itself a board-and-move-list construction rather than a number or formula. The load-bearing idea, the knight-colour parity that resolves the “impossibility,” is recorded above.

Riddler Classic

Play Conway’s Game of Life on a grid of three rows and $N$ columns with periodic (toroidal) boundaries, so the first and last rows are neighbours and the first and last columns are neighbours. What is the smallest $N$ that can support an oscillator (a pattern that returns to itself after two or more ticks)?

The Riddler, FiveThirtyEight, April 17, 2020(original post)

Solution

The simplest oscillator, the blinker (three cells in a row, flipping between horizontal and vertical), cannot live here: with only three rows wrapped into a cycle, a vertical line of three cells fills an entire column, and on a torus the top and bottom of that column are neighbours, so the cells see too many neighbours and the pattern collapses. Something larger is needed.

Searching every starting pattern for each width, no oscillator of any period exists for $N = 1, 2$ or $3$; the first width that supports one is $$\boxed{N = 4},$$ with a period-$2$ oscillator: two adjacent columns are fully alive on one tick, the other two columns are alive on the next, and then the original two return. (Treating each column of three cells as a single on/off unit, the dynamics collapse to a one-dimensional cellular automaton, which is why a clean period-$2$ pattern appears exactly at four columns.)

The computation

Encode Life on the $3\times N$ torus, build the map from every state to its successor, and ask whether any state lies on a cycle of length $\ge 2$. Peeling away states with no predecessor (in-degree zero) leaves exactly the states on cycles; an oscillator exists when one of those is not a fixed point.

from collections import Counter, deque
def step(state, N):
    c = Counter()
    for (r, col) in state:
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr or dc: c[((r + dr) % 3, (col + dc) % N)] += 1
    return frozenset(cell for cell, k in c.items()
                     if k == 3 or (k == 2 and cell in state))
def has_oscillator(N):
    cells = [(r, c) for r in range(3) for c in range(N)]; m = len(cells)
    states = [frozenset(cells[i] for i in range(m) if bits >> i & 1)
              for bits in range(1 << m)]
    succ = {s: step(s, N) for s in states}
    indeg = Counter(succ.values())
    q = deque(s for s in states if indeg[s] == 0); gone = set()
    while q:
        s = q.popleft(); gone.add(s); t = succ[s]; indeg[t] -= 1
        if indeg[t] == 0: q.append(t)
    return any(succ[s] != s for s in states if s not in gone)   # cycle, not fixed
for N in range(1, 5):
    print(N, has_oscillator(N))                # 1 F, 2 F, 3 F, 4 T

The first width supporting an oscillator is $N = 4$, as boxed.