Knight's Tour
Move a knight so it visits every square of the board exactly once. At each square, try the 8 knight moves in order and recurse; if every move leads to a dead end, backtrack and try the previous square's next option.
- Category
- Backtracking
- Time complexity
- O(8^(n²))
- Space complexity
- O(n²)
Pseudocode
place knight, mark square visited try each of 8 knight moves in order recurse; all visited ⇒ solved no move works ⇒ unmark, backtrack
Reference implementation
def solve(r, c, num):
board[r][c] = num
if num == n*n: return True
for dr, dc in KNIGHT_MOVES:
if valid(r+dr, c+dc) and solve(r+dr, c+dc, num+1):
return True
board[r][c] = 0 # backtrack