Minimum Knight Moves
Fold the board into one quadrant and BFS across a pruned window to the fewest knight moves.
Examples
[0, 0] → [2, 1] is a single knight move.
[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5].
Problem Understanding
A knight starts at (0, 0) on a chessboard with no edges, and moves in the usual L shape: two squares one way and one the other, which is (±1, ±2) or (±2, ±1).
- Goal: the fewest moves that land it on
(x, y)(LeetCode 1197). - Input:
x = 2,y = 1. Output:1— that square is one jump away. - Input:
x = 5,y = 5. Output:4.
Every move costs the same, so this is a shortest-path question on an unweighted graph whose nodes are squares and whose edges are jumps — which is BFS. The one difficulty is that the board is infinite, so the search has to be given an edge of its own.
Algorithm Strategy
BFS out from (0, 0), but on a board cut down to a window first.
- Fold the target. The board is symmetric about both axes, so
(-2, 1),(2, -1)and(2, 1)all cost the same. Replacexandywith their absolute values and only the first quadrant is left. - Bound the search. Two squares past the folded target on each side is enough — no shortest path ever needs to go further out. That is the
-2and thex + 2in the condition, and it is the board the figure draws. - One array, two jobs.
steps[r + 2][c + 2]is-1for a square not yet reached and otherwise the moves that reached it, so it is both the visited set and the answer. The+ 2is what lets the negative margin be stored in an array that starts at 0. - Walk the layers. Dequeue a square; if it is the target, its recorded number is the answer. Otherwise try the eight jumps, discard any that leave the window or that have been reached already, and enqueue the rest one move deeper.
Why the margin is not zero. Reaching (1, 1) takes two moves, and the shortest route leaves the quadrant on the way: (0, 0) → (-1, 2) → (1, 1). A search clamped at 0 would never find it.
Interactive Visualization
The board drawn is the pruned window itself — two squares past the folded target on every side — so the bound the method relies on is the thing you can see. A square shows the moves that reached it, which makes the layers legible: a ring of 1s around the origin, then a ring of 2s. A jump that would leave the window is drawn as a × where it would have landed. Try Needs a dip, where the shortest route to (1, 1) goes through (-1, 2).
Dry Run
Target: (2, 1), which is already in the first quadrant, so the fold changes nothing. The window runs from -2 to 4 down and -2 to 3 across.
| Dequeued | Its moves | The eight jumps from it | Queue after |
|---|---|---|---|
| (0, 0) | 0 | all eight are inside the window and new: (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2) | those eight, in that order |
| (1, 2) | 1 | (2,4) and (0,4) fall outside the window; (0,0) is already recorded; (3,3), (3,1), (2,0), (-1,1) and (-1,3) are new | the rest of layer 1, then those five |
| (2, 1) | 1 | it is the target — return 1 | — |
The answer is found on the second dequeue, before the rest of layer 1 has even been expanded. That is the property BFS is bought for: a square is dequeued only after every square closer to the start.
Edge Cases & Common Mistakes
Edge Cases:
(0, 0): the start is the target, so the first dequeue answers 0.- A target in another quadrant: folded to its absolute values before anything is searched.
(1, 1): 2 moves, by way of(-1, 2)— the case the negative margin exists for.
Common Mistakes:
- Clamping the window at 0. It looks safe, because the target is in the first quadrant, but it breaks
(1, 1). - DFS instead of BFS. On an infinite board a depth-first walk has no reason to ever come back.
- Marking a square visited when it is dequeued. Each square would then be enqueued once per neighbour that reaches it.
- Hashing coordinates into strings.
"3,4"works, but the window is small and bounded, so a plain array with a+ 2offset is both simpler and faster.
Solution Code
Fold the target into one quadrant, then BFS across the pruned window (LeetCode 1197).
Minimum Knight Moves Code
1var minKnightMoves = function(x, y) {2 x = Math.abs(x);3 y = Math.abs(y);4 const moves = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];5 const steps = Array.from({ length: x + 5 }, () => new Array(y + 5).fill(-1));6 steps[2][2] = 0;7 const queue = [[0, 0]];8 let head = 0;9 while (head < queue.length) {10 const [r, c] = queue[head++];11 if (r === x && c === y) {12 return steps[r + 2][c + 2];13 }14 for (const [dr, dc] of moves) {15 const nr = r + dr, nc = c + dc;16 if (nr < -2 || nc < -2 || nr > x + 2 || nc > y + 2 || steps[nr + 2][nc + 2] !== -1) {17 continue;18 }19 steps[nr + 2][nc + 2] = steps[r + 2][c + 2] + 1;20 queue.push([nr, nc]);21 }22 }23 return -1;24};