The Knight's tour

Hard

Problem

Move a knight around an n × n board so that it visits every square exactly once. Return the board with each square numbered by its visiting order (the backtracking version is usually shown with n = 8).

Example 1

Input:  n = 5, start (0, 0)
Output: a 5 × 5 grid numbered 0..24 in knight-move order

Also asked as: The Knight’s tour problem

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. DFS numbering squares; backtrack on dead ends

Time exponential (Warnsdorff heuristic makes it fast)Space O(N²)

From the current square, try all 8 knight moves to an unvisited in-bounds square; mark it with the move number; recurse; unmark on failure.

function knightTour(N) {
const board = Array.from({ length: N }, () => Array(N).fill(-1));
const moves = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];
board[0][0] = 0;
const bt = (r, c, step) => {
if (step === N * N) return true;
for (const [dr, dc] of moves) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < N && nc < N && board[nr][nc] === -1) {
board[nr][nc] = step;
if (bt(nr, nc, step + 1)) return true;
board[nr][nc] = -1;
}
}
return false;
};
return bt(0, 0, 1) ? board : null;
}