I wrote the same BFS twice: once as a quality gate, once as a teacher

My Sokoban game (BoxCat) has a hundred levels, each guaranteed solvable, and each labeled with an official minimum move count that is genuinely minimal. No human verified that — a BFS solver guards it in CI.

Later I built a Sokoban lab on this site, where you can watch BFS solve puzzles. It contains a solver too — the same algorithm — but I rewrote it from scratch in TypeScript.

Two solvers, one algorithm: sounds like an engineering mistake. Only after finishing did I see it clearly — they are two different products, and sharing an algorithm is almost coincidental surface resemblance.

First, how similar they are

The core loops correspond almost line for line. The GDScript version:

# GDScript (Godot) — BFS main loop
var visited := {_key(board.player, board.boxes): true}
var queue := [[board.player, board.boxes, 0, Vector2i.ZERO]]
var head := 0
while head < queue.size():
    if visited.size() > max_states:
        return NO_MOVE            # state budget blown: treated as unsolvable
    var item: Array = queue[head]
    head += 1
    for dir in dirs:
        # skip walls; pushing checks the box's next cell...
        if not visited.has(key):
            visited[key] = true
            queue.append([next, new_boxes, depth + 1, step_first])

The TypeScript skeleton is identical: the same visited set, the same head-pointer sweep instead of shift() (shift is O(n) — a disaster once the queue grows), the same state-budget fuse.

State representation differs — Godot uses Vector2i with a Dictionary as a set, TS uses "x,y" strings with a Set — but that is language idiom, not design.

The real divergence is elsewhere: what they return.

The Godot version returns one move: it is a gate and a hint

The Godot version's full return value is {"steps": minimum, "move": first move of an optimal solution}. That is all — not even the full path.

Because both of its consumers need exactly that and nothing more:

The first consumer is CI. Before any level enters levels.json, the test suite uses the solver to prove two things: the level is solvable (steps ≠ -1), and the par shown to players is the true minimum. Generator candidates that are unsolvable or have inflated pars never reach the repository. A gate needs a verdict, not a journey.

The second consumer is the hint system. A stuck player taps hint; the game feeds the current position to the solver and gets back the optimal next move. Hence the move in the return value — the first move from the root, carried along during expansion, known the instant a solution is found, no path reconstruction needed.

Note what this design implies: hints are not prerecorded. Push the board into any mess you like, and the hint is the optimal next step from that mess. The cost is a fresh BFS per hint tap — milliseconds on phone-sized boards, entirely worth it.

The browser version returns everything: it is a teacher

The TypeScript version's return value:

export interface SolverResult {
  steps: number;
  path: readonly DirectionName[];      // the full solution path
  visited: number;                     // total states explored
  layers: readonly SearchLayer[];      // per depth: state count, player cells
  budgetExceeded: boolean;
}

The full path, the exploration total, and a snapshot of every layer — how many states at each depth, which cells the player might occupy. Useless to a gate; the entirety of teaching. The lab page draws layers one by one, and you watch the BFS ripple spread and the state count swell per depth.

Same algorithm; the return value assigns its identity. Return a boolean and it is a test. Return one move and it is a hint. Return per-layer history and it is a teacher.

The numbers: what state explosion looks like

While writing this I benchmarked the browser version (Node 22, 200 runs averaged per level):

Two things worth seeing.

First: the unsolvable level is fast. "Corner deadlock" exhausted its entire reachable space after only 21 states — once a box is pushed into a corner, nothing further is possible and the state space collapses. BFS needs no special logic to prove unsolvability; walking everything reachable is the proof.

Second: the explosion arrives faster than intuition says. Growing the board from 6×5 to 9×6 with the same two boxes takes the state count from 62 to 6,226 — a hundredfold. This is why both versions carry a max_states fuse (200k in Godot, 400k in the browser): not fear of a wrong algorithm, but fear of someone feeding a big board and freezing the tab. A blown budget reports "unsolvable" — for a gate, conservative and correct: a level that cannot be proven solvable does not ship.

Why not share one implementation

The natural question: extract a shared core with bindings on both sides — is that not better engineering?

I considered it seriously. It is not worth it. GDScript and TypeScript share no runtime; "sharing" means one side crossing a language bridge or transpiling, and maintaining that bridge costs far more than 60 lines of BFS. Moreover the two return interfaces genuinely differ — one wants a move, the other wants layers — so a shared core would still need a wrapper on each side.

When the algorithm is small enough, writing it twice is the honest option. What actually needs guarding is behavioral agreement — the same board must yield the same move count on both sides. Tests guard that: both suites carry the same boards with the same expected values.

Three things to take away

One — a solver's identity is its return value; know the consumer before designing the interface. A gate wants a verdict, a hint wants one move, a teacher wants the journey: one algorithm, three products.

Two — every search program gets a state budget, and the semantics of blowing it deserve thought (my choice: always report unsolvable — conservative, safe).

Three — for small cross-language algorithms, writing twice plus behavioral tests routinely beats extracting a shared core. Sixty lines of BFS does not justify a bridge.