LeetCode 2664: The Knight’s Tour Solution

Master LeetCode problem 2664 (The Knight’s Tour), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2664. The Knight’s Tour

Medium

Array Backtracking Matrix

Problem Explanation

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.

: :

Solution Code

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();
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2664 (The Knight’s Tour)?

This page provides optimized solutions for LeetCode problem 2664 (The Knight’s Tour) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2664 (The Knight’s Tour)?

The time complexity for LeetCode 2664 (The Knight’s Tour) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2664 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2664 in Java, C++, or Python.

Back to LeetCode Solutions