Knight Tour Configuration in Python

C++ Solution
Java Solution

Problem Description

Welcome to the whimsical world of chess, where knights gallop around the board like they own the place! The problem at hand is to determine if a knight can traverse a given grid in a valid tour configuration. Imagine a knight trying to impress its fellow chess pieces by visiting every square exactly once. Sounds easy, right? Well, it’s not as simple as it seems!

Picture this: you’re at a party, and you want to greet every guest without repeating anyone. But what if some guests are standing in corners, and you can only reach them by hopping over other guests? That’s the knight’s life! The knight can only move in an “L” shape: two squares in one direction and then one square perpendicular. So, if you think you can just stroll around the board, think again!

Code Solution


class Solution:
    def checkValidGrid(self, grid: list[list[int]]) -> bool:
        if grid[0][0] != 0:
            return False

        dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
                (-1, -2), (-2, -1), (-2, 1), (-1, 2))
        n = len(grid)
        i = 0
        j = 0

        def nextGrid(i: int, j: int, target: int) -> tuple[int, int]:
            """
            Returns (x, y), where grid[x][y] == target if (i, j) can reach target.
            """
            for dx, dy in dirs:
                x = i + dx
                y = j + dy
                if x < 0 or x >= n or y < 0 or y >= n:
                    continue
                if grid[x][y] == target:
                    return (x, y)
            return (-1, -1)

        for target in range(1, n * n):
            x, y = nextGrid(i, j, target)
            if x == -1 and y == -1:
                return False
            i = x
            j = y

        return True

Approach Explanation

The code starts by checking if the knight is at the starting position (0,0). If not, it immediately returns False. It then defines the possible knight moves in a tuple called dirs. The function nextGrid is responsible for finding the next position of the knight based on the current position and the target number. It iterates through all possible knight moves and checks if the target can be reached. If it can, it returns the new coordinates; otherwise, it returns (-1, -1).

The main loop runs through all target numbers from 1 to n*n, checking if the knight can reach each target in sequence. If it can’t reach a target, it returns False. If it successfully visits all squares, it returns True.

Time and Space Complexity

Time Complexity: O(n2), where n is the size of the grid. The algorithm checks each position in the grid for possible knight moves.

Space Complexity: O(1), as we are using a constant amount of space for variables and not utilizing any additional data structures that grow with input size.

Real-World Example

Imagine a knight at a chess tournament trying to impress the judges by performing a flawless tour of the chessboard. The knight must navigate through the board, avoiding any squares it has already visited, just like a contestant trying to impress the judges without repeating their performance. If the knight can successfully visit every square without stepping on the same one twice, it wins the admiration of the audience (and maybe a trophy)!

Similar Problems