Check Knight Tour Configuration

Medium

Asked by:

36 views

Topics:

Arrays

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once.

You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n * n - 1] where grid[row][col] indicates that the cell (row, col) is the grid[row][col]^th cell that the knight visited. The moves are 0-indexed.

Return true if grid represents a valid configuration of the knight's movements or false otherwise.

Note that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

Example 1:

Input: grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
Output: true
Explanation: The above diagram represents the grid. It can be shown that it is a valid configuration.

Example 2:

Input: grid = [[0,3,6],[5,8,1],[2,7,4]]
Output: false
Explanation: The above diagram represents the grid. The 8^th move of the knight is not valid considering its position after the 7^th move.

Constraints:

n == grid.length == grid[i].length
3 <= n <= 7
0 <= grid[row][col] < n * n
All integers in grid are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the chessboard? Is it always an N x N board?
The input is a sequence of moves, represented as coordinates. Are these coordinates 0-indexed or 1-indexed?
Are the coordinates guaranteed to be within the bounds of the chessboard? What should I return if a coordinate is out of bounds?
If the knight's tour is invalid (doesn't start at (0,0) or contains illegal moves), what should I return? Should I return an error code or a boolean value?
Does the tour need to visit every square on the board exactly once, or is it sufficient for the knight to make a series of valid moves?

Brute Force Solution

Approach

The brute force way to solve this problem is to try every possible path a knight could take on the board. We will check each possibility to see if it matches the given sequence of moves in the desired order. Essentially we are simulating every single possible knight tour.

Here's how the algorithm would work step-by-step:

Begin with the knight at the first position in the sequence.
Explore all possible moves the knight can make from its current position.
For each possible move, check if the new position matches the next position in the given sequence.
If it does, continue exploring possible moves from this new position, looking for the subsequent position in the sequence.
If it doesn't, discard this move and try another.
Repeat this process until either the entire sequence is matched, or there are no more moves to explore from a particular position.
If the entire sequence is matched, then the given sequence is a valid knight's tour configuration.
If all possible move combinations have been exhausted and the entire sequence hasn't been matched, then the given sequence is not a valid knight's tour configuration.

Code Implementation

def check_knight_tour_configuration_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])
    move_sequence_length = rows * cols

    # Possible moves for a knight
    knight_moves = [
        (-2, -1), (-2, 1), (-1, -2), (-1, 2),
        (1, -2), (1, 2), (2, -1), (2, 1)
    ]

    def is_valid_move(row, col):
        return 0 <= row < rows and 0 <= col < cols

    def solve_knight_tour(row, col, move_number):
        # Check if we have completed the tour
        if move_number == move_sequence_length - 1:
            return True

        # Try all possible knight moves
        for move_row, move_col in knight_moves:
            next_row = row + move_row
            next_col = col + move_col

            if is_valid_move(next_row, next_col) and \
               grid[next_row][next_col] == move_number + 1:

                # Check if next move completes tour
                if solve_knight_tour(next_row, next_col, move_number + 1):
                    return True
        return False

    # The tour must start at 0
    if grid[0][0] != 0:
        return False

    # Begin recursion to check all valid tour paths
    return solve_knight_tour(0, 0, 0)

Big(O) Analysis

Time Complexity

O(8^n) – The brute force approach simulates all possible knight tours. At each position, a knight has up to 8 possible moves. We explore each possible move recursively to check if it matches the next position in the sequence. In the worst case, we need to explore almost all possible paths of length n (where n is the length of the tour), leading to a branching factor of up to 8 at each step. Thus, the time complexity is exponential and can be approximated as O(8^n), where n is the number of cells in the board. This is because in the worst case, the algorithm has to explore all the possible move combinations, and at each step (for each cell), the knight has a maximum of 8 possible moves to make.

Space Complexity

O(N) – The brute force approach described simulates all possible knight tours, implicitly using a call stack to track the current path being explored. In the worst case, the algorithm might have to explore a significant number of paths before finding a match or exhausting all possibilities. The depth of the recursion, and thus the size of the call stack, can grow up to N, where N is the length of the given sequence, as each recursive call corresponds to matching a position in the sequence. Therefore, the auxiliary space used by the recursion stack can be proportional to N, leading to O(N) space complexity.

Optimal Solution

Approach

The key idea is to verify that a given sequence of moves on a chessboard is a valid knight's tour. We check if each move is a valid knight's move and if we visit each square exactly once.

Here's how the algorithm would work step-by-step:

Start at the beginning of the provided sequence of moves on the chessboard.
For each step, determine if the move from the current square to the next square is a valid knight's move. A knight's move means moving two steps in one direction (horizontally or vertically) and one step in a perpendicular direction.
Keep track of which squares have already been visited. Ensure that each square is visited only once during the entire sequence of moves. If a square is visited more than once (excluding the starting square), it's not a valid tour.
If any move is not a valid knight's move, or if any square is visited more than once, the configuration is invalid.
If all moves are valid knight's moves and each square is visited exactly once, then the tour is valid.

Code Implementation

def check_knight_tour_configuration(grid):
    rows = len(grid)
    cols = len(grid[0])
    board_size = rows * cols

    if grid[0][0] != 0:
        return False

    visited = [[False] * cols for _ in range(rows)]
    visited[0][0] = True
    current_row = 0
    current_col = 0

    # Iterate through the sequence of moves to check validity.
    for move_number in range(1, board_size):
        next_row = -1
        next_col = -1

        # Find the next move in the sequence.
        for row_index in range(rows):
            for col_index in range(cols):
                if grid[row_index][col_index] == move_number:
                    next_row = row_index
                    next_col = col_index
                    break
            if next_row != -1:
                break

        if next_row == -1:
            return False

        # Check if the move is a valid knight's move.
        row_diff = abs(next_row - current_row)
        col_diff = abs(next_col - current_col)

        if not ((row_diff == 2 and col_diff == 1) or (row_diff == 1 and col_diff == 2)):
            return False

        # Check if the square has already been visited.
        if visited[next_row][next_col]:
            return False

        visited[next_row][next_col] = True
        current_row = next_row
        current_col = next_col

    return True

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through the given sequence of moves, which has a length proportional to n, the number of squares on the chessboard. Inside the loop, for each move, a constant number of operations are performed to validate that it's a knight's move. Additionally, for each move, we also check if the destination square has already been visited, potentially requiring a check across all previously visited squares up to that point, which is proportional to n in the worst case. Thus, the algorithm involves a loop of n iterations, each containing operations that may take up to n steps, which gives a complexity of n * n. Therefore, the time complexity is O(n^2).

Space Complexity

O(N) – The algorithm maintains a record of visited squares to ensure each square is visited only once. This is typically implemented using a boolean matrix or a set. In the worst-case scenario, the knight's tour visits all N squares on the chessboard (where N is the number of squares on the board). Therefore, the space required to store the visited squares grows linearly with the number of squares, resulting in O(N) space complexity. No other significant data structures are used that impact space complexity.

Edge Cases

Case	How to Handle
Null or empty board	Return false immediately as no tour is possible.
Board with dimensions 1x1 or 1x2	Handle these small boards specifically as valid tours might exist or not, based on the starting position.
Knight does not start at position (0, 0)	Check if the first move is from (0,0) to ensure the given configuration starts correctly; return false if not.
Invalid knight moves based on board size	Ensure each move is within the bounds of the board using boundary checks.
Visited positions not consecutive or out of order	Verify that each knight move follows the correct sequence of the tour, using move sequence validation.
Board size exceeding maximum memory allocation	Consider the practical limitations on board size and memory usage, potentially limiting input dimensions based on available resources.
Input board contains duplicate positions	The algorithm needs to guarantee that each position is only visited once.
The knight tour is incomplete and doesn't cover all squares	Verify that the number of moves made in the input configuration is exactly the total number of squares in the board.

Null or empty board

How to Handle:

Return false immediately as no tour is possible.

Board with dimensions 1x1 or 1x2

How to Handle:

Handle these small boards specifically as valid tours might exist or not, based on the starting position.

Knight does not start at position (0, 0)

How to Handle:

Check if the first move is from (0,0) to ensure the given configuration starts correctly; return false if not.

Invalid knight moves based on board size

How to Handle:

Ensure each move is within the bounds of the board using boundary checks.

Visited positions not consecutive or out of order

How to Handle:

Verify that each knight move follows the correct sequence of the tour, using move sequence validation.

Board size exceeding maximum memory allocation

How to Handle:

Consider the practical limitations on board size and memory usage, potentially limiting input dimensions based on available resources.

Input board contains duplicate positions

How to Handle:

The algorithm needs to guarantee that each position is only visited once.

The knight tour is incomplete and doesn't cover all squares

How to Handle:

Verify that the number of moves made in the input configuration is exactly the total number of squares in the board.