We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check Knight Tour Configuration

Number: 2662

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

Given an n x n chessboard and a matrix grid where grid[row][col] represents the move number when the knight visited that cell, determine if the configuration represents a valid knight tour. A valid configuration means the knight starts at the top-left cell (i.e., grid[0][0] must be 0), visits each of the n*n cells exactly once, and every consecutive move is a valid knight move.

Key Insights

  • The knight must start at the top-left cell and follow the sequence of moves specified by grid numbers from 0 to n*n - 1.
  • Each consecutive move must follow one of the eight valid knight movements.
  • Building a reverse mapping from move number to grid coordinates simplifies checking consecutive moves.
  • Use simple iterations with constant time check for valid knight moves.

Space and Time Complexity

Time Complexity: O(n^2) where n is the size of the board (since n^2 cells are processed) Space Complexity: O(n^2) for storing the mapping from move number to coordinates

Solution

The solution involves creating a mapping from each move number to its corresponding cell (row, col) from the provided grid. First, we ensure that the starting position (move 0) is at cell (0, 0). Then, for every move i from 0 to n*n - 2, we retrieve the cell for move i and the cell for move i+1. We check if the absolute differences in rows and columns match one of the eight legal knight moves (the valid pattern being 2 and 1 or 1 and 2). If any move is invalid, return false; if all moves are valid, return true.

Code Solutions

# Python solution for Check Knight Tour Configuration

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        # Check if starting point is at the top-left cell
        if grid[0][0] != 0:
            return False
        
        # Create a mapping from move number to its coordinates (row, col)
        move_to_coord = {}
        for row in range(n):
            for col in range(n):
                move_number = grid[row][col]
                move_to_coord[move_number] = (row, col)
        
        # List of valid knight moves (row change, column change)
        knight_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1),
                        (1, 2), (1, -2), (-1, 2), (-1, -2)]
        
        total_moves = n * n
        # Check each consecutive move
        for i in range(total_moves - 1):
            current_row, current_col = move_to_coord[i]
            next_row, next_col = move_to_coord[i+1]
            # Calculate the difference between consecutive moves
            row_diff = next_row - current_row
            col_diff = next_col - current_col
            # Check if the difference corresponds to any valid knight move
            if (row_diff, col_diff) not in knight_moves:
                return False
        return True

# Note: Make sure to include necessary imports and List from typing if using in LeetCode.
← Back to All Questions