The Algorithm That Knows When to Walk Away

There’s a moment when you’re working a puzzle box — fingers pressing, sliding, tilting — and you realize you’ve gone wrong somewhere. Not because anything broke, but because nothing moves anymore. The box has become a wall. So you undo. You retreat. You try the other branch.

Backtracking formalizes this feeling into an algorithm. It emerged in the early 1960s, though the name came later — the technique showed up in Lehmer’s work on permutations and became foundational for constraint satisfaction problems. The idea is devastatingly simple: explore a path, and if it leads nowhere, back up to the last decision point and try something else.

function isValid(state: number[]): boolean {
  return state.join(",") === "1,1,2";
}

function canContinue(_state: number[], _pos: number): boolean {
  return true;
}

function solve(state: number[], pos: number): boolean {
  if (pos === state.length) return isValid(state);
  for (const move of [0, 1, 2]) {
    state[pos] = move;
    if (canContinue(state, pos) && solve(state, pos + 1)) return true;
  }
  state[pos] = -1; // undo
  return false;
}

The TypeScript version reads like imperative sculpture — you mutate, you check, you recurse, you clean up after yourself. OCaml prefers immutability; instead of undoing, you simply don’t carry the bad choice forward:

let is_valid state =
  Array.to_list state = [1; 1; 2]

let can_continue _state _pos =
  true

let rec solve state pos =
  if pos = Array.length state then is_valid state
  else List.exists (fun move ->
    let next = Array.copy state in
    next.(pos) <- move;
    can_continue next pos && solve next (pos + 1)
  ) [0; 1; 2]

The OCaml version allocates more but reasons more clearly — each recursive call gets its own copy of reality. Neither is wrong. They’re different trade-offs for the same structural insight: that exploration and retreat can be systematized.

Designing a puzzle box mechanism is backtracking made physical. You’re encoding a search tree into wood or PLA — some paths proceed, others dead-end. The solver must explore, remember, and retreat. A good puzzle box is a backtracking algorithm you can hold in your hands, one that punishes greedy strategies and rewards patient, methodical reversal.

Sample output from running the solver on a simple 3-slot constraint puzzle:

Trying [0,_,_]... dead end at slot 2
Trying [1,_,_]...
  Trying [1,0,_]... dead end
  Trying [1,1,_]... success: [1,1,2]

That hesitation in the middle — trying, failing, trying again — is the soul of the algorithm. And if you’ve ever watched someone work a puzzle box, it’s the soul of that too.