# The Trapped Knight

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:

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


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))))

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()

Current rating: 5

#### Nathan Eaves 3 years, 2 months ago

I made an implementation which does not need a generated board. By dividing the number spiral into sections where the section index is derived by s(n)=floor(sqrt(n-1)) we. By implementing these sections into an imaginary board I can derive the coordinates from n and vice versa.

For example, if n is the number in the spiral and we want the coordinates of n on the board we do:
def getCoord(n):
s=floor(sqrt(n-1))
m=s%2
p=m*2-1
sx=p*(s-m)//2+m
sy=p*(s-m)//2
x=sx-p*max(min(s,n-s**2-s-1),0)
y=sy-p*min(s,n-s**2-1)
return x,y

Suffice it to say, without a board to generate and an array to manage, the memory constraints as well as efficiency are improved significantly. This allows for further generation of the sequence (traps are ignored).

TL;DR, just a fun improvement on your program I worked on by using a number spiral pattern. No numpy needed.

Current rating: 5

#### christian 3 years, 2 months ago

Interesting – thanks for sharing!

Current rating: 5

#### Cole 2 years, 11 months ago

What about multiple chess board with a high amount of players. It get so large that there's a macro pattern of strategies. I was figuring intersecting grid through a platonic solid to see 3D behavior the same say. See if your curious to try it out. I can visualize it and would be amusing to through it into the quantum algorithm. Combine it with the spiral to see what happens.

Currently unrated

#### Cole 2 years, 11 months ago

May you also do the same with a Go Board. I love this kind of discoveries.