My sequential constraint solver (no backtracking) also found 24,976,511 games it could solve without backtracking or using more than one constraint at a time.
To get an idea of the speed difference between solving sequentially vs solving using backtracking, on my 10 year old MacBook Pro running on a single core, solving all 28,781,820 possible distinct games:
- sequential solver: ~75s to either solve or abandon each problem
- backtracking solver: ~175s (2.3x) to find every solution for every problem
The backtracking solver is unfairly disadvantaged in this comparison as it takes more time to solve the difficult games requiring backtracking and those with multiple solutions - for example the game {1, 1, 1, 1, 1 | 1, 1, 1, 1, 1} has 120 solutions that need to be found, but the sequential solver abandons its attempt after making no progress on its first pass through the constraints.
For the 25,309,575 uniquely determined games only, the gap in performance is a bit narrower:
- sequential solver: ~60s
- backtracking solver: ~120s (2.0x)
The recursive backtracking solver was a far simpler program to write though!
Incidentally, to generate a database of all possible games took ~35s and finding all solutions for all of the games by looking them up took ~20s in total.
To get an idea of the speed difference between solving sequentially vs solving using backtracking, on my 10 year old MacBook Pro running on a single core, solving all 28,781,820 possible distinct games: - sequential solver: ~75s to either solve or abandon each problem - backtracking solver: ~175s (2.3x) to find every solution for every problem
The backtracking solver is unfairly disadvantaged in this comparison as it takes more time to solve the difficult games requiring backtracking and those with multiple solutions - for example the game {1, 1, 1, 1, 1 | 1, 1, 1, 1, 1} has 120 solutions that need to be found, but the sequential solver abandons its attempt after making no progress on its first pass through the constraints.
For the 25,309,575 uniquely determined games only, the gap in performance is a bit narrower: - sequential solver: ~60s - backtracking solver: ~120s (2.0x)
The recursive backtracking solver was a far simpler program to write though!
Incidentally, to generate a database of all possible games took ~35s and finding all solutions for all of the games by looking them up took ~20s in total.