Solver Comparison
This notebook implements three different backtracking solvers for Suguru puzzles, each with increasing levels of optimization:
BasicSolver
The simplest backtracking solver. It:
- Selects the cell with the fewest possible values (and most neighbors as tiebreaker)
- Tries each possible value in order
- Uses true backtracking (undoes moves when a branch fails)
- No early pruning - explores all branches until they fail
SmartSolver
An optimized version that adds:
- Early pruning: After making a move, checks if any cell has zero possible values
- If an impossible cell is detected, immediately backtracks without exploring further
- Values are tried in sorted order for consistency
- Significantly reduces the search space by avoiding dead-end branches
ConstraintPropSolver
The most advanced solver that adds:
- Constraint propagation: Before backtracking, finds and fills all "forced moves" (cells with only one possible value)
- These forced moves are made automatically and can't be undone (they're logically required)
- After propagation, uses the same smart backtracking as SmartSolver
- Often solves puzzles with minimal or no backtracking needed
- Validates moves during propagation to catch invalid states early
All solvers use true backtracking with a context manager that automatically undoes moves when a branch doesn't lead to a solution.