AlgoMaster Logo

Minimum Knight Moves

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A knight starts at the origin of an infinite chess board, and we need the shortest path to a target square (x, y). The knight moves like a chess knight: two squares in one direction plus one square perpendicular. From any position it can jump to 8 different squares.

This is a shortest-path question on an unweighted graph: every cell is a node, every valid knight move is an edge of cost 1. BFS solves this directly. It explores all positions reachable in k moves before any position reachable in k+1 moves, so the first time it reaches the target, the distance is minimal. A recursive formulation that reduces (x, y) toward the origin reaches the same answer with less work, which is the second approach.

Key Constraints:

  • The board is infinite, so the search must be bounded. Moving far past the target only increases the distance, so coordinates can be capped a few squares beyond the target.
  • 0 <= |x| + |y| <= 300 → The Manhattan distance is at most 300, so the answer (number of moves) stays small. The bounded region the search touches is at most a few hundred squares on a side.

Approach 1: BFS (Breadth-First Search)

Intuition

Each cell on the chessboard is a node and each knight move is an edge of equal cost. BFS explores all positions reachable in exactly k moves before exploring positions reachable in k+1 moves, so the first time it reaches the target, that distance is the minimum number of moves.

The board is infinite, so the search needs two restrictions. First, symmetry: the knight's move set is symmetric across both axes, so reaching (x, y) takes the same number of moves as reaching (|x|, |y|). Taking absolute values collapses the four quadrants into one and lets us search a single positive quadrant.

Second, a bound on how far the search can wander. The knight never needs to go more than a couple of squares past the target, so coordinates are capped to [-2, max(|x|, |y|) + 4]. The -2 lower bound matters near the origin: reaching a small target like (1, 0) is shortest when the knight steps to a coordinate like (-1, 1) on the way, so the search must allow a small excursion below zero rather than clamping at 0.

Algorithm

  1. Take the absolute values of x and y (exploit symmetry).
  2. Initialize a queue with position (0, 0) at distance 0.
  3. Create a visited set and add (0, 0).
  4. While the queue is not empty:
    • Dequeue the front position (cx, cy) and its distance.
    • If (cx, cy) equals (x, y), return the distance.
    • For each of the 8 knight moves, compute the next position (nx, ny).
    • If (nx, ny) is within bounds and not visited, mark it visited and enqueue it with distance + 1.

Example Walkthrough

1Initialize queue with starting position (0,0)
Front
(0,0)
Rear
1/3

Code

BFS explores every reachable cell in a growing area around the origin, including cells that move away from the target. The next approach cuts that work by searching from both ends at once.

Approach 2: Bidirectional BFS

Intuition

Standard BFS expands outward from the source one level at a time. Bidirectional BFS runs two such expansions at once, one from the source and one from the target, and stops when they meet. Since the number of cells at depth k grows with k, splitting the search depth between two fronts visits fewer cells than one front reaching the full depth.

If the shortest path has length d, a single front reaching depth d touches on the order of b^d cells, where b is the branching factor (up to 8 for knight moves). Two fronts each reaching depth d/2 touch on the order of 2 * b^(d/2) cells, which is smaller for any d beyond a couple of moves.

The implementation always expands whichever frontier currently has fewer cells, keeping the two sides balanced. A cell reached from one side that already appears in the other side's visited map is the meeting point, and the answer is the sum of the two recorded distances.

Algorithm

  1. Take absolute values of x and y.
  2. If (0, 0) is already the target, return 0.
  3. Initialize two sets: frontSource starting from (0, 0) and frontTarget starting from (x, y).
  4. Initialize two distance maps: visitedSource and visitedTarget.
  5. Alternate between expanding the smaller frontier:
    • For each position in the current frontier, try all 8 knight moves.
    • If the new position has been visited by the other side, return the sum of distances.
    • Otherwise, add it to the current side's visited map and next frontier.
  6. Return the sum of distances when the two frontiers meet.

Example Walkthrough

1Initialize: source frontier = {(0,0)}, target frontier = {(5,5)}
(0,0)
1/4

Code

Both BFS approaches explore the board level by level. The next approach works in the opposite direction, reducing the target toward the origin with a recurrence.

Approach 3: DFS with Memoization

Intuition

Instead of expanding the board with BFS, this approach reduces the target recursively. Reaching (x, y) in the minimum number of moves means the last move came from some neighbor, so the answer is 1 plus the minimum over the eight neighbors. Inside the first quadrant with x >= y, the two moves that step toward the origin are the ones from (x-2, y-1) and (x-1, y-2). The other six either increase a coordinate or move along the wrong axis, so they cannot start a shorter path. That gives the recurrence: minMoves(x, y) = 1 + min(minMoves(x-2, y-1), minMoves(x-1, y-2)).

Applying abs() to the recursive arguments keeps the search in the first quadrant even when a coordinate would go negative. Near the origin the shortest path sometimes passes through a cell on the far side of an axis (reaching (1, 0) takes 3 moves, not 1, because no single knight move covers a distance of 1). Reflecting a negative coordinate back to its absolute value reuses the symmetric subproblem and accounts for those extra moves.

The base cases are (0, 0) at 0 moves, (1, 0) at 3 moves, and (1, 1) at 2 moves. These three cannot be derived from the recurrence because their reverse moves loop back among the same small cells, so they are stated directly. Memoization computes each (x, y) pair once.

The if (x < y) return dfs(y, x) line at the top enforces x >= y on every call, which maps (x, y) and (y, x) to the same memo entry and halves the number of distinct states stored.

Algorithm

  1. Take absolute values of x and y. Ensure x >= y for symmetry.
  2. Handle base cases: (0,0) returns 0, (1,0) returns 3, (1,1) returns 2.
  3. Recursively compute 1 + min(dfs(abs(x-2), abs(y-1)), dfs(abs(x-1), abs(y-2))).
  4. Memoize all results to avoid recomputation.

Example Walkthrough

1dfs(5,5): x >= y, not a base case -> recurse: 1 + min(dfs(|3|,|4|), dfs(|4|,|3|))
1/9

Code