I've already written about a trapped knight in a post from May 23rd 2020 titled Knight Tours in which the Knight gets trapped on an infinite chess board if it follows these rules:
Suppose we devise a Knight Tour such that the Knight starts on square 0 and then moves always to the unvisited square closest to the origin. "Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral is chosen.
On the first move, the Knight could move to squares 9, 11, 13, 15, 17, 19, 21 or 23. All these squares are the same distance from the 0 square but 9 is chosen because it comes first in the spiral. From 9, subsequent squares are 2, 5, 8, 3, 6, 1, 4, 7, 10, 13 and so on.
Figure 1 depicts the situation:
 |
Figure 1 |
The initial terms are of the sequence are:
0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81, ...
What's really interesting about this tour is that the knight gets trapped at the 22325th move, where it can't reach any unvisited square. The square on which the Knight is stuck is 25983.
Of course, if the numbering began from one instead of zero, then the square on which the knight becomes stuck would be 25984.
 |
Figure 2: screenshot from Numberphile video |
As can be seen, the numbering starts from one, not zero. The rule for the knight's movements is that it must move to the lowest available square and not the square that is closest to the origin. The numbers of the squares that the knight moves to are listed in OEIS A316667:
| A316667 | Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square. |
The initial terms are:
1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36
As the OEIS comments state:
This sequence is finite: At step 2016, square 2084 is visited, after which there are no unvisited squares within one knight move.
The number of steps required to become trapped, 2016, is far less than the number required in the PART 1 example where 22325 steps were required. Figure 3 shows the path of the knight as it starts at 1 and ends up at 2084. The path was generated by Python code that I found on this site. I pasted the code into SageMathCell and it worked just fine. Here is the permalink. This graphic always appears in the Numberphile video.
 |
| Figure 3 |
If 2084 is the end of the knight's tour and 26943 is never visited, then how can this number be involved? The answer is that we can continue the tour if we repeatedly block the squares where the knight would not have any available moves. Thus when we get to 2467, the square before 2084, we block the latter and move instead to the next lowest number and the tour continues. See Figure 4:
 |
Figure 4: screenshot from Numberphile video |
Eventually the knight gets trapped again once it moves to square 2720. Again we block that square and allow the knight to move to the next lowest square. These blocked squares constitute OEIS A323714:
| A323714 | Squares where knight moving to a lowest unvisited square on a spirally numbered board will have no available moves. |
, 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()){kind=link}
No comments:
Post a Comment