2664. The Knight’s Tour

Explanation:

The Knight's Tour problem is a classic puzzle where the goal is to find a sequence of moves for a knight on a chessboard such that the knight visits every square exactly once. The knight moves in an L-shape, two squares in one direction and one square in a perpendicular direction.

To solve this problem, we can use backtracking. We start with the knight placed on any square on the chessboard and recursively try all possible moves from that position. If a move is valid (within the board boundaries and not visited before), we mark that square as visited and move to the next square. If we reach a dead end where no more moves are possible, we backtrack to the previous position and try a different move.

The algorithm explores all possible paths until it finds a solution or exhausts all possibilities.

Algorithm:

Create a chessboard of size N x N where N is the size of the board.
Initialize the chessboard with all squares unvisited.
Start from any square on the board and perform a depth-first search (DFS) with backtracking.
If a move is valid, mark the square as visited and move to the next square.
If all squares are visited, the tour is complete. Print the path.
If no valid moves are left, backtrack to the previous square and try a different move.
Repeat steps 4-6 until a solution is found.

Time Complexity:

The time complexity of the Knight's Tour problem using backtracking is exponential, O(8^(N^2)), where N is the size of the chessboard.

Space Complexity:

The space complexity of the algorithm is O(N^2) to store the chessboard and the recursive call stack for backtracking.

: :

View Leetcode Problem

public class KnightsTour {
    public static void main(String[] args) {
        int N = 8; // Size of the chessboard
        int[][] board = new int[N][N];
        int moveNumber = 1;

        if (!solveKnightsTour(board, 0, 0, moveNumber)) {
            System.out.println("No solution found.");
        } else {
            printBoard(board);
        }
    }

    public static boolean solveKnightsTour(int[][] board, int row, int col, int moveNumber) {
        // Base case: all squares visited
        if (moveNumber == board.length * board.length + 1) {
            return true;
        }

        if (isSafe(board, row, col)) {
            board[row][col] = moveNumber;

            int[] rowMoves = {2, 1, -1, -2, -2, -1, 1, 2};
            int[] colMoves = {1, 2, 2, 1, -1, -2, -2, -1};

            for (int i = 0; i < 8; i++) {
                int nextRow = row + rowMoves[i];
                int nextCol = col + colMoves[i];

                if (solveKnightsTour(board, nextRow, nextCol, moveNumber + 1)) {
                    return true;
                }
            }

            board[row][col] = 0; // Backtrack
        }

        return false;
    }

    public static boolean isSafe(int[][] board, int row, int col) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length && board[row][col] == 0;
    }

    public static void printBoard(int[][] board) {
        for (int[] row : board) {
            for (int cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.