Repository navigation
Stepwise 1.2 — Sudoku three ways, recursion call trees
Two things this release: Sudoku gets serious, and recursion gets a module of its own. 73 algorithms total.
Sudoku, three ways
The Backtracking module now solves the same puzzle with three engines, so the metrics tell the story directly:
- Naive backtracking (existing) — first empty cell, digits 1–9, hundreds of steps of trial and error.
- Constraint propagation + MRV — the Norvig-style engine behind sudoku.nirbhay.dev: 9-bit candidate masks, naked/hidden-single cascades on every elimination, and most-constrained-cell guessing when logic stalls. Solves the easy default with zero guesses; open cells show their live candidate count.
- Human techniques — no guessing at all: naked and hidden singles for placements, naked pairs/triples, pointing pairs and X-Wings to prune candidates, with each applied technique named and tallied. Stops honestly when the ladder stalls.
Recursion module
Live call trees, one node per invocation, captions filling in as calls return:
- Naive vs. memoized Fibonacci on the same n — watch 67 calls collapse to 15, with memo hits highlighted; the collapse is dynamic programming.
- Subsets (2ⁿ leaves) and permutations (n! leaves) — the counting identities drawn.
- Tower of Hanoi — 2ⁿ−1 moves with peg state tracked per move.
- Ackermann — nested recursion that outgrows the canvas fast; explosive inputs are refused with an explanation.
All verified in CI: solver outputs cross-checked between engines, call-tree node counts against closed forms, Hanoi move legality simulated, 115 tests.