Minimum knight moves on a grid

Problem Find the minimum number of knight moves from a start cell to a target cell on an N x N board (standard 8 knight moves; stay on the board).

Input / Output

• Input: N, start (x1,y1), target (x2,y2). Output: minimum move count (-1 if unreachable on tiny boards).

Constraints

• N up to 10^3 → O(N^2) BFS is fine; the infinite-board variant needs pruning/bidirectional BFS — mention if asked.

Example

• N=8, (0,0) → (7,7) → 6 moves; (0,0) → (2,1) → 1.

Expected approach

• Unweighted shortest path → BFS from the start over the 8 move offsets, visited matrix, level count = answer; stop at target. O(N^2)/O(N^2). Why not DFS (finds a path, not the shortest) and why not Dijkstra (unit weights make BFS optimal) are the standard probes. Escalations: bidirectional BFS (meet in the middle) for large/infinite boards, A* with Manhattan/knight-distance heuristic, and symmetry pruning (first quadrant) for the infinite variant.