Minimum Knight Moves

Minimum Knight Moves is the classic "shortest path on an unweighted board" problem. A chess knight jumps in an L, and we want the fewest jumps to reach a target square. The single most important idea here: when every move costs the same, breadth-first search (BFS) finds the shortest path.

The slow way first

You could try to be greedy — always hop "toward" the target. But the knight moves in Ls, so a square that looks closer in straight-line distance can actually be farther in knight moves. Greedy guessing gets the wrong answer.

You could also explore every possible sequence of jumps with plain recursion (DFS), but that re-walks the same squares over and over and explodes exponentially. The question to ask: how do I find a shortest path when every step costs exactly one move?

The idea: spread outward in rings

Treat each square as a node and each legal knight jump as an edge. Every edge has the same cost (one move), so the graph is unweighted — and on an unweighted graph, BFS gives the shortest path for free.

BFS visits squares in order of distance: first everything reachable in 0 moves (just the start), then everything in 1 move, then 2, and so on. The wavefront spreads outward like a ripple. The first time the wavefront touches the target, that distance is the minimum.

The trick that keeps it fast: a seen set. We mark a square the moment we enqueue it, so it never enters the queue twice. That caps total work at one visit per square.

Walk through it

Step through the animation. The start square S lights up first (distance 0). Layer 1 fills the two on-board L-jumps from S. Layer 2 expands those, and one of them — (1,2) — lands a knight jump exactly on the target T = (3,3). The moment we dequeue T, we return its recorded distance: 2.

Pseudocode

queue starts with (start, distance 0)
seen = {start}
while the queue is not empty:
    (square, d) = pop the front of the queue
    if square == target:
        return d                      # first arrival is the shortest
    for each of the 8 knight offsets:
        next = square + offset
        if next is on the board and not in seen:
            add next to seen          # never enqueue a square twice
            push (next, d + 1)
return -1                             # unreachable

The Python solution

def min_knight_moves(start, target):
    OFFSETS = [(1, 2), (2, 1), (-1, 2), (-2, 1),
               (1, -2), (2, -1), (-1, -2), (-2, -1)]
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == target:
            return d
        for dr, dc in OFFSETS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append(((nr, nc), d + 1))
    return -1

• OFFSETS lists the 8 L-shaped knight moves once, so we can apply them in a loop.
• q is a FIFO queue of (square, distance) pairs; popping from the front (popleft) is what makes this breadth-first rather than depth-first.
• seen records every square we have ever enqueued so we never revisit one — this keeps each square to a single visit.
• The check (r, c) == target happens when we pop, and because BFS pops in distance order, the first match is guaranteed minimal.
• We only enqueue a neighbor when it is on the board and not in seen, recording its distance as d + 1.

Complexity

On an N x N board there are N^2 squares, and BFS visits each at most once with a constant 8 neighbors, so it runs in O(N^2) time and uses O(N^2) space for the queue and seen set. That "every move costs one, so use BFS" trade is one of the most reusable patterns in interviews.

When this pattern shows up

Practice