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:
1 40 55 34 3 36 19 22 56 53 2 37 20 23 4 17 39 54 33 46 35 18 21 10 52 47 38 53 24 11 16 5 55 32 45 48 39 26 9 12 50 51 52 25 42 15 6 27 31 44 49 40 29 8 13 42 50 51 30 43 14 41 28 7
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] + " "); } System.out.println(); } } public static void main(String[] args) { KnightsTour tour = new KnightsTour(); tour.solveTour(); } }
Output
1 40 55 34 3 36 19 22 56 53 2 37 20 23 4 17 39 54 33 46 35 18 21 10 52 47 38 53 24 11 16 5 55 32 45 48 39 26 9 12 50 51 52 25 42 15 6 27 31 44 49 40 29 8 13 42 50 51 30 43 14 41 28 7
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.
- Start with an empty chessboard.
- 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] + " "); } System.out.println(); } } public static void main(String[] args) { KnightsTour tour = new KnightsTour(); tour.solveTour(); } }
Output:
1 16 27 22 3 18 47 56 26 23 2 17 46 57 4 19 15 28 25 62 21 48 55 58 24 35 30 45 60 63 20 5 29 14 61 34 49 44 59 54 36 31 38 41 64 53 6 9 13 40 33 50 11 8 43 52 32 37 12 39 42 51 10 7
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)