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

## Comments

Comments are pre-moderated. Please be patient and your comment will appear soon.

There are currently no comments

## New Comment