This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1197) before relying on it.

♞ Minimum Knight Moves

An interactive visualization of BFS on a chess board. Watch the wavefront expand as a knight explores all reachable squares level by level, finding the shortest path to any target coordinate.

BFS LeetCode 1197 ↗ Medium

The Problem

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction (an L-shape).

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Interactive Visualization

Target X

Target Y

Preset

Speed:

Chess Board

BFS Level: 0

Visited: 1

Queue: 1

Result: --

♞

Knight

Origin (0,0)

Target

Current level

Visited

Shortest path

Code

fun minKnightMoves(x: Int, y: Int): Int {    val ax = Math.abs(x); val ay = Math.abs(y) // symmetry    val queue = ArrayDeque<Triple<Int, Int, Int>>()    queue.add(Triple(0, 0, 0))    val visited = mutableSetOf(Pair(0, 0))    val moves = arrayOf(        intArrayOf(-2,-1),intArrayOf(-2,1),intArrayOf(-1,-2),intArrayOf(-1,2),        intArrayOf(1,-2),intArrayOf(1,2),intArrayOf(2,-1),intArrayOf(2,1))    while (queue.isNotEmpty()) {        val (cx, cy, steps) = queue.removeFirst()        if (cx == ax && cy == ay)            return steps        for (m in moves) {            val nx = cx + m[0]; val ny = cy + m[1]            if (Pair(nx, ny) !in visited                && nx >= -2 && ny >= -2) {                visited.add(Pair(nx, ny))                queue.add(Triple(nx, ny, steps + 1))            }        }    }    return -1}

def minKnightMoves(x, y):    x, y = abs(x), abs(y)  # symmetry    queue = deque([(0, 0, 0)])    visited = {(0, 0)}    moves = [(-2,-1),(-2,1),(-1,-2),(-1,2),             (1,-2),(1,2),(2,-1),(2,1)]    while queue:        cx, cy, steps = queue.popleft()        if cx == x and cy == y:            return steps        for dx, dy in moves:            nx, ny = cx + dx, cy + dy            if (nx, ny) not in visited \               and nx >= -2 and ny >= -2:                visited.add((nx, ny))                queue.append((nx, ny, steps+1))    return -1

Current Step

Press Step or Play to begin BFS.

How It Works

Key Insight

A knight on an infinite chess board can reach any square. Since every knight move is "cost 1" (unweighted graph), BFS guarantees the shortest path. Each BFS level represents one additional knight move, so the first time we reach the target, we have found the minimum number of moves.

Symmetry Optimization

Because a knight's moves are symmetric in all four quadrants, we can map the target to the first quadrant using x, y = abs(x), abs(y). This reduces the search space dramatically. We allow a small negative buffer (nx >= -2, ny >= -2) because some shortest paths briefly dip into negative coordinates (e.g., reaching (1,1) requires 4 moves, passing through negative territory).

The Algorithm

Initialize a queue with the starting position (0, 0) at step 0, and a visited set containing (0, 0).
Map target to first quadrant: x, y = abs(x), abs(y).
BFS loop: dequeue a position (cx, cy, steps).
— If (cx, cy) equals (x, y), return steps.
— Otherwise, try all 8 L-shaped knight moves. For each valid, unvisited neighbor (nx, ny) with nx >= -2 and ny >= -2, mark visited and enqueue with steps+1.
BFS processes cells level by level. Each level = one more knight move from the origin.

Complexity

Time O(max(|x|, |y|)^2)

Space O(max(|x|, |y|)^2)

The BFS explores an area roughly proportional to the square of the distance to the target. With the symmetry optimization, we only explore the first quadrant (plus a small buffer), which keeps the search manageable. The answer itself is approximately max(|x|, |y|) / 2 moves for large values, but the exact formula depends on the parity and relative values of x and y.