Check Knight Tour Configuration - Practice Coding Problems

Check Knight Tour Configuration - Problem

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: A valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically.

Input & Output

Example 1 — Valid Knight Tour

$ 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

💡 Note: The knight starts at (0,0) with move 0, then follows valid knight moves through all positions: 0→1→2→3...→24, visiting each cell exactly once.

Example 2 — Invalid Knight Tour

$ Input: grid = [[0,3,6],[5,8,1],[2,7,4]]

› Output: false

💡 Note: The knight starts at (0,0) with move 0, but move 1 is at position (2,1). A knight cannot move from (0,0) to (2,1) in one valid L-shaped move.

Example 3 — Wrong Starting Position

$ Input: grid = [[1,0],[2,3]]

› Output: false

💡 Note: Move 0 should start at top-left (0,0), but here it's at (0,1). Invalid tour configuration.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with move numbers 0 to n²-1

Map Positions

Create move number → position mapping

Validate Moves

Check each consecutive pair forms valid knight move

Key Takeaway

🎯 Key Insight: Map move numbers to positions, then validate each consecutive move follows the knight's L-shaped movement pattern

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to map each move number to its position coordinates, then validate that consecutive moves follow valid knight movement patterns. The optimal approach uses a hash map for O(1) position lookup, achieving O(n²) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Validation	O(n⁴)	O(1)	Check each consecutive move by searching through the entire grid
Position Mapping Optimization	O(n²)	O(n²)	Create a position lookup map first, then validate moves in one pass

Brute Force Validation — Algorithm Steps

Step 1: Start with move 0 (must be at top-left)
Step 2: For each move, search grid to find its position
Step 3: Find next move's position and validate knight move

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Move 0

Search entire grid to find position of move 0

Find Move 1

Search entire grid to find position of move 1

Validate

Check if move from position 0 to position 1 is valid knight move

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

bool solution(int** grid, int n) {
    // Knight moves: 8 possible directions
    int knightMoves[8][2] = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};
    
    // Check if position (0,0) has move 0
    if (grid[0][0] != 0) {
        return false;
    }
    
    // For each move from 0 to n*n-2, check if next move is valid
    for (int move = 0; move < n * n - 1; move++) {
        // Find position of current move
        int currRow = -1, currCol = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == move) {
                    currRow = i;
                    currCol = j;
                    break;
                }
            }
            if (currRow != -1) break;
        }
        
        // Find position of next move
        int nextRow = -1, nextCol = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == move + 1) {
                    nextRow = i;
                    nextCol = j;
                    break;
                }
            }
            if (nextRow != -1) break;
        }
        
        // Check if it's a valid knight move
        bool validMove = false;
        for (int k = 0; k < 8; k++) {
            if (currRow + knightMoves[k][0] == nextRow && currCol + knightMoves[k][1] == nextCol) {
                validMove = true;
                break;
            }
        }
        
        if (!validMove) {
            return false;
        }
    }
    
    return true;
}

int main() {
    // Simple parsing for demonstration - assumes small input
    int n = 3; // Example size
    int** grid = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = malloc(n * sizeof(int));
    }
    
    // Read input (simplified)
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse grid (basic implementation)
    // For actual implementation, would need proper JSON parsing
    
    bool result = solution(grid, n);
    printf(result ? "true\n" : "false\n");
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

For each of n² moves, we search the n×n grid to find positions

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler