Minimum Knight Moves

medium graph bfs

Problem

On an infinite chessboard, a knight starts at (0, 0) and may move in any of the 8 L-shaped directions. Return the minimum number of moves to reach (x, y).

Inputx = 2, y = 1

Output1

A knight can move directly from (0,0) to (2,1) in one L-shape jump.

from collections import deque

def min_knight_moves(x, y):
    x, y = abs(x), abs(y)
    dirs = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
    seen = {(0, 0)}
    q = deque([(0, 0, 0)])
    while q:
        cx, cy, d = q.popleft()
        if (cx, cy) == (x, y): return d
        for dx, dy in dirs:
            nx, ny = cx + dx, cy + dy
            if (nx, ny) not in seen and nx >= -2 and ny >= -2:
                seen.add((nx, ny))
                q.append((nx, ny, d + 1))

function minKnightMoves(x, y) {
  x = Math.abs(x); y = Math.abs(y);
  const dirs = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]];
  const seen = new Set(["0,0"]);
  const q = [[0, 0, 0]];
  while (q.length) {
    const [cx, cy, d] = q.shift();
    if (cx === x && cy === y) return d;
    for (const [dx, dy] of dirs) {
      const nx = cx + dx, ny = cy + dy, k = nx + "," + ny;
      if (!seen.has(k) && nx >= -2 && ny >= -2) {
        seen.add(k); q.push([nx, ny, d + 1]);
      }
    }
  }
}

class Solution {
    public int minKnightMoves(int x, int y) {
        x = Math.abs(x); y = Math.abs(y);
        int[][] dirs = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
        Set<Long> seen = new HashSet<>();
        seen.add(0L);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0, 0});
        while (!q.isEmpty()) {
            int[] c = q.poll();
            if (c[0] == x && c[1] == y) return c[2];
            for (int[] d : dirs) {
                int nx = c[0] + d[0], ny = c[1] + d[1];
                long key = (long) nx * 10000 + ny;
                if (!seen.contains(key) && nx >= -2 && ny >= -2) {
                    seen.add(key);
                    q.offer(new int[]{nx, ny, c[2] + 1});
                }
            }
        }
        return -1;
    }
}

int minKnightMoves(int x, int y) {
    x = abs(x); y = abs(y);
    int dirs[8][2] = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
    set<pair<int,int>> seen{{0,0}};
    queue<tuple<int,int,int>> q;
    q.push({0, 0, 0});
    while (!q.empty()) {
        auto [cx, cy, d] = q.front(); q.pop();
        if (cx == x && cy == y) return d;
        for (auto& dd : dirs) {
            int nx = cx + dd[0], ny = cy + dd[1];
            if (!seen.count({nx, ny}) && nx >= -2 && ny >= -2) {
                seen.insert({nx, ny});
                q.push({nx, ny, d + 1});
            }
        }
    }
    return -1;
}

Explanation

We want the fewest knight hops from the origin to a target square. Since each hop costs the same, this is a classic shortest-path-by-steps problem, which is exactly what BFS (breadth-first search) solves: it explores all squares one move away, then two moves away, and so on, so the first time we reach the target we know it was via the minimum number of moves.

The first trick is symmetry. A knight on an infinite board behaves the same in all four quadrants, so we flip the target into the positive quadrant with x, y = abs(x), abs(y). That keeps the search small.

From each square we try all 8 L-shaped moves in dirs. We keep a seen set so we never revisit a square, and a queue holding (cx, cy, d) where d is the distance so far. To stop the search from wandering infinitely far in the wrong direction, we only allow squares with nx >= -2 and ny >= -2 (a small cushion past the origin is enough).

Example: for (x, y) = (2, 1), BFS starts at (0,0) with distance 0. One of its 8 moves lands exactly on (2,1), so it returns 1.

Because BFS expands squares in order of distance, the answer it returns is guaranteed to be the smallest possible number of moves.

Time: O(max(|x|,|y|)²) Space: O(max(|x|,|y|)²)