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

Revised September 21, 2026: corrected budget-exhaustion semantics and added a reproducible same-board comparison. The original Node 22, 200-run timing table is historical and lacks its raw run output here; it does not validate current mobile performance.

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 below is from publication in July 2026:

# 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 exhausted: not accepted by the gate
    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

In July 2026, the Godot version's full return value was {"steps": minimum, "move": first move of an optimal solution}. That was 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.

Hints search the player’s current state rather than replay a fixed answer. Latency depends on the board and device; a state budget does not guarantee millisecond completion.

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 search space can grow rapidly, which makes a budget useful. A browser result with steps: -1 still requires checking budgetExceeded: true means the search stopped without deciding solvability; false means the search exhausted its reachable states without a solution. CI can reject both for release, but only one establishes unsolvability under this solver’s rules.

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 should guard that, with the same boards and expected step counts on both sides. As of November 5, 2026, this is not done yet; see the example below.

Example: the two solvers as they stand today

The code below is as of November 5, 2026. The TS version is src/pages/sokobanSolver.ts in this site's repo. The Godot version is game/scripts/sokoban/SokobanSolver.gd in the BoxCat project. That file is in the kof-forge repo, not in this site's repo.

The snapshot of live BoxCat 1.2.0 already returns status and path (lines 14, 26 and 53). The snapshot is kof-forge commit 7e450f3, added on October 13, 2026. The same repo's July 23, 2026 commit, feb0d7b, has neither field. The snapshot commit says it is unmodified, so git does not show when the change was made. The path is rebuilt from a parents array (lines 48-52). "Not even the full path" above is true only for the version at publication (July 30, 2026).

The CI gate still looks only at step counts. The level test calls solve() with a budget of 400,000. It requires steps above 0 and equal to par (test_levels_solvable.gd, lines 16-19). solve() returns -1 both for an exhausted budget and for no solution (SokobanSolver.gd, lines 7-8), so neither enters the repository.

The Godot version also has a cat-hole rule: a box cannot be pushed into a cat hole (line 42). This site's repo has no test file for sokobanSolver.ts. So the two sides are not yet checked against the same boards.

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 — keep three outcomes: solved, exhausted without a solution, and unresolved because the budget ran out. A release gate may reject unresolved candidates, while the UI should explain why.

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.

One result type, three distinct outcomes

The example uses this site’s solver. The first board is solvable in three moves; a budget of one leaves it unresolved. A separate board traps the box in a non-goal corner and exhausts the search without a solution. The download includes the solver for reproduction; it does not verify every Godot level.

import { parseBoard, solveBoard } from './solver.mjs';
const board = parseBoard({ id: 'budget-demo', name: 'Budget demo', par: 3,
  rows: ['#######', '#@    #', '# $ . #', '#     #', '#######'] });
for (const budget of [1, 400000]) {
  const { steps, budgetExceeded } = solveBoard(board, board.initial, budget);
  console.log({ budget, steps, budgetExceeded });
}
const dead = parseBoard({ id: 'deadlock', name: 'Deadlock', par: -1,
  rows: ['#####', '#$@ #', '# . #', '#####'] });
const result = solveBoard(dead, dead.initial);
console.log({ steps: result.steps, budgetExceeded: result.budgetExceeded });