2596. Check Knight Tour Configuration
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.
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.
Which of these pictures shows the visit order of a depth-first search?
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.
Which two pointer technique does Quick Sort use?
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:
10 10 17 6 23 215 5 8 11 18 324 1 14 21 7 49 16 3 20 12 54 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
poslist, we iterate through the grid:
grid[0][0]is 0, sopos[0]becomes(0, 0).grid[0][1]is 10, sopos[10]becomes(0, 1).- ...
grid[4][4]is 2, sopos[2]becomes(4, 4).
Our pos list now represents the sequence in which the knight moves on the chessboard.
- Next, we iterate through the
poslist to verify if each move is valid.
- For the start:
pos[0]is(0, 0)andpos[1]is(2, 1). The move from (0, 0) to (2, 1) has differencesdx = 2anddy = 1, which is a legal knight's move. - We then look at
pos[1]topos[2]: moving from(2, 1)to(4, 4). The differencesdx = 2anddy = 3do not match the legal moves of a knight. Thus, according to our algorithm, we returnfalse.
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
451class 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}
431#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};
501function 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}
42Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.