Problem

The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once. Knight starts from chess position [0,0] generate the knight’s path.

What

The problem states that, given a N*M chessboard, a Knight’s Tour is defined as the sequence of moves of a Knight, such that the Knight visits every square only once.

If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. (Source : wiki)

Here is the Knight’s path(gif):

If you prefer video format:

Similar

Does this sound similar? Yes it is similar to finding the Hamiltonian Path as defined in Hamiltonian Path.

The Hamiltonian Path also requires visiting every vertex in a graph exactly once, and Knight’s tour requires Knight must visit every square of the chessboard exactly once.

Also, similar problem - Count Knight’s Tour.

Solution

Method 1 - Backtracking

The knight moves in an L-shape: two squares in one direction and then one square perpendicular to that, or one square in one direction and then two squares perpendicular to that. On a standard 8x8 chessboard, the problem is to determine a sequence of moves such that the knight visits every square exactly once.

A Knight on any given cell of the chessboard can have up to eight possible moves. These moves are characterized by the relative positions: ({ { 2, 1 }, { 2, -1 }, { 1, 2 }, { 1, -2 }, { -2, 1 }, { -2, -1 }, { -1, 2 }, { -1, -2 } }).

Defining Safe Move

Let’s define what constitutes a safe cell for the Knight to move to. There are three main conditions:

  • The target cell must be within the board’s boundaries.
  • The cell must not have been visited before.
  • The cell must be accessible from the current position using any of the valid knight moves.

Approach

The backtracking algorithm will use recursion to attempt to move the knight to all possible spots. If it can’t find a valid solution from a given position, it will backtrack and try a different path.

Suppose the Knight is currently at position (r, c) and has already moved to k-1 cells. To determine the kth move, we consider all possible safe moves. When a safe move is found, the Knight is placed on the new cell, and we proceed to the (k+1)th move. But what if, further along, no safe moves are available and cells remain unvisited?

  • In such cases, the partial solution is discarded, and the previous cell is emptied where the failure occurred.
  • We then try the remaining moves for that cell.
  • This process is repeated until all cells are visited according to the rules.

Here’s the step-by-step approach in code:

  1. Maintain a solution board to keep track of visited squares.
  2. Start from position (0, 0) with index = 0 (index tracks the number of cells the Knight has visited).
  3. Ensure the current cell is unvisited. If it is, mark it (start with 0 and increment, showing the Knight’s path). Lets mark Knight’s path by variable moveCount
  4. Check if moveCount = N*N - 1, indicating the Knight has covered all cells. If so, return true and print the solution matrix.
  5. Define all possible 8 moves a knight can make
  6. Use a recursive function to try each move checking the boundary condition, marking the square as visited.
  7. If the move doesn’t lead to a solution, backtrack and try another move.

Refer to the code for a clearer understanding.

Code

Java
public class KnightsTour {

	private final int N = 8;

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

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

	public void solveKnightsTour(int N) {
		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;
			}
		}

		// Starting position
		int moveX = 0;
		int moveY = 0;
		board[moveX][moveY] = 0;

		if (!solve(board, moveX, moveY, 1)) {
			System.out.println("Solution does not exist.");
		} else {
			printBoard(board);
		}
	}

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

		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;

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

		return false;
	}

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

	private void printBoard(int[][] board) {
		for (int[] row: board) {
			for (int cell: row) {
				System.out.printf("%2d ", cell);
			}

			System.out.println();
		}
	}
}

Output

For eg. n = 5, this is the output:

00 03 16 09 20 
15 10 01 04 17 
02 19 08 21 14 
11 06 23 18 05 
22 13 12 07 24

Complexity

  • ⏰ Time complexity: O(8 ^ (N^2))
    • Recursive Calls: Each position on the board can make up to 8 possible knight moves.
    • Depth of Recursion: In the worst case, the depth of the recursion can be N^2 since the knight needs to visit every cell on an N x N board.
  • 🧺 Space complexity: O(N*N)
    • The board itself is an (N * N) matrix.
    • he recursion stack can go as deep as (N^2) in the worst case because we may need to visit every cell.