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.

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.

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],
2 [-1, -1, -1]]

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

1[[ 0, -1, -1],
2 [-1, -1, -1]]

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

3. 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:

1[[ 0, -1, -1],
2 [-1, -1,  1]]

4. 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).

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

1[[ 0,  2, -1],
2 [-1, -1,  1]]

6. 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:

1[[ 0, -1, -1],
2 [-1, -1,  1]]

7. 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).

8. 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:

1[[ 0, -1, -1],
2 [-1, -1,  1]]

9. 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

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.