A Knight's Move Log

Medium

A chess knight toured an n × n board: it started in the top-left cell and visited every cell exactly once. The order is recorded in board: board[r][c] = k means cell (r, c) was the k-th cell visited (0-based, the starting cell is 0). A knight moves in an L shape: two cells vertically and one horizontally, or two horizontally and one vertically. Return true if board describes a valid knight's tour, and false otherwise.

Example 1

board=[[0, 3, 6], [5, 8, 1], [2, 7, 4]] → False

Moves 0 → … → 7 are fine, but going from 7 at (2, 1) to 8 at (1, 1) is a single step up, which is not a knight move.

Example 2

board=[[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]] → True

Every two consecutive numbers are a knight's move apart, and the tour starts in the top-left corner.

Example 3

board=[[1, 6, 3], [4, 0, 8], [7, 2, 5]] → False

The top-left corner holds 1 rather than 0, so the tour did not start there.

Constraints

3 ≤ n ≤ 7
board is an n × n square
Every number from 0 to n² − 1 appears in board exactly once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Matrix Simulation

Similar problems

Quarantine for Mould Hard Drain the Landlocked Ponds Medium Land Regions on a Map Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium

Input

board=[[0, 3, 6], [5, 8, 1], [2, 7, 4]]

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 15 tests on the server, hidden ones included.