Sudoku Solver

Constraint propagation search + compiled transformer verification — 21 clues, 172 guesses, 162 backtracks

Puzzle and solution

Solving process

Two phases: Norvig’s constraint propagation performs the search (guessing values and backtracking when propagation detects contradictions), then the compiled transformer stack machine verifies every placement via constraint checking against heap memory.

▶

Verification opcode frequency

▶

How the machine verifies

Verification protocol

For each of the 60 empty cells, the program writes the solution value to the grid in heap memory, then loads all 20 peer cells (8 row + 8 column + 4 remaining box) and compares each against the placed value. That’s 1,200 I32.LOAD operations and 1,200 EQ comparisons, each executed as a parabolic attention head lookup on the compiled transformer weights. Any conflict would halt with an error code — but none do.

The 7,147-instruction program is generated analytically: Python computes the peer lists for each cell and emits specific PUSH addr, I32.LOAD, PUSH val, EQ, JNZ fail sequences. The transformer doesn’t need to “understand” Sudoku — its compiled weights implement exact memory lookup and comparison.