Solving...

Sudoku Solver

Generate Puzzle

Statistics

Time
-
Iterations
-
Backtracks
-
Propagations
-

Hybrid WFC-CSP Solver

This solver combines Wave Function Collapse (WFC) concepts with Constraint Satisfaction Problem (CSP) techniques. It is NOT simple backtracking - it uses domain-based state, queue-driven propagation, and entropy-guided decisions.

Key Concepts

Domains - Each cell stores a set of possible values {1-9}, not just one number. When a cell has only one possibility left, it "collapses" to that value.

Entropy - The number of possibilities a cell has. Lower entropy = more constrained. We always pick the lowest entropy cell first (fail-fast strategy).

Propagation - When a cell collapses, we remove that value from all its peers (same row, column, and 3x3 box). This may cause chain reactions of further collapses.

Algorithm Steps

  1. Initialize Domains - Fixed cells get domain {value}. Empty cells get {1-9}, then immediately pruned by existing constraints.
  2. Propagate - Use a queue to process collapsed cells. For each, remove its value from all 20 peers. New collapses join the queue.
  3. Check State - If all domains have size 1, solved! If any domain is empty, contradiction detected.
  4. Speculate - If stuck, snapshot the entire state. Pick min-entropy cell, try one value, propagate. If contradiction, restore snapshot and try next value.
  5. Repeat - Continue until solved or all possibilities exhausted.

Why This Approach?

Deterministic First - Many cells solve themselves through propagation alone, no guessing needed.

Minimal Speculation - We only guess when forced, and pick the cell with fewest options to minimize wrong guesses.

Explicit State - Snapshots are stored on a stack, not hidden in recursion. This makes backtracking transparent and bounded.

Statistics Explained

Iterations = Main loop cycles checking puzzle state
Backtracks = Times speculation failed and state was restored
Propagations = Constraint propagation steps (values removed from peer domains)