The Trapped Knight

Posted on 26 March 2020

The Trapped Knight problem is a chess-based problem apparently invented by Neil Sloane and giving rise to a finite number sequence in his Online Encyclopedia of Integer Sequences (OEIS A316667).

The squares of an infinite chess board are numbered in a spiral, as in this diagram:

An infinite chessboard, numbered in a spiral

A knight, starts at square 1 and moves according to the normal rules of chess, except that where there is more than one possible move, it chooses the square with the smallest number that it has not previously visited. So the first move is to square 10, the second to square 3, and so on. See this Numberphile video for more information.

The interesting thing about the sequence is that it terminates, at step 2016 on square 2084, where it has no further legal moves to make. The Python code below generates the trapped knight sequence and plots the knight's position:

1, 10, 3, 6, 9, 4, 7, 2, 5, ..., 2880, 2467, 2084

enter image description here

The green and red markers indicate the knight's initial and final positions respectively.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection
from matplotlib.colors import ListedColormap

DPI = 72
width, height = 700, 525
fig, ax = plt.subplots(figsize=(width/DPI, height/DPI), dpi=DPI)
ax.axis('square')

# Set up the grid: a board of 100 x 100 squares is enough.
n = 100
grid = [[0]*n for i in range(n)]
ix, iy = 0, 0
dx, dy = 1, 0
s = 1
i = 0
while i <= n*n:
    for j in range(s):
        i += 1
        try:
            grid[iy+n//2][ix+n//2] = i
        except IndexError:
            break
        ix += dx
        iy += dy
    dx, dy = dy, dx
    if dy:
        dy = -dy
    else:
        s += 1

def get_next(iy, ix):
    """Get the position of the next square visited by the knight."""

    next_sq = []
    moves = (-1,-2), (-1,2), (1,-2), (1,2), (-2,-1), (-2,1), (2,-1), (2,1)
    for dy, dx in moves:
        jy, jx = iy + dy, ix + dx
        if 0 <= jx < n and 0 <= jy < n:
            if (jy, jx) not in visited:
                next_sq.append((jy, jx))
    if not next_sq:
        # No valid moves – we're done: return None
        return
    return min(next_sq, key=lambda e: grid[e[0]][e[1]])

# Keep track of the visited squares' indexes in the list visited.
visited = []
iy, ix = n//2, n//2
i = 0
# Run the game until there are no valid moves and print the visited squares.
while True:
    i += 1
    visited.append((iy, ix))
    try:
        iy, ix = get_next(iy, ix)
    except TypeError:
        break
print(', '.join(str(grid[iy][ix]) for iy, ix in visited))
print('Done in {} steps'.format(i))

# Plot the path of the knight on a chessboard in a pleasing colour scheme.
points = np.array(visited).reshape(-1, 1, 2)
segments = np.concatenate([points[:-1], points[1:]], axis=1)
norm = plt.Normalize(1, len(visited))
lc = LineCollection(segments, cmap='plasma_r', norm=norm)
lc.set_array(np.array(range(len(visited))))
line = ax.add_collection(lc)

ax.scatter([visited[0][0], visited[-1][0]], [visited[0][1], visited[-1][1]],
           c=('g','r'), marker='x', zorder=10)

ptp = np.concatenate( (np.min(points[:,:], axis=0),
                       np.max(points[:,:], axis=0)) ).T

ax.set_xlim(ptp[0][0]-0.5, ptp[0][1]+0.5)
ax.set_ylim(ptp[1][0]-0.5, ptp[1][1]+0.5)

xmin, xmax = ptp[0]
ymin, ymax = ptp[1]
board = np.zeros((ymax-ymin+1, xmax-xmin+1), dtype=int)
board[1::2, ::2] = 1
board[::2, 1::2] = 1

cmap = ListedColormap(['#aaaaaa', 'white'])

ax.imshow(board, extent=[xmin-0.5,xmax+0.5,ymin-0.5,ymax+0.5], cmap=cmap)

plt.savefig('trapped-knight.png', dpi=DPI)
plt.show()