Log inSign up
hardGeeksforGeeksNot Started

Knight's Tour

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer N, representing the dimensions of an N x N chessboard, determine a valid Knight's Tour starting from the top-left square (0, 0).

A Knight's Tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once.

Return an N x N 2D matrix board where board[r][c] contains the step number (from 0 to N*N - 1) at which the square was visited. If no tour exists, return an empty matrix or -1.

Example 1 · 5x5 Knight's Tour:

Input: N = 5
Output: [[0, 11, 16, 5, 18], [15, 6, 19, 12, 23], [10, 1, 22, 17, 4], [7, 14, 9, 24, 13], [2, 21, 8, 3, 20]]
Explanation: Every cell from 0 to 24 is visited exactly once via legal knight moves.

Example 2 · 1x1 Trivial Board:

Input: N = 1
Output: [[0]]
Explanation: Single square visited at step 0.

Constraints:

  • 1 <= N <= 8

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master grid backtracking with fixed delta jump vectors.
  • Understand the power of Warnsdorff's greedy lookahead heuristic.
  • Visualize 2D board state exploration.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Visit every cell on an N x N grid exactly once
  • Movement constrained by knight's 8 L-shaped jumps
  • Hamiltonian path on knight's graph

Algorithmic Decision Tree:

  • Use 8 delta vectors dx = [2, 1, -1, -2, -2, -1, 1, 2], dy = [1, 2, 2, 1, -1, -2, -2, -1].
  • Check boundary: 0 <= nr < N && 0 <= nc < N && board[nr][nc] == -1.
  • Warnsdorff's rule: sort candidate neighbors by ascending count of onward unvisited neighbors.

Connected Patterns:

Rat in a MazeN-QueensHamiltonian Path

1. Pure DFS Backtracking (Arbitrary Move Order)

Intuition

Place knight at (0, 0) with step 0. From (r, c), iterate through the 8 directions in fixed array order. If next cell is inside board and unvisited, mark with step + 1 and recurse. If all 8 moves fail, reset cell to -1 and return false.

When to apply: Sufficient for small boards (N <= 5).

Algorithm

  1. Initialize N x N board with -1.
  2. Set board[0][0] = 0.
  3. In solve(r, c, step):
  4. - If step == N * N, return true (tour complete).
  5. - Loop k from 0 to 7 for 8 knight moves:
  6. - If (nr, nc) is valid and board[nr][nc] == -1:
  7. - board[nr][nc] = step.
  8. - If solve(nr, nc, step + 1) returns true, return true.
  9. - Backtrack: board[nr][nc] = -1.
  10. - Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
8 int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
9
10 bool solve(int r, int c, int step, int n, vector<vector<int>>& board) {
11 if (step == n * n) return true;
12
13 for (int i = 0; i < 8; i++) {
14 int nr = r + dx[i];
15 int nc = c + dy[i];
16
17 if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] == -1) {
18 board[nr][nc] = step;
19 if (solve(nr, nc, step + 1, n, board)) return true;
20 board[nr][nc] = -1; // backtrack
21 }
22 }
23 return false;
24 }
25
26public:
27 vector<vector<int>> knightsTour(int n) {
28 vector<vector<int>> board(n, vector<int>(n, -1));
29 board[0][0] = 0;
30 if (solve(0, 0, 1, n, board)) return board;
31 return {};
32 }
33};
34
35int main() {
36 Solution sol;
37 auto board = sol.knightsTour(5);
38 for (const auto& row : board) {
39 for (int v : row) printf("%2d ", v);
40 cout << endl;
41 }
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(8^(N^2)) — Worst-case branching factor of 8 at each of the N2 cells.
  • Space complexity: O(N^2) — Recursion call stack depth is N2.

2. Degree Lookahead Pruning (Filtered Next Moves)

Intuition

Before picking a move, calculate how many unvisited neighbors each potential square has. If a square has 0 onward moves and we are not on the final step, skip it immediately.

When to apply: Medium sized boards (N = 6).

Algorithm

  1. Calculate unvisited neighbor count for each valid move.
  2. Reject moves that create isolated unreachable cells.
  3. Recurse on valid remaining moves.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
8 int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
9
10 int countNeighbors(int r, int c, int n, const vector<vector<int>>& board) {
11 int count = 0;
12 for (int i = 0; i < 8; i++) {
13 int nr = r + dx[i], nc = c + dy[i];
14 if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] == -1) count++;
15 }
16 return count;
17 }
18
19 bool solve(int r, int c, int step, int n, vector<vector<int>>& board) {
20 if (step == n * n) return true;
21
22 for (int i = 0; i < 8; i++) {
23 int nr = r + dx[i], nc = c + dy[i];
24 if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] == -1) {
25 int onward = countNeighbors(nr, nc, n, board);
26 if (onward == 0 && step < n * n - 1) continue; // dead-end filter
27
28 board[nr][nc] = step;
29 if (solve(nr, nc, step + 1, n, board)) return true;
30 board[nr][nc] = -1;
31 }
32 }
33 return false;
34 }
35
36public:
37 vector<vector<int>> knightsTour(int n) {
38 vector<vector<int>> board(n, vector<int>(n, -1));
39 board[0][0] = 0;
40 if (solve(0, 0, 1, n, board)) return board;
41 return {};
42 }
43};
44
45int main() {
46 Solution sol;
47 auto b = sol.knightsTour(5);
48 for (const auto& r : b) {
49 for (int v : r) printf("%2d ", v);
50 cout << endl;
51 }
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(8^(N^2)) (reduced branching factor) — Pruning dead ends reduces average branching factor significantly.
  • Space complexity: O(N^2) — Recursion depth is N2.

3. Warnsdorff's Minimum Degree Heuristic (Optimal)

Intuition

Warnsdorff's rule states: the knight always moves to the adjacent unvisited square with the fewest onward unvisited moves. By visiting constrained perimeter/corner cells first, we prevent them from becoming isolated, stranded dead ends. This achieves nearly 0 backtrack operations on standard chessboards.

When to apply: The gold standard optimal solution solving N=8 and larger boards in O(N2) near-linear time.

Algorithm

  1. From current (r, c), find all valid unvisited moves (nr, nc).
  2. For each move, calculate its degree (count of unvisited neighbors).
  3. Sort candidate moves in ascending order of degree.
  4. Recurse in sorted order.

5x5 Board Step Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 0: Place Knight at (0, 0)
Visual state
Values and pointers at this exact step
matrix
c0
r0
0 (Start)
Variables at this step
currentStep
0
pos
[0,0]
Why this step matters

Step 0: Place Knight at (0, 0). Mark board[0][0] = 0.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
9 int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
10
11 int getDegree(int r, int c, int n, const vector<vector<int>>& board) {
12 int count = 0;
13 for (int i = 0; i < 8; i++) {
14 int nr = r + dx[i];
15 int nc = c + dy[i];
16 if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] == -1) {
17 count++;
18 }
19 }
20 return count;
21 }
22
23 bool solve(int r, int c, int step, int n, vector<vector<int>>& board) {
24 if (step == n * n) return true;
25
26 // Collect all valid next moves and their degrees
27 vector<pair<int, pair<int, int>>> nextMoves;
28 for (int i = 0; i < 8; i++) {
29 int nr = r + dx[i];
30 int nc = c + dy[i];
31 if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] == -1) {
32 int deg = getDegree(nr, nc, n, board);
33 nextMoves.push_back({deg, {nr, nc}});
34 }
35 }
36
37 // Warnsdorff's Rule: Sort by ascending degree
38 sort(nextMoves.begin(), nextMoves.end());
39
40 for (const auto& move : nextMoves) {
41 int nr = move.second.first;
42 int nc = move.second.second;
43
44 board[nr][nc] = step;
45 if (solve(nr, nc, step + 1, n, board)) return true;
46 board[nr][nc] = -1; // backtrack
47 }
48
49 return false;
50 }
51
52public:
53 vector<vector<int>> knightsTour(int n) {
54 vector<vector<int>> board(n, vector<int>(n, -1));
55 board[0][0] = 0;
56 if (solve(0, 0, 1, n, board)) return board;
57 return {};
58 }
59};
60
61int main() {
62 Solution sol;
63 auto board = sol.knightsTour(8);
64 for (const auto& row : board) {
65 for (int v : row) printf("%2d ", v);
66 cout << endl;
67 }
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O(N^2) — Warnsdorff's heuristic avoids almost all dead ends, finding a solution in O(N2) steps.
  • Space complexity: O(N^2) — Board and recursion stack take O(N2) memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pure DFS BacktrackingO(8^(N^2))O(N^2)Explore 8 knight moves in fixed array order.Massive blind search space
2.Degree Lookahead PruningO(8^(N^2)) (reduced branching)O(N^2)Prune candidate moves with zero onward unvisited neighbors.Unsorted candidate traversal
3.Warnsdorff's Minimum Degree HeuristicOptimalO(N^2)O(N^2)Sort candidate moves ascending by number of unvisited neighbors.Neighbor sorting overhead

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Sorting by descending degree instead of ascending degree (which causes the knight to visit central squares with many exits first, stranding corners).

Pitfall 2:

Not initializing the board to -1.

Pitfall 3:

Forgetting to backtrack when all candidate branches fail.

Crucial Edge Cases to Validate:

  • N = 1: Single cell board [[0]] is already a complete tour.
  • N = 2, 3: No full Knight's Tour exists on 2x2 or 3x3 boards -> returns empty board.
  • N = 8 Standard Chessboard: Warnsdorff's heuristic solves 64 steps instantaneously.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention Warnsdorff's algorithm by name — it immediately shows mastery of graph heuristics and constraint satisfaction.
  2. Explain that Knight's Tour is a special instance of finding a Hamiltonian Path on a graph.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the core principle behind Warnsdorff's Heuristic in solving the Knight's Tour?

2.How many distinct legal moves can a knight make from an unconstrained center square on a chessboard?

Back to DSA Sheet