The Knight's tour
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.
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;}