2664. The Knight’s Tour


Problem Description

The problem requires us to simulate the tour of a knight on a chessboard. Given a 2D-array with dimensions m by n representing the chessboard, and a starting position (r, c) for the knight, we need to move the knight around the board in such a way that every cell is visited exactly once. The board is 0-indexed, meaning the cells are counted from 0. The values in the cells of the array should represent the order in which each cell is visited, starting from 0 at the initial position of the knight.

A knight in chess moves in an "L" shape, meaning it can move either two squares in one direction and then one square perpendicular to that, or one square in one direction and then two squares perpendicular to that. Mathematically, this means that for a move from (r1, c1) to (r2, c2): min(abs(r1 - r2), abs(c1 - c2)) should be 1 and max(abs(r1 - r2), abs(c1 - c2)) should be 2, with (r2, c2) being in the bounds of the board.

The problem provides the constraints that the board's dimensions m and n will not exceed 5, which suggests the problem is expecting a brute-force or backtracking approach due to the small input size. The problem guarantees that there is at least one possible way to tour the entire board from the starting position.

Flowchart Walkthrough

Let's analyze LeetCode 2664. The Knight’s Tour using the provided algorithm flowchart. Here's how we can step through the decision-making process:

  1. Is it a graph?

    • Yes: This problem can be thought of as a graph-related issue where each position on the chessboard represents a node and moves of the knight represent the edges connecting these nodes.
  2. Need to solve for kth smallest/largest?

    • No: The task is not about finding kth smallest or largest value but rather about finding a route for the knight.
  3. Involves Linked Lists?

    • No: The problem does not utilize linked lists; it uses a chessboard matrix/grid representation.
  4. Does the problem have small constraints?

    • Yes: The problem involves a confined chessboard (usually 8x8 or similar), which suggests that the constraints are relatively small.
  5. Brute force / Backtracking?

    • Yes: Given the small constraints and the nature of the problem, which involves exploring all possible moves of a knight on a chessboard to cover all spaces without repeating, backtracking is the suitable approach. This allows us to undo moves (backtrack) if they lead to a dead-end.

Conclusion: Based on the flowchart’s guidance, a backtracking approach is recommended for solving the Knight’s Tour problem. It involves exploring all potential sequences of moves, backtracking when necessary, and using suitable structures to maintain state and undo decisions. This matches the typical problem-solving pattern used in other Chessboard-based problems where possible moves and constraints are explored exhaustively.

Intuition

The solution follows a backtracking approach, which is a common technique used to solve problems that require exploring all possible combinations or permutations to find a solution that meets certain criteria. Backtracking is akin to a depth-first search on a decision tree of all possible moves. It works by trying out moves one by one and recursively continuing the process. If at any point, it's found that a particular sequence of moves doesn't lead to a solution (i.e., a dead end is reached), the algorithm backtracks, undoing the last move and trying the next possible move.

In this scenario, since the board size is small, the backtracking approach is suitable due to its exhaustive nature of exploring all possible knight tours. The algorithm starts from the starting cell, marks it as visited by setting the order of visit to 0 and then tries all possible moves a knight can make from that cell using the chess knight's movement rules. Whenever it moves to a new cell, it marks that cell with the next number in the sequence.

If a point is reached where no further moves are possible and not all cells are visited, the algorithm backtracks - it undoes the last move by resetting the cell's value to unvisited (marked by -1 in the implementation) and tries a different move from the previous cell.

The process continues recursively until every cell has been visited exactly once, at which point the solution is found, and the backtracking ceases. If a complete tour is found, the ok variable is used to stop the search upon finding the first solution, which is guaranteed to exist according to the problem statement.

The given solution defines the dfs function which is used for the depth-first search and backtracking. It uses a grid g initialized with -1 to mark unvisited cells. The grid is updated with the visiting order as the knight moves around. The ok variable is used as a flag to indicate the completion of a successful tour, avoiding further unnecessary recursion once a full tour is found.

Learn more about Backtracking patterns.

Solution Approach

The solution uses the Depth-First Search (DFS) algorithm for backtracking and a 2D grid to represent the chessboard. Here is a step-by-step explanation of how the solution is implemented:

  1. Initial Setup: A 2D list g is created with dimensions m by n, and all cells are initialized to -1, indicating they are unvisited. The starting cell (r, c) is set to 0 to indicate the knight starts from there.

  2. Depth-First Search: The DFS function is called with the starting cell. It defines the base case for DFS where if the current cell's value indicates that it is the last cell to be visited (value is m * n - 1), and it sets the flag ok to True to indicate that the tour is complete.

  3. Exploring Moves: The DFS function explores all possible moves a knight can make from the current cell. It iterates through a pairwise sequence of relative moves that a knight can make. The pairwise helper in this context generates the movement vector (e.g., moving two squares up and one square right).

  4. Validating Moves: Before moving to a cell, it checks if the cell (x, y) is within the bounds of the grid and if it hasn't been visited yet (g[x][y] == -1).

  5. Making Moves: If the move is valid, the knight moves to that cell by setting g[x][y] to the next sequence number post-incrementing the sequence number of the current cell g[i][j].

  6. Recursive Backtracking: After making a move, DFS recurses from the new cell (x, y). If during any of these recursive calls, the tour is found to be complete (ok is True), the recursion unwinds, and no further calls are made.

  7. Undoing Moves: If a move does not lead to a solution (i.e., it is not possible to move to a next valid cell), the algorithm backtracks by resetting the cell's value to -1 (indicating it is unvisited) and trying another move from the current sequence of choices.

  8. Stopping Condition: The recursion stops entirely when the tour is complete (all cells are visited once). The flag ok is used effectively to halt further recursive calls.

  9. Output: Once the full tour is achieved, the filled 2D grid g is returned, showing the order of the cells visited by the knight.

The approach uses no extra space beyond the grid and the call stack for recursion. The time complexity depends on the number of possible paths and the efficiency of backtracking in pruning the search space. Given the small board sizes guaranteed by the problem constraints, this brute-force backtracking approach is efficient and suitable for finding the knight's tour.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have a chessboard with dimensions m = 2, n = 3, and the knight's starting position is (r = 0, c = 0). The knight will make moves in a way that attempts to visit all cells on this chessboard exactly once.

  1. Initial Setup: We create a 2D list g with m * n cells, all set to -1. The board looks like this:
[[-1, -1, -1],
 [-1, -1, -1]]

We then set the starting cell (0,0) to 0 to indicate the knight's beginning:

[[ 0, -1, -1],
 [-1, -1, -1]]
  1. Depth-First Search: Starting from cell (0,0), the DFS function begins the search for a valid tour.

  2. Exploring Moves: From (0,0), the knight can move to (1,2) or (2,1). However, since our board is only 2 x 3, the move would be to (1,2) because (2,1) is out of bounds. After moving, the board looks like this:

[[ 0, -1, -1],
 [-1, -1,  1]]
  1. Validating Moves: The knight is now at (1,2). It attempts to find the next move that is within bounds and on an unvisited cell. The possible moves would be to (0,0), which is already visited, or (0,1) and (2,0) - both of which are out of bounds. Therefore, the only valid move from here is to (0,1).

  2. Making Moves: We move the knight to (0,1) and increment the sequence number. The board now looks like:

[[ 0,  2, -1],
 [-1, -1,  1]]
  1. Recursive Backtracking: Now at (0,1), we continue with our DFS recursion. The possible moves from here would be (1,3), (2,2), (2,0), or (1,-1). All these moves are out of bounds, except for (2,0). But as our board is only 2 rows high, (2,0) doesn't exist, so the knight cannot move further from (0,1).

Since there are no other moves to make here, the algorithm backtracks to the previous cell (1,2) and marks (0,1) as unvisited:

[[ 0, -1, -1],
 [-1, -1,  1]]
  1. Undoing Moves: At (1,2), we find that all moves lead to already visited cells or are out of bounds. Thus, we backtrack again to the starting cell (0,0).

  2. Stopping Condition: Our backtracking brings us back to the start. We would then try any other moves that were not tried before from the starting position. However, in our small 2x3 board, the only moves were to (1,2) which we already attempted. Thus, we can conclude our search with this particular path:

[[ 0, -1, -1],
 [-1, -1,  1]]
  1. Output: This DFS and backtracking process would continue exploring all possible moves until either a successful tour is constructed, or all possibilities have been exhausted. In our case with a 2x3 board, it's not actually possible to tour all cells exactly once starting from (0,0). For a larger board, the steps above would continue until such a tour is found or determined to be impossible.

In practice, for a larger board size, you'd likely see more recursive calls and backtracking as the knight tries different paths through the grid, until finally discovering a path that visits every square exactly once, or concluding that no such path exists from the given starting position.

Solution Implementation

1from typing import List
2
3class Solution:
4    def tourOfKnight(self, m: int, n: int, start_row: int, start_col: int) -> List[List[int]]:
5        # Helper function for depth-first search algorithm.
6        def dfs(row: int, col: int):
7            # Mark the search as successful when the last cell is reached.
8            if grid[row][col] == m * n - 1:
9                self.found_path = True
10                return
11          
12            # Try all possible moves a knight can make.
13            # (-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)
14            for row_offset, col_offset in zip([-2, -1, 1, 2, 2, 1, -1, -2], [-1, -2, -2, -1, 1, 2, 2, 1]):
15                next_row, next_col = row + row_offset, col + col_offset
16              
17                # Check if the next move is within the board boundaries and the cell is unvisited.
18                if 0 <= next_row < m and 0 <= next_col < n and grid[next_row][next_col] == -1:
19                    # Mark the cell with the step number in the path.
20                    grid[next_row][next_col] = grid[row][col] + 1
21                    # Continue searching for a path from the new cell.
22                    dfs(next_row, next_col)
23                    # If a full path has been found, return early.
24                    if self.found_path:
25                        return
26                    # If the path does not lead to a solution, backtrack.
27                    grid[next_row][next_col] = -1
28      
29        # Initialize the grid with -1 indicating unvisited cells.
30        grid = [[-1] * n for _ in range(m)]
31      
32        # Start the knight's tour from the given starting position.
33        grid[start_row][start_col] = 0
34      
35        # Variable indicating if a full tour path has been found.
36        self.found_path = False
37      
38        # Perform a depth-first search to find the knight's tour path.
39        dfs(start_row, start_col)
40      
41        # Return the completed grid showing the knight's tour path.
42        return grid
43
1class Solution {
2    private int[][] grid; // The chessboard representation
3    private int rows;     // Number of rows in the chessboard
4    private int cols;     // Number of columns in the chessboard
5    private boolean solutionFound; // Flag to indicate if a solution is found
6
7    // Method to generate the tour of a knight on a chessboard
8    public int[][] tourOfKnight(int rows, int cols, int startRow, int startCol) {
9        this.rows = rows;
10        this.cols = cols;
11        this.grid = new int[rows][cols];
12        this.solutionFound = false;
13
14        // Initialize all cells as unvisited by setting them to -1
15        for (int[] row : grid) {
16            Arrays.fill(row, -1);
17        }
18      
19        // Start tour at the given starting position by setting it to 0
20        grid[startRow][startCol] = 0;
21      
22        // Use Depth-First Search to explore all possible moves
23        dfs(startRow, startCol);
24        return grid; // Return the completed tour grid
25    }
26
27    // Helper method for DFS traversal from a given cell (i, j)
28    private void dfs(int i, int j) {
29        // Check if we've visited all cells, meaning a full tour is complete
30        if (grid[i][j] == rows * cols - 1) {
31            solutionFound = true;
32            return; // Found a solution, so backtrack
33        }
34      
35        // Array of possible moves a knight can make (8 possible moves)
36        int[] moveX = {-2, -1, 1, 2,  2, 1, -1, -2};
37        int[] moveY = {1, 2, 2, 1, -1, -2, -2, -1};
38
39        // Explore all possible moves
40        for (int move = 0; move < 8; ++move) {
41            int nextX = i + moveX[move];
42            int nextY = j + moveY[move];
43
44            // Check if the move is within bounds and the cell is not yet visited
45            if (isValidMove(nextX, nextY)) {
46                grid[nextX][nextY] = grid[i][j] + 1; // Mark the cell with the move number
47                dfs(nextX, nextY); // Continue dfs from the new cell
48              
49                // If a solution is found, no need to explore further; start backtracking
50                if (solutionFound) {
51                    return;
52                }
53              
54                // Backtrack: Unmark the cell as part of the path as it leads to no solution
55                grid[nextX][nextY] = -1;
56            }
57        }
58    }
59
60    // Helper method to check if a move is valid and legal on the chessboard
61    private boolean isValidMove(int x, int y) {
62        return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == -1;
63    }
64}
65
1#include <vector>
2#include <functional> // for std::function
3
4class Solution {
5public:
6    vector<vector<int>> tourOfKnight(int m, int n, int r, int c) {
7        // Initialize a grid to keep track of knight's tour with -1 (unvisited)
8        vector<vector<int>> grid(m, vector<int>(n, -1));
9
10        // Start position for the knight
11        grid[r][c] = 0;
12
13        // Relative movements of a knight on a chessboard
14        // (as pairs of changes in the x and y direction)
15        int directions[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
16                                 {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
17
18        // Flag to indicate if tour is complete
19        bool completed = false;
20      
21        // Recursive function to perform depth-first search (DFS)
22        std::function<void(int, int)> dfs = [&](int x, int y) {
23            // Base case: if we visited last cell, set completed to true
24            if (grid[x][y] == m * n - 1) {
25                completed = true;
26                return;
27            }
28
29            // Try all possible movements for a knight
30            for (int k = 0; k < 8; ++k) {
31                int nextX = x + directions[k][0];
32                int nextY = y + directions[k][1];
33                // Check if the next position is within the board and unvisited
34                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == -1) {
35                    grid[nextX][nextY] = grid[x][y] + 1; // Mark the next position with the move number
36                    dfs(nextX, nextY); // Continue the tour from the next position
37                    if (completed) {
38                        return; // If the tour is complete, we can exit the recursion
39                    }
40                    grid[nextX][nextY] = -1; // Backtrack if move did not lead to solution
41                }
42            }
43        };
44
45        // Start the DFS from the given start position
46        dfs(r, c);
47
48        // Return the completed board or unfinished tour (if solution not found)
49        return grid;
50    }
51};
52
1// This function generates a path for the knight to visit each cell on an m x n board exactly once starting from (r, c).
2// It returns a 2D grid with the steps of the knight marked in each cell.
3// If it's not possible to visit each cell exactly once, -1 is kept in unreachable cells.
4function tourOfKnight(m: number, n: number, r: number, c: number): number[][] {
5    // Initialize the grid with -1 indicating unvisited cells.
6    const grid: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(-1));
7  
8    // Move offsets in terms of row, col for a knight's L-shaped moves.
9    const moves = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
10  
11    // Flag to indicate if a complete tour has been found.
12    let isComplete = false;
13  
14    // Helper function to recursively perform a Depth-First Search (DFS) for the knight's tour.
15    const dfs = (row: number, col: number) => {
16        // If we have filled the last cell, we found a complete tour.
17        if (grid[row][col] === m * n - 1) {
18            isComplete = true;
19            return;
20        }
21      
22        // Try all possible L-shaped moves.
23        for (let i = 0; i < 8; ++i) {
24            const newRow = row + moves[i];
25            const newCol = col + moves[i + 1];
26          
27            // Check if the new move is within bounds and the cell is unvisited.
28            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] === -1) {
29                grid[newRow][newCol] = grid[row][col] + 1; // Mark the step number.
30                dfs(newRow, newCol); // Continue searching from the new cell.
31                if (isComplete) {
32                    return; // If tour is complete, no need to explore further.
33                }
34                grid[newRow][newCol] = -1; // Backtrack: mark the cell as unvisited again.
35            }
36        }
37    };
38  
39    // Start the knight's tour from the given starting cell (r, c).
40    grid[r][c] = 0;
41    dfs(r, c);
42  
43    // Return the grid showing the steps of the knight.
44    return grid;
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m * n * 8^(m * n)).

This is because, in the worst case, the algorithm tries to explore all possible movements of the knight from each cell on the board. In each call to dfs, the knight has up to 8 possible moves to consider. If the board was entirely empty, the knight could theoretically attempt to move from each cell to every other cell, making the full depth-first search (DFS) very costly. Since the termination condition is reaching the cell with a value of m * n - 1, it means that DFS should cover every cell on an m by n board without visiting any cell more than once, which could lead to (m * n)! permutations; however, due to the nature of the knight's movement and the early termination when the end condition is met (ok == True), the actual complexity is reduced but remains exponential.

Space Complexity

The space complexity of the code is O(m * n).

The recursive stack could potentially grow to m * n in the worst case scenario where the path includes all cells. In addition to the recursive stack, a 2D grid g of size m by n is maintained throughout the algorithm to store the steps of the knight's tour. The pairwise function does not significantly affect space complexity, as it just iterates over a constant size tuple. Since these two are the largest space-consuming parts of the algorithm, they also define its overall space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More