2596. Check Knight Tour Configuration

MediumDepth-First SearchBreadth-First SearchArrayMatrixSimulation

Problem Description

In this problem, you are given a chessboard of size n x n, where n represents both the height and width of the board. The chessboard is represented by an integer matrix grid, with each integer being unique and ranging from 0 to n * n - 1. The grid shows the order in which a knight has visited each cell on the chessboard, starting from the top-left cell (which should be 0). The knight is supposed to visit every cell exactly once.

The task is to verify if the given grid represents a valid knight's tour. In a knight's tour, the knight starts at the top-left corner and makes moves in an "L" shape pattern: either moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. Every cell must be visited exactly once in the tour. The problem asks you to return true if the grid is a valid tour, or false if it is not.

Flowchart Walkthrough

To analyze LeetCode problem 2596. Check Knight Tour Configuration using the Flowchart, let's proceed step-by-step through the provided decision points:

Is it a graph?

Yes: The knight's jumps on a chessboard can be represented as movements from one vertex to another (nodes are positions, and edges are valid knight moves).

Is it a tree?

No: The problem deals with a tour over a graph that does not necessarily follow a hierarchical structure like a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: The task to check a knight's complete moves does not inherently involve directed acyclic properties.

Is the problem related to shortest paths?

No: The problem does not concern finding the shortest path between nodes but rather validating the comprehensiveness and correctness of a given path.

Does the problem involve connectivity?

Yes: In the context that the tour must visit every node (position on the board) precisely once in a closed path.

Is the graph weighted?

No: Each knight's move is equivalent; no specific weights distinguish one move from another as more or less "costly" or "valuable."

Conclusion: For a connectivity problem on an unweighted graph, employing an exhaustive exploration to ensure every required node is visited exactly once without revisits or omissions fits the context of a Depth-First Search (DFS). Therefore, using DFS is relevant here to validate the correctness of the entire tour path.

In summary, the flowchart recommends utilizing DFS to explore and confirm each potential knight's movement as per the given configuration, ensuring all cells are visited maintaining the knight's move constraints. This approach effectively checks that the configuration represents a valid closed knight’s tour.

Intuition

To approach this solution, you can simulate the knight's path using the given grid and check if each move is valid. Begin by ensuring that the knight starts at the top-left corner, which would be the 0th position in the tour—any other starting position makes the grid invalid immediately.

Next, create an array pos that will store the coordinates (x, y) for each step the knight takes. It is necessary because the grid is a 2D array representing the tour sequence, and you need to derive the actual coordinates visited at each step.

Once you have the coordinates for the entire path the knight took, go through them in pairs and check if the difference between two adjacent coordinates corresponds to a legal knight move. A legal knight move is only valid if the change in x (dx) and change in y (dy) match either (1, 2) or (2, 1). If at any point you find that the move does not match these conditions, the tour is invalid, and you return false.

If all the moves are legal, once you complete the traversal of the path, you return true indicating the grid represents a valid knight's tour.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution begins by creating a list pos that will record the coordinates (i, j) corresponding to each step of the knight's tour, with i being the row index and j being the column index in the grid. The grid holds integers that represent the move sequences, and the pos list will be used to store the actual (x, y) positions for these moves.

Next, a for loop iterates over each cell (i, j) of the grid to fill out the pos list where pos[grid[i][j]] will be the tuple (i, j), effectively mapping the move sequence to coordinates. If the knight did not start at the top-left corner (grid[0][0] should be 0), then the grid is immediately deemed invalid.

After the pos list is populated, another for loop iterates through pos in pairs using the pairwise function. For each pair of adjacent positions (x1, y1) and (x2, y2), we calculate the absolute differences dx as abs(x1 - x2) and dy as abs(y1 - y2). These differences correspond to the movements made by the knight.

We check if the move is a legal knight's move—a move that results in dx being 1 and dy being 2 or vice versa. The ok variable holds a Boolean representing whether the move is valid (dx == 1 and dy == 2) or (dx == 2 and dy == 1).

If at any point, a pair of positions does not form a legal knight's move, the function returns false because this would indicate an invalid knight's tour.

Finally, if all adjacent pairs fulfill the criteria of a knight's valid move, the loop completes without finding any invalid moves, and the function returns true, which signifies that the provided grid corresponds to a valid configuration of the knight's tour.

This approach relies on the idea of transforming the problem into a simpler data structure (pos list) that can be more easily traversed and verified. The pairwise iterator is a pattern that helps in checking the adjacent elements without manually handling index increments, making the code more readable and less error-prone.

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 consider a 5x5 chessboard and a sequence that we need to verify. Let's assume the given grid is as follows:

0  10  17  6  23
15 5   8   11 18
24 1   14  21 7
9  16  3   20 12
4  13  22  19 2

According to our solution approach, we need to first map each move sequence number to its coordinates on the grid.

To create the pos list, we iterate through the grid:

grid[0][0] is 0, so pos[0] becomes (0, 0).
grid[0][1] is 10, so pos[10] becomes (0, 1).
...
grid[4][4] is 2, so pos[2] becomes (4, 4).

Our pos list now represents the sequence in which the knight moves on the chessboard.

Next, we iterate through the pos list to verify if each move is valid.

For the start: pos[0] is (0, 0) and pos[1] is (2, 1). The move from (0, 0) to (2, 1) has differences dx = 2 and dy = 1, which is a legal knight's move.
We then look at pos[1] to pos[2]: moving from (2, 1) to (4, 4). The differences dx = 2 and dy = 3 do not match the legal moves of a knight. Thus, according to our algorithm, we return false.

The pairwise iteration helps us quickly check the moves one after the other:

Current Position = (0, 0), Next Position = (2, 1), Move = Legal
Current Position = (2, 1), Next Position = (4, 4), Move = Illegal, returns false.

We immediately know that the sequence is not a valid knight's tour since the second move is not legal for a knight, so we don't need to check the entire grid.

This example walkthrough effectively illustrates how our algorithm works to verify a knight's tour on the chessboard. By converting move sequences into coordinates and verifying each move one by one, we can efficiently determine the validity of the tour.

Solution Implementation

1from typing import List
2from itertools import pairwise  # Python 3.10 introduced pairwise function in itertools
3
4class Solution:
5    def check_valid_grid(self, grid: List[List[int]]) -> bool:
6        """ Check if the numbers in the grid follow a knight's move pattern
7
8        Args:
9        grid: A 2D list representing a square grid
10
11        Returns:
12        A boolean value indicating whether the grid is valid under the condition
13        that each consecutive number must be a knight's move away from the previous.
14        """
15
16        # Ensure the first element is 0 as required by the problem's conditions
17        if grid[0][0] != 0:
18            return False
19
20        # Get the size of the grid
21        size = len(grid)
22
23        # Initialize a list to hold the positions of the numbers in the grid
24        positions = [None] * (size * size)
25
26        # Populate the positions list with coordinates of numbers from the grid
27        for row_index in range(size):
28            for col_index in range(size):
29                # Note that the numbers have to be decreased by 1 to become 0-indexed positions
30                positions[grid[row_index][col_index] - 1] = (row_index, col_index)
31
32        # Use pairwise from itertools to iterate over consecutive pairs of number positions
33        for (row1, col1), (row2, col2) in pairwise(positions):
34            # Calculate the absolute deltas between the positions
35            delta_row, delta_col = abs(row1 - row2), abs(col1 - col2)
36          
37            # Check for valid knight's move: either 1 by 2 steps or 2 by 1 step
38            is_valid_knight_move = (delta_row == 1 and delta_col == 2) or (delta_row == 2 and delta_col == 1)
39            if not is_valid_knight_move:
40                # If any pair of numbers is not separated by a knight's move, the grid is invalid
41                return False
42
43        # If all pairs of numbers are separated by a knight's move, the grid is valid
44        return True
45

1class Solution {
2    // Function to check if a given grid represents a valid grid for the given conditions
3    public boolean checkValidGrid(int[][] grid) {
4        // Check if the first element is 0 as required
5        if (grid[0][0] != 0) {
6            return false;
7        }
8
9        // Calculate the size of the grid
10        int gridSize = grid.length;
11
12        // Create a position array to store positions of each number in the grid
13        int[][] positions = new int[gridSize * gridSize][2];
14        for (int row = 0; row < gridSize; ++row) {
15            for (int col = 0; col < gridSize; ++col) {
16                // Storing the current number's position
17                positions[grid[row][col]] = new int[] {row, col};
18            }
19        }
20
21        // Loop to check the validity of the grid based on the position of consecutive numbers
22        for (int i = 1; i < gridSize * gridSize; ++i) {
23            // Get the positions of the current and previous numbers
24            int[] previousPosition = positions[i - 1];
25            int[] currentPosition = positions[i];
26
27            // Calculate the distance between the current number and the previous number
28            int dx = Math.abs(previousPosition[0] - currentPosition[0]);
29            int dy = Math.abs(previousPosition[1] - currentPosition[1]);
30
31            // Check if the distance satisfies the condition for a knight's move in chess
32            boolean isValidMove = (dx == 1 && dy == 2) || (dx == 2 && dy == 1);
33            if (!isValidMove) {
34                // If the move is not valid, the grid is not valid
35                return false;
36            }
37        }
38
39        // If all moves are valid, the grid is valid
40        return true;
41    }
42}
43

1#include <vector>
2#include <cmath> // Include <cmath> for abs function
3
4// The Solution class containing a method to check if a grid is valid
5class Solution {
6public:
7    // Method to check if the moves in the grid represent a valid knight's tour
8    bool checkValidGrid(std::vector<std::vector<int>>& grid) {
9        // The start position must be 0, if not return false
10        if (grid[0][0] != 0) {
11            return false;
12        }
13      
14        // Size of the grid
15        int gridSize = grid.size();
16      
17        // Vector to hold the positions of the numbers in the grid
18        std::vector<std::pair<int, int>> numberPositions(gridSize * gridSize);
19      
20        // Populate numberPositions with coordinates of each number in the grid
21        for (int row = 0; row < gridSize; ++row) {
22            for (int col = 0; col < gridSize; ++col) {
23                numberPositions[grid[row][col]] = {row, col};
24            }
25        }
26      
27        // Iterate over the numbers in the grid and check if each move is a valid knight move
28        for (int number = 1; number < gridSize * gridSize; ++number) {
29            // Get the current and previous positions
30            auto [previousX, previousY] = numberPositions[number - 1];
31            auto [currentX, currentY] = numberPositions[number];
32          
33            // Calculate the differences in x and y coordinates
34            int deltaX = std::abs(previousX - currentX);
35            int deltaY = std::abs(previousY - currentY);
36          
37            // Check if the move is a valid knight's move (L shape move)
38            bool isValidKnightMove = (deltaX == 1 && deltaY == 2) || (deltaX == 2 && deltaY == 1);
39          
40            // If the move isn't valid, return false
41            if (!isValidKnightMove) {
42                return false;
43            }
44        }
45      
46        // If all moves are valid, the grid represents a valid knight's tour
47        return true;
48    }
49};
50

1function checkValidGrid(grid: number[][]): boolean {
2    // Ensure the first element is 0 as expected
3    if (grid[0][0] !== 0) {
4        return false;
5    }
6  
7    // Find the size of the grid
8    const gridSize = grid.length;
9
10    // Initialize an array to track the positions of the numbers in the grid
11    const positions = Array.from({ length: gridSize * gridSize }, () => new Array(2).fill(0));
12  
13    // Populate positions array with the coordinates of each number in the grid
14    for (let row = 0; row < gridSize; ++row) {
15        for (let col = 0; col < gridSize; ++col) {
16            positions[grid[row][col]] = [row, col];
17        }
18    }
19  
20    // Validate the positions of all numbers from 1 to n*n - 1
21    for (let i = 1; i < gridSize * gridSize; ++i) {
22        // Get the position of the current and previous number
23        const previousPos = positions[i - 1];
24        const currentPos = positions[i];
25      
26        // Calculate the absolute differences in x and y directions
27        const deltaX = Math.abs(previousPos[0] - currentPos[0]);
28        const deltaY = Math.abs(previousPos[1] - currentPos[1]);
29      
30        // Check for knight-like move (L-shape): 2 by 1 or 1 by 2 steps
31        const isValidMove = (deltaX === 1 && deltaY === 2) || (deltaX === 2 && deltaY === 1);
32      
33        // If the move is not valid, return false
34        if (!isValidMove) {
35            return false;
36        }
37    }
38  
39    // If all positions are valid, return true
40    return true;
41}
42

Time and Space Complexity

The time complexity of the code is O(n^2). This is because the main computations are in the nested for-loops, which iterate over every cell in the given grid. Since the grid is n by n, the iterations run for n^2 times.

The space complexity of the code is O(n^2) as well. This stems from creating a list called pos of size n * n, which is used to store the positions of the integers from the grid in a 1D array. Since the grid stores n^2 elements, and we're converting it to a 1D array, the space taken by pos will also be n^2.

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

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know