The Knight’s Tour problem involves moving a knight on a chessboard such that it visits every square exactly once. The solution can be implemented using backtracking.

Java Program

public class KnightsTour {
    private static final int N = 8; // Size of the chessboard
    private static final int[] X_MOVES = {2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] Y_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};

    public static void main(String[] args) {
        int[][] board = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = -1; // Initialize the board
            }
        }
        board[0][0] = 0; // Starting position
        if (solveKT(board, 0, 0, 1)) {
            printSolution(board);
        } else {
            System.out.println("Solution does not exist.");
        }
    }

    private static boolean solveKT(int[][] board, int currRow, int currCol, int movei) {
        if (movei == N * N) {
            return true; // All squares are visited
        }

        for (int k = 0; k < 8; k++) { int nextRow = currRow + X_MOVES[k]; int nextCol = currCol + Y_MOVES[k]; if (isSafe(nextRow, nextCol, board)) { board[nextRow][nextCol] = movei; // Make the move if (solveKT(board, nextRow, nextCol, movei + 1)) { return true; // Recur for the next move } board[nextRow][nextCol] = -1; // Backtrack } } return false; // No valid move found } private static boolean isSafe(int x, int y, int[][] board) { return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
    }

    private static void printSolution(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf("%2d ", board[i][j]);
            }
            System.out.println();
        }
    }
}

Program Structure

• Constants: The program defines the size of the chessboard (8×8) and the possible moves of the knight.
• Main Method: Initializes the chessboard, sets the starting position of the knight, and invokes the solving function.
• solveKT Method: Implements backtracking to find a solution for the Knight’s Tour problem.
• isSafe Method: Checks if the knight’s next move is within the bounds of the chessboard and hasn’t been visited yet.
• printSolution Method: Prints the chessboard showing the knight’s tour path.

Explanation of the Code Structure:

1. Constants:
   • The chessboard size (N = 8) and possible knight moves are defined using arrays.
2. Main Method:
   • Initializes a board filled with -1 (indicating unvisited squares).
   • Sets the starting position for the knight and initiates the solving process.
3. solveKT Method:
   • Implements the backtracking algorithm. It checks if all squares are visited and tries each possible knight move.
   • If a move is valid, it marks the square and recursively attempts the next move. If it fails, it backtracks.
4. isSafe Method:
   • Verifies if the knight’s next move is within bounds and the square hasn’t been visited.
5. printSolution Method:
   • Displays the board with the knight’s path.

This program will provide a solution to the Knight’s Tour problem if one exists and displays the path taken by the knight on the chessboard.

Documentation

This Java program uses backtracking to solve the Knight’s Tour problem. The knight’s movement options are represented using arrays for easy access. The program initializes an 8×8 board and starts the knight from the top-left corner (0,0). It recursively attempts to fill the board, backtracking if a move does not lead to a solution.

To run this program, simply copy the code into a Java development environment, compile it, and execute the main method.