Problem

A knight’s tour is a sequence of moves by a knight on a chessboard such that all squares are visited once.

Given N, write a function to return the number of knight’s tours on an N by N chessboard.

We have already see Knight’s Tour

Examples

Example 1:

1
2

Input: n = 5
Output: 1728

Solution

Method 1 - Backtracking

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class KnightsTourCounter {
	// Possible moves of the knight
	private final int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };

	private final int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };

	private int N;

	private int tourCount;

	public static int countKnightsTours(int n) {
		N = n;
		tourCount = 0;
		int[][] board = new int[N][N];

		// Initialize the board with -1
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = -1;
			}
		}

		// Start from (0, 0)
		board[0][0] = 0;
		solve(board, 0, 0, 1);
		return tourCount;
	}

	private void solve(int[][] board, int x, int y, int moveCount) {
		if (moveCount == N * N) {
			tourCount++;
			return;
		}

		for (int i = 0; i < dx.length; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];

			if (isSafe(nextX, nextY, board)) {
				board[nextX][nextY] = moveCount;
				solve(board, nextX, nextY, moveCount + 1);
				board[nextX][nextY] = -1; // Backtracking
			}
		}
	}

	private boolean isSafe(int x, int y, int[][] board) {
		return x >= 0 && x < N && y >= 0 && y  <  N && board[x][y] == -1;
	}
}

Complexity

  • ⏰ Time complexity: O(8 ^ (N^2))
    • Each position on the board can make up to 8 possible knight moves.
    • In the worst case, the depth of the recursion can be ( N^2 ) since the knight needs to visit every cell on an N^2
    • For each of the ( N^2 ) cells, you can have up to 8 possible moves. This gives a high upper bound on the number of recursive calls.
  • 🧺 Space complexity: O(N*N)
    • The board itself is an(N*N) matrix
    • Recursion stack can go as deep as N^2