I calculated that 25,309,575 games have a unique solution. My back-tracking solver correctly finds all answers for all of the 28,781,820 possible distinct games.
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.
I realised the backtracker can stop early as soon as all squares are filled in (doh!). As a result the timings have changed dramatically.
Database generation: 25s;
Sequential solver - all 'solvable' problems or abandon: 52s;
Backtracking solver - all solutions: 19s;
Database Lookup - all solutions: 16s;
Key takeaway is that the backtracker is not only much simpler, its actually much faster (for a computer at least) and almost as fast as looking up the answer in a table.
My definition of a "valid" nonogram is a little different as it excludes puzzles that require branching or back-tracking strategies. I think my use of the term "solvable" led to some confusion, sorry.
That's the number of unique combinations of clues for all 2^25 puzzles. There are 13 possible clues for each row/column (0 1 2 3 4 5 11 12 13 21 22 31 111), but not all 13^10 possible combinations can appear together - for instance, 5 5 5 5 5 / 0 0 0 0 0 is obviously impossible.
(I wrote a program to calculate this by generating all 2^25 puzzles and their clues, then sorting by the clues. I also verified the count of 25,309,575 clues with unique solutions.)
