Sudoku Petri-Net Model

This post shows how Sudoku—a constraint satisfaction puzzle—can be modeled as a Petri net and analyzed using ODE simulation. We'll use a 4×4 mini-Sudoku to keep things comprehensible.

The Puzzle

  Initial:            Solution:
+---+---+---+---+    +---+---+---+---+
| 1 |   | . | . |    | 1 | 2 | 4 | 3 |
+---+---+---+---+    +---+---+---+---+
| . | . | 2 | . |    | 3 | 4 | 2 | 1 |
+===+===+===+===+ -> +===+===+===+===+
| . | 3 | . | . |    | 2 | 3 | 1 | 4 |
+---+---+---+---+    +---+---+---+---+
| . | . | . | 4 |    | 4 | 1 | 3 | 2 |
+---+---+---+---+    +---+---+---+---+

Constraints: Each row, column, and 2×2 block
             must contain digits 1-4 exactly once.

Petri Net Structure

The model has three layers: Cells (16 places), History (64 places), and Constraint Collectors (12 transitions feeding into a solved place).

Layer 1: Cell Places

Each cell holds a token when empty. Given cells (with digits 1, 2, 3, 4 pre-filled) have no token.

Layer 2: Digit Transitions & History

For each cell × digit combination, a transition writes the digit:

Transition D2_01:            History place _D2_01:
"Write digit 2 at (0,1)"     "Digit 2 is at (0,1)"

      +------+
P01 --| D2   |---> _D2_01
(1)   | _01  |     (0->1)
      +------+

Firing consumes cell token, creates history token.

Total: 16 cells × 4 digits = 64 digit transitions and 64 history places.

Layer 3: Constraint Collectors

When all 4 digits appear in a row/column/block, a collector fires. The solved place accumulates tokens: 12 tokens = puzzle solved.

How It Works

Step-by-step for cell (0,1):

1. Initial: P01 = 1 (cell empty)

2. Player considers digit 2:
   Transition D2_01 is ENABLED (P01 has token)

3. Firing D2_01:
   • P01: 1 → 0 (cell now filled)
   • _D2_01: 0 → 1 (history records "2 at (0,1)")

4. When Row 0 has all digits placed:
   Row0_Complete fires → solved gets +1 token

ODE Simulation

Converting to ODEs lets us predict outcomes without exhaustive search:

For each candidate move:
  1. Create hypothetical state
  2. Run ODE simulation (t=0 to t=3.0)
  3. Measure token flow to 'solved' place
  4. Higher flow = move more likely leads to solution

Example: Evaluating Cell (0,1)

The model structure encodes all constraints—conflicts appear as zero-flow transitions, valid moves as positive flow.

Scaling to 9×9

The same pattern scales:

Tuning the ODE

A naive ODE simulation of the full 9×9 model (729 transitions!) would be prohibitively slow. We tune for insight, not precision:

Parameter         Default    Tuned      Why
─────────────────────────────────────────────────────
Time horizon      t=10.0     t=3.0      We only need relative rankings
Abstol            1e-6       1e-4       Looser tolerance, faster solve
Reltol            1e-3       1e-3       Already reasonable
Step size (dt)    0.01       0.2        Larger steps, fewer iterations
Max iterations    100000     1000       Early termination OK

The Key Insight

We don't need the ODE to converge to exact token counts. We need it to rank candidates:

Move A: solved flow = 0.31  ← Best
Move B: solved flow = 0.28
Move C: solved flow = 0.15
Move D: blocked (conflict)

Short simulations with loose tolerances still preserve ordering. A move that produces higher flow at t=3.0 will generally produce higher flow at t=10.0.

Performance Impact

This makes interactive analysis feasible—evaluating all candidates for a cell takes seconds, not minutes.

Why This Matters

1. No hardcoded solver — constraints emerge from topology
2. ODE reveals structure — flow patterns show which moves lead to solutions
3. Composable — same pattern works for any constraint satisfaction problem
4. Analyzable — can prove properties about reachability and deadlocks

Try It

cd examples/sudoku
go run ./cmd --size 4x4 --ode --analyze

Data generated with go-pflow

For more on this approach: Declarative Differential Models