Minimum Knight Moves on an N-by-N Board
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$.
startandtargetare valid on-board coordinates.
Examples:
n = 8,start = (0, 0),target = (1, 2)-> one L-move reaches the target, so the answer is1.n = 8,start = (0, 0),target = (0, 0)-> already there, the answer is0.n = 1,start = (0, 0),target = (0, 0)-> the only square; the answer is0(and any other target on a1 x 1board 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.