Minimum Knight Moves on an N-by-N Board

Reported in interviews at Bytedance Citadel McKinsey

Problem statement

A knight starts on a square of an n x n chessboard and wants to reach a target square in the fewest moves. A knight moves in an L-shape: two squares in one orthogonal direction then one square perpendicular, giving eight candidate moves; it may never step off the board. Given the board size n and the start and target coordinates (each a (row, col) pair with 0 <= row, col < n), return the minimum number of moves to reach the target, or -1 if it is unreachable.

Complete:

def minMoves(n: int, start: tuple[int, int], target: tuple[int, int]) -> int:

Constraints:

  • $1 \le n \le 1000$.
  • start and target are valid on-board coordinates.

Examples:

  • n = 8, start = (0, 0), target = (1, 2) -> one L-move reaches the target, so the answer is 1.
  • n = 8, start = (0, 0), target = (0, 0) -> already there, the answer is 0.
  • n = 1, start = (0, 0), target = (0, 0) -> the only square; the answer is 0 (and any other target on a 1 x 1 board is unreachable, -1).
Show hint

When every move costs the same, which graph search guarantees that the first time you reach a square you used the fewest moves?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems