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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check Knight Tour Configuration

Difficulty: Medium

Problem Description

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.

Key Insights

  • The knight must start its journey at the top-left corner of the board (cell (0,0)).
  • The knight moves in an "L" shape: it can move two squares in one direction and one square perpendicular, resulting in up to 8 possible moves.
  • To validate the configuration, each move must correspond to one of the valid knight moves from the previous position.
  • The grid must be fully traversed without revisiting any cell.

Space and Time Complexity

Time Complexity: O(n^2) - We iterate through the grid cells to validate moves. Space Complexity: O(n^2) - The knight's position for each move is stored in a 2D grid.

Solution

To solve the problem, we will:

  1. Create a list of all possible knight moves.
  2. Iterate through the grid and for each move, check if it corresponds to a valid knight move from the previous position.
  3. If any move is invalid, return false. If all moves are valid up to the last cell, return true.

Code Solutions

def checkKnightTourConfiguration(grid):
    n = len(grid)
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
    
    # Create a position map to quickly find the coordinates of each move
    position = {}
    for row in range(n):
        for col in range(n):
            position[grid[row][col]] = (row, col)
            
    for move in range(1, n * n):
        curr_pos = position[move]
        prev_pos = position[move - 1]
        
        # Check if the current position is a valid knight move from the previous position
        if not any((curr_pos[0] == prev_pos[0] + dx and curr_pos[1] == prev_pos[1] + dy) for dx, dy in moves):
            return False
            
    return True
← Back to All Questions