9.17

To obtain every knight’s tour on an [math]n\times n[/math] board you only need a systematic depth-first search that 1) tries all eight legal knight steps from the current square and 2) backtracks as soon as it reaches a square that has already been visited. Below is a minimal, but complete, outline. State representation • Board: 2-D array vis[n][n] holding visit order (0 = not yet visited). • Possible moves: steps = {(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)}. • Path: dynamic array tour that stores square indices in the order they are entered. Recursive DFS (yields every Hamiltonian path of the knight graph)

def dfs(x, y, depth): if depth == n*n: # all squares used → output 1 tour yield tour.copy() # or count += 1 return # Warnsdorff ordering (optional, speeds up large n) nxt = sorted(legal_moves(x, y), key=lambda p: degree(p)) for nx, ny in nxt: vis[ny][nx] = depth tour.append((nx, ny)) yield from dfs(nx, ny, depth + 1) tour.pop() vis[ny][nx] = 0

Helper functions legal_moves(x,y) = {(x+dx, y+dy) ∈ [0,n)² | vis[y+dy][x+dx]==0} degree(p) = number of still-free squares reachable from p (Warnsdorff). Initial call For every starting square (sx,sy): set vis[sy][sx]=1, tour=[(sx,sy)], then execute dfs(sx,sy,1); afterwards reset vis. Complexity The implicit graph has [math]n^{2}[/math] vertices; the search explores each Hamiltonian path exactly once, so the worst-case running time is the number of knight’s tours, exponential in [math]n^{2}[/math]. The Warnsdorff heuristic plus symmetry pruning (start only in one fundamental region and rotate/reflect the resulting tours) is enough to generate all solutions up to the classical 8×8 board in reasonable time. Result Running the procedure above produces every sequence of moves in lexicographic order (under the chosen move ordering) where the knight visits each of the [math]n^{2}[/math] squares exactly once; these sequences are the complete set of knight’s tours on the [math]n\times n[/math] chessboard.

Back to Chapter 9