The Knight’s Tour Problem in Java

The Knight's Tour problem is a classic puzzle in which the task is to find a sequence of moves for a knight on a chessboard such that the knight visits every square exactly once. The problem can be solved using various algorithms, one of which is backtracking. Here's an example implementation of the Knight's tour problem in Java using backtracking:

Example

Input:

N = 8

Output:

14055343361922
56532372023417
3954334635182110
524738532411165
553245483926912
505152254215627
314449402981342
505130431441287

Explanation:

The output of the program is the final configuration of the chessboard after the Knight's Tour has been completed. Each number represents the move count of the knight on a particular square.

Approach: Recursive Backtracking

The approach used in this program is a recursive backtracking algorithm. The algorithm starts at a given position on the chessboard and attempts to make a valid move to the next position. It recursively explores all possible moves from each position until a solution is found or all moves have been exhausted. If a move leads to a dead end (no valid moves available), the algorithm backtracks to the previous position and tries a different move.

The backtracking process involves marking the current position on the board with the move count and then recursively exploring all possible moves from that position. If a solution is not found, the algorithm "unmarks" the current position and continues with the next move.

The algorithm stops when it reaches the move count equal to the total number of squares on the board, indicating that a solution has been found.

Example 1

In the above code, we use a 2D array called a board to represent the chessboard. Each square is initially marked as 0, indicating that it is unvisited. The solveTour() method initiates the solving process by starting at position (0, 0) and calling the solve() method recursively.

FileName: KnightsTour.java

public class KnightsTour {
 private static final int BOARD_SIZE = 8;
 private static final int[] ROW_MOVES = {-2, -1, 1, 2, 2, 1, -1, -2};
 private static final int[] COL_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};
 private int[][] board;
 public KnightsTour() {
 board = new int[BOARD_SIZE][BOARD_SIZE];
 }
 public void solveTour() {
 // Start at position (0, 0)
 solve(0, 0, 1);
 printSolution();
 }
 private void solve(int row, int col, int moveCount) {
 board[row][col] = moveCount;
 if (moveCount == BOARD_SIZE * BOARD_SIZE) {
 // Solution found here
 return;
 }
 for (int i = 0; i < 8; i++) {
 int nextRow = row + ROW_MOVES[i];
 int nextCol = col + COL_MOVES[i];
 if (isMoveValid(nextRow, nextCol)) {
 solve(nextRow, nextCol, moveCount + 1);
 if (board[nextRow][nextCol] == 0) {
 // If the next move doesn't lead to a solution, backtrack
 board[nextRow][nextCol] = 0;
 }
 }
 }
 }
 private boolean isMoveValid(int row, int col) {
 // Check if the move is within the board boundaries and the position is unvisited
 if (row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE && board[row][col] == 0) {
 return true;
 }
 return false;
 }
 private void printSolution() {
 // Print the final board configuration after the tour has been completed
 for (int i = 0; i < BOARD_SIZE; i++) {
 for (int j = 0; j < BOARD_SIZE; j++) {
 System.out.print(board[i][j] + "\t");
 }
 System.out.println();
 }
 }
 public static void main(String[] args) {
 KnightsTour tour = new KnightsTour();
 tour.solveTour();
 }
}

Output

14055343361922
56532372023417
3954334635182110
524738532411165
553245483926912
505152254215627
314449402981342
505130431441287

Complexity:

The time complexity of the Knight's Tour algorithm depends on the number of valid moves explored during the backtracking process. Since the knight can make a maximum of 8 moves from each position, the maximum number of moves that need to be explored is 8^(BOARD_SIZE * BOARD_SIZE). However, the actual number of moves explored is much less due to the backtracking mechanism.

Therefore, the time complexity of the algorithm is approximately O(8^(BOARD_SIZE * BOARD_SIZE)).

The space complexity of the code is determined by the memory required to store the chessboard and the recursive calls made during the backtracking process. The board array requires O(BOARD_SIZE * BOARD_SIZE) space to store the move count on each square.

Approach: Warnsdorff's rule

Another common approach to solving the Knight's tour problem is by using Warnsdorff's rule. Warnsdorff's rule is a heuristic that suggests always moving to the square with the fewest accessible moves.

1. Start with an empty chessboard.
2. Place the knight on any square as the starting position.
3. Repeat the following steps until a complete tour is achieved or no more moves are possible:
   • From the current position, generate all possible moves.
   • For each possible move, count the number of accessible moves from that position (i.e., the number of unvisited squares that the knight can reach).
   • Sort the possible moves in ascending order based on the count of accessible moves. Choose the move with the fewest accessible moves as the next move.
   • Move the knight to the chosen square and mark it as visited.
4. If a complete tour is achieved (i.e., the knight has visited every square on the chessboard), the algorithm terminates successfully. Otherwise, if no more moves are possible, the algorithm backtracks to the previous position and tries a different move.

Here's an implementation using Warnsdorff's rule:

The above code uses Warnsdorff's rule to select the next move based on the number of accessible moves from each square. It sorts the next possible moves in ascending order based on the count of accessible moves and then proceeds with the move that has the fewest accessible moves.

FileName: KnightsTour.java

import java.util.Arrays;
import java.util.Comparator;
public class KnightsTour {
 private static final int BOARD_SIZE = 8;
 private static final int[] ROW_MOVES = {-2, -1, 1, 2, 2, 1, -1, -2};
 private static final int[] COL_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};
// 2D array
 private int[][] board;
 public KnightsTour() {
 board = new int[BOARD_SIZE][BOARD_SIZE];
 }
 public void solveTour() {
 solve(0, 0, 1);
 printSolution();
 }
 private void solve(int row, int col, int moveCount) {
 board[row][col] = moveCount;
 if (moveCount == BOARD_SIZE * BOARD_SIZE) {
 // Solution found
 return;
 }
 // Generate the next possible moves
 int[][] nextMoves = getNextMoves(row, col);
 // Sort the moves based on the number of accessible moves from each square
 Arrays.sort(nextMoves, Comparator.comparingInt(move -> countAccessibleMoves(move[0], move[1])));
 for (int[] nextMove : nextMoves) {
 int nextRow = nextMove[0];
 int nextCol = nextMove[1];
 if (board[nextRow][nextCol] == 0) {
 solve(nextRow, nextCol, moveCount + 1);
 if (board[nextRow][nextCol] == 0) {
 // If the next move doesn't lead to a solution, backtrack
 board[nextRow][nextCol] = 0;
 }
 }
 }
 }
 private int[][] getNextMoves(int row, int col) {
 int[][] nextMoves = new int[8][2];
 int index = 0;
 for (int i = 0; i < 8; i++) {
 int nextRow = row + ROW_MOVES[i];
 int nextCol = col + COL_MOVES[i];
 if (isMoveValid(nextRow, nextCol)) {
 nextMoves[index][0] = nextRow;
 nextMoves[index][1] = nextCol;
 index++;
 }
 }
 return nextMoves;
 }
 private boolean isMoveValid(int row, int col) {
 // Check if the move is within the board boundaries and the position is unvisited
 if (row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE && board[row][col] == 0) {
 return true;
 }
 return false;
 }
 private int countAccessibleMoves(int row, int col) {
 // Count the number of accessible moves from a given position
 int count = 0;
 for (int i = 0; i < 8; i++) {
 int nextRow = row + ROW_MOVES[i];
 int nextCol = col + COL_MOVES[i];
 if (isMoveValid(nextRow, nextCol)) {
 count++;
 }
 }
 return count;
 }
 private void printSolution() {
 // Print the final board configuration after the tour has been completed
 for (int i = 0; i < BOARD_SIZE; i++) {
 for (int j = 0; j < BOARD_SIZE; j++) {
 System.out.print(board[i][j] + "\t");
 }
 System.out.println();
 }
 }
 public static void main(String[] args) {
 KnightsTour tour = new KnightsTour();
 tour.solveTour();
 }
}

Output:

11627223184756
26232174657419
1528256221485558
243530456063205
2914613449445954
36313841645369
134033501184352
323712394251107

Complexity

The time complexity of the KnightsTour code using Warnsdorff's rule is O(N^2 * log(N^2)), where N is the size of the chessboard (in this case, N = 8).

The main factor contributing to the time complexity is the sorting operation performed on the nextMoves array in each recursive call. The sorting operation has a time complexity of O(N^2 * log(N^2)) since the nextMoves array has a maximum of N^2 elements, and the comparison function takes O(1) time.

The space complexity of the code is O(N^2) since it uses a 2D array to represent the chessboard. The board array occupies N^2 elements of space.

Time complexity: O(N^2 * log(N^2))

Space complexity: O(N^2)