Knight's Tour

Introduction

The Knight's Tour is a classical problem in combinatorics and graph theory. The challenge is to find a sequence of moves for a chess knight such that the knight visits every square on the board exactly once. This problem dates back to the 9th century and has attracted the attention of mathematicians including Euler, who published an analysis of the problem in 1759.

On a standard 8x8 chessboard, the knight must make exactly 63 moves to complete the tour, visiting all 64 squares. The problem can be generalized to an n x n board or even to non-square rectangular boards. A tour is called a closed tour (or re-entrant tour) if the knight can return to its starting square with one additional move; otherwise, it is called an open tour.

The Knight's Tour is a specific instance of the more general Hamiltonian path problem on a graph, where each square is a vertex and each legal knight move is an edge. Since the Hamiltonian path problem is NP-hard in general, no efficient algorithm is known for arbitrary graphs. However, the structured nature of the chessboard graph allows heuristic methods such as Warnsdorff's rule to find solutions very efficiently in practice.

Problem Definition

Given an n x n chessboard and a knight placed on an arbitrary starting square, the task is to find a sequence of moves such that the knight visits every square exactly once. A chess knight moves in an "L" shape: two squares in one direction and one square in a perpendicular direction, giving up to eight possible moves from any position.

Knight's Possible Moves

From any position (r, c), the knight can move to the following eight positions:

A move is valid only if the destination square lies within the board boundaries and has not been visited yet.

"The Knight's Tour is a special case of the Hamiltonian path problem. While finding Hamiltonian paths is NP-hard on general graphs, the regularity of the chessboard graph makes the Knight's Tour tractable using heuristic methods." -- Schwenk (1991)

Backtracking Approach

The most straightforward method for solving the Knight's Tour is backtracking. The algorithm places the knight on a starting square, then recursively attempts to extend the partial tour. If a dead end is reached (no unvisited neighbor), it backtracks by undoing the last move and trying the next available neighbor.

Pseudocode

procedure KnightTour(board, row, col, moveCount): board[row][col] = moveCount if moveCount == n * n: return true // all squares visited for each (nextRow, nextCol) in possibleMoves(row, col): if isValid(nextRow, nextCol) and board[nextRow][nextCol] == 0: if KnightTour(board, nextRow, nextCol, moveCount + 1): return true board[row][col] = 0 // backtrack return false

Key Observations

• The board is initialized with zeros; a non-zero entry records the move number at which that square was visited.
• The algorithm explores all eight possible moves from the current position in a fixed order.
• When all moves from a position lead to dead ends, the algorithm resets the square and returns to try the next option at the previous level.
• Without heuristic ordering, the plain backtracking approach can be extremely slow, especially for boards larger than 5x5.

Warnsdorff's Rule

Warnsdorff's rule, proposed by H. C. von Warnsdorff in 1823, is a heuristic that dramatically improves the efficiency of the Knight's Tour search. The rule states: at each step, move to the neighboring square that has the fewest onward moves (i.e., the smallest degree in the remaining unvisited graph).

Algorithm with Warnsdorff's Rule

procedure WarnsdorffTour(board, row, col, moveCount): board[row][col] = moveCount if moveCount == n * n: return true neighbors = possibleMoves(row, col) sort neighbors by degree(neighbor) ascending for each (nextRow, nextCol) in neighbors: if isValid(nextRow, nextCol) and board[nextRow][nextCol] == 0: if WarnsdorffTour(board, nextRow, nextCol, moveCount + 1): return true board[row][col] = 0 return falsefunction degree(row, col): count = 0 for each (r, c) in possibleMoves(row, col): if isValid(r, c) and board[r][c] == 0: count = count + 1 return count

Warnsdorff's heuristic is greedy in nature: by visiting the most constrained square first, it avoids creating isolated squares early in the tour. In practice, this heuristic finds a valid tour on the first attempt for boards up to at least 76x76 without backtracking.

Tie-Breaking Strategies

When two or more neighbors have the same degree, a tie-breaking rule is needed. Common strategies include:

• Choosing the neighbor closest to the board edge (Roth's improvement)
• Choosing the neighbor closest to a corner
• Random selection among tied candidates
• Looking ahead an additional level to compare the degrees of neighbors' neighbors

Worked Example

Consider a 5x5 board with the knight starting at position (0, 0). We apply Warnsdorff's rule to construct the tour.

Step 1: Place knight at (0,0). Mark it as move 1. Available neighbors: (1,2) with degree 4, (2,1) with degree 4. Tie -- choose (2,1).

Step 2: Move to (2,1). Mark as move 2. Available neighbors: (0,2) deg 3, (4,2) deg 3, (4,0) deg 2, (3,3) deg 4, (1,3) deg 4. Choose (4,0) with smallest degree 2.

Step 3: Move to (4,0). Mark as move 3. Available neighbors: (2,1) visited, (3,2) deg 4. Move to (3,2).

Continuing this process, one possible completed 5x5 tour is:

 1 12 21 18 320 17 2 13 2211 8 19 4 1516 23 6 9 24 7 10 25 14 5

Each number indicates the order in which the knight visited that square. You can verify that consecutive numbers are always a valid knight's move apart.

Complexity Analysis

Why Backtracking Alone Is Insufficient

On an 8x8 board, the knight graph has 64 vertices and 168 edges. The number of possible move sequences is astronomically large. Plain backtracking without heuristic ordering explores the search tree in a fixed order and may spend vast amounts of time in dead-end branches. For an 8x8 board, the backtracking algorithm without pruning can take minutes or hours, whereas Warnsdorff's rule typically finds a solution in under a millisecond.

Space Complexity

Both approaches use O(n^2) space for the board representation. The recursion stack depth is also O(n^2) since the knight must visit every square. No additional data structures beyond the board and the move offsets are required.

Implementation

Python Implementation with Warnsdorff's Rule

def knight_tour(n): board = [[0] * n for _ in range(n)] moves = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] def degree(r, c): count = 0 for dr, dc in moves: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0: count += 1 return count def solve(r, c, move_num): board[r][c] = move_num if move_num == n * n: return True neighbors = [] for dr, dc in moves: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0: neighbors.append((degree(nr, nc), nr, nc)) neighbors.sort() for _, nr, nc in neighbors: if solve(nr, nc, move_num + 1): return True board[r][c] = 0 return False solve(0, 0, 1) return board

Open vs Closed Tours

An open tour is any Hamiltonian path on the knight graph -- the starting and ending squares need not be a knight's move apart. A closed tour (also called a re-entrant tour) additionally requires that the ending square is a knight's move away from the starting square, forming a Hamiltonian cycle.

Existence Results

• For the standard 8x8 board, both open and closed tours exist. There are approximately 26,534,728,821,064 directed closed tours.
• No closed tour exists on an n x n board when n is odd, because the knight alternates between light and dark squares, and an odd-sized board has unequal numbers of each color.
• Schwenk (1991) proved that an open Knight's Tour exists on an m x n board (m <= n) if and only if at least one of the following holds: (a) m and n are both at least 5, (b) m = 1 and n = 1, or with specific small-board exceptions.

A closed tour on an 8x8 board can be converted into 64 distinct open tours by choosing any square as the starting point and cutting the cycle at that position.

Applications and Variants

Cryptography and Encryption

Knight's Tour sequences have been used as a basis for simple substitution ciphers. The tour order provides a permutation of the board squares, which can be used to scramble a message arranged in a grid. While not cryptographically secure by modern standards, it illustrates how combinatorial structures can generate permutations.

Magic Knight's Tours

A magic Knight's Tour is a closed tour on an 8x8 board where, when the squares are numbered in the order visited, the resulting arrangement forms a magic square (all rows and columns sum to the same value). Semi-magic tours, where only rows and columns (but not diagonals) produce equal sums, were first discovered in the 18th century.

Neural Network Approach

Takefuji and Lee (1992) proposed using a Hopfield-style neural network to solve the Knight's Tour. Each legal move is represented by a neuron, and the network converges to a state representing a valid tour. This approach is notable for being massively parallel and potentially implementable in hardware.

Generalized Knight's Tours

The problem extends to non-standard boards (rectangular, toroidal, cylindrical) and to generalized knights that move (a, b) squares instead of the standard (1, 2). The existence of tours on these variants depends on the specific dimensions and move parameters.

References

• Euler, L. "Solution d'une question curieuse qui ne paroit soumise a aucune analyse." Memoires de l'Academie Royale des Sciences et Belles Lettres, 1759.
• Warnsdorff, H. C. von. "Des Rosselsprunges einfachste und allgemeinste Losung." Schmalkalden, 1823.
• Schwenk, A. J. "Which Rectangular Chessboards Have a Knight's Tour?" Mathematics Magazine, vol. 64, no. 5, 1991, pp. 325-332.
• Parberry, I. "An Efficient Algorithm for the Knight's Tour Problem." Discrete Applied Mathematics, vol. 73, 1997, pp. 251-260.
• Takefuji, Y. and Lee, K. C. "Neural Network Computing for Knight's Tour Problems." Neurocomputing, vol. 4, 1992, pp. 249-254.
• Conrad, A. et al. "A Combination of Local Search and Warnsdorff's Rule for the Knight's Tour Problem." Congressus Numerantium, vol. 78, 1990, pp. 191-196.