Unlocking the Shortest Knight Path: From BFS to a Closed Form

The problem is one line. Given two squares on a chessboard, find the minimum number of moves a knight needs to travel between them. A3 to B5 is one. A3 to C3 is two. Easy to state, surprisingly fiddly to compute, and — as it turns out — solvable without ever simulating a move.

The obvious approach

Tree exploration. Breadth-first search (BFS — explore the fringe layer by layer, never the depths) from the start square, expanding by the eight legal knight offsets each iteration, returning the move count the moment the destination shows up in the frontier.

const OFFSETS: [number, number][] = [
  [1, 2], [2, 1], [2, -1], [1, -2],
  [-1, -2], [-2, -1], [-2, 1], [-1, 2],
];

function successors([x, y]: [number, number]): [number, number][] {
  return OFFSETS
    .map(([dx, dy]): [number, number] => [x + dx, y + dy])
    .filter(([x, y]) => x >= 0 && x < 8 && y >= 0 && y < 8);
}

function shortestKnightPath(start: string, finish: string): number {
  const startCoord = toCoord(start);
  const finishCoord = toCoord(finish);
  let fringe: [number, number][] = [startCoord];
  const seen = new Set<string>([startCoord.join(",")]);
  let moves = 0;
  while (fringe.length) {
    if (fringe.some(([x, y]) => x === finishCoord[0] && y === finishCoord[1])) {
      return moves;
    }
    const next: [number, number][] = [];
    for (const sq of fringe) {
      for (const s of successors(sq)) {
        const key = s.join(",");
        if (!seen.has(key)) {
          seen.add(key);
          next.push(s);
        }
      }
    }
    fringe = next;
    moves++;
  }
  return -1;
}

This works. The seen set is load-bearing — without it the fringe grows exponentially and LeetCode times you out somewhere around move four. With it, BFS is correct and fast enough to pass.

Job done, in the sense that the tests are green. Not job done, in the sense that nothing about this code feels like it understands the problem. It just walks around until it bumps into the answer. The distance between two squares on a board is a function of their coordinates. Pythagoras can compute the Euclidean distance with arithmetic alone. There ought to be a formula for the knight version too — the only complication is that knights don't move in straight lines, they hop in an irregular L. That irregularity is what I called local chaos: the square immediately next door takes three moves to reach, which is more moves than it takes to reach squares two rows away. Annoying, but bounded.

BFS as a research tool

This is the bit that generalises. I couldn't see the formula by staring at the problem, so I used BFS to generate the data and looked at the data instead.

I dropped a knight in the centre of a 40×40 grid and ran BFS to exhaustion — no early exit, just propagate until the fringe is empty, recording the move count to reach every square. Pasted the matrix into Excel. Conditional-formatted it as a heatmap.

The raw heatmap shows two things at once. The further from the origin, the more moves — obvious. But interleaved through that there's a striping pattern: rows like 7 8 7 8 7 8 8 9 8 9 10 that looks regular until it isn't. The local chaos near the origin distorts the picture and makes the underlying pattern hard to see.

Two transformations cleaned it up. First, I re-ran BFS with the eight squares immediately adjacent to the origin treated as already-seen, and the fringe seeded with all nine central squares as zero-move starting points. This is the no-local-chaos version — what the knight's distance field would look like if the awkward neighbourhood didn't exist. The result is concentric, almost circular contours. Beautiful. Second, I subtracted the second heatmap from the first, giving me a map of just the local chaos — the correction term needed to recover the real answer from the clean version.

That subtraction map is where the formula lives. Outside the chaotic core, it's a regular, repeating pattern. Quadrants are mirror images. Edges and corners each have their own repeating motif. Reflect everything down to the half-plane below the line dy/dx ≤ 0.5 and you're staring at a single triangular region that describes the entire board.

From there it's algebra. The dy/dx ≤ 0.5 half — where the destination is roughly along the long axis of the knight's L — is governed by the Manhattan distance modulo three, because the knight moves three squares per hop and the residue tracks the wasted motion. The other half — steeper than 0.5 — needed more work. I copy-pasted a block of the BFS-generated values into a separate spreadsheet and expressed it as f(x, y). Base row first: 2·floor(n/4) + (n mod 4) captures the 0,1,2,3 / 2,3,4,5 / 4,5,6,7 ladder. Odd y rows are the same ladder shunted right by two, plus one. That offset compresses to n + 2·(y mod 2), then add y mod 2. Done.

Plus three hardcoded exceptions for the local chaos: (dy + dx) === 1 returns 3, dy === 2 && dx === 2 returns 4, and the corner-to-(1,1) case on a finite board adds 2 because the knight can't leave the board to swing back.

The closed form

function shortestKnightPath(start: string, finish: string): number {
  const [sx, sy] = toCoord(start);
  const [fx, fy] = toCoord(finish);
  const dx = Math.abs(fx - sx);
  const dy = Math.abs(fy - sy);
  const [a, b] = dy > dx ? [dy, dx] : [dx, dy]; // a is the long side
  const exceptional =
    (a === 1 && b === 0) ||           // adjacent: actually 3
    (a === 2 && b === 2) ||           // knight's "two-two": actually 4
    (a === 1 && b === 1 && isCorner(sx, sy, fx, fy)); // corner edge case
  const yn = a + 2 * (b % 2);
  const base = 2 * Math.floor(yn / 4) + (yn % 4) + (b % 2);
  return base + Number(exceptional) * 2;
}

Two lines if you compress it. No tree, no fringe, no seen set, no allocation. Works on an infinite board. The exceptional term resolves to a boolean, multiplied by two — every chaos case happens to be exactly two greater than the formula would otherwise give, which is the kind of structural symmetry you only notice once you've tabulated every value and looked.

The methodology is the point

BFS isn't the answer here. BFS is the instrument.

The senior-engineer move on this problem isn't picking BFS over a formula or vice versa. It's recognising that the brute-force solution — the one you can write in five minutes and trust to be correct — is the cheapest way to manufacture the dataset that reveals the formula. Run the slow correct thing exhaustively, dump it into a spreadsheet, stare at it until the structure surfaces, then write the fast version with the slow version as your oracle for correctness testing.

This generalises far beyond knight paths. Any time you've got an answer-producing function that's correct but slow, and you suspect there's a closed form or a heuristic hiding behind the costly path, the procedure is the same. Compute the answer for a representative input space. Visualise it. Apply transformations that strip out noise. Look for symmetry, periodicity, mirroring, modular residues. The pattern is almost always there — what was missing was the lens.

People reach for "brute force is the wrong answer" too quickly. Brute force is rarely the shipping answer, but it's frequently the answer that lets you find the shipping answer. The same code that's too slow to submit is exactly fast enough to run once over the whole input space and hand you the structure on a plate.