May 17, 2024
I’m sure you’ve been wondering why there haven't been any new pages for a while. Martin has been working hard on The Nonogram Project and this morning, it finally passed the most gruesome test we’ve tried, Griddlers.net #260236 Illustrated Book. This is a 44 x 26 monster.
There it is! Griddlers.net #260236 Illustrated Book solved! Click on the image to see it at full size.
Running in fast mode it took 4589.4589911 seconds to solve or about 76 minutes. The app was completely non-responsive for that whole time. After creating the allPositions array for all the row and column solvers, it ate 90 gigabytes of memory. Martin had to order more memory for his machine to have enough to solve this one.
Since we’re coding this in C++, here’s the declaration of that enormous array:
typedef struct solverCell{
unsigned char color; ///< There are lots of times when we don't know a solverCells rowSolver, so we CAN'T get this from the clues.
bool solved; ///< If true, this cell has been solved and therefor we can't touch it.
short clueIndex; ///< If unknown this is negative.
bool isEmpty; ///< If true, we don't HAVE a clueIndex, but we're known to be empty.
vector<vector<solverCell>> allPositions; ///< One row per possible position.
For this puzzle, the largest of them had 84,672,315 rows in it!
We store the puzzles in our own version of XML that looks like:
<! This is Griddlers 260236 Illustrated Book ->
<GameBoard>
<rowClues>
<Clues> <!- The clues are color length color length ->
<! 1 > <clueStrip> 2 3 2 7 2 8 2 3</clueStrip>
<! 2 > <clueStrip> 2 1 2 3 2 3 2 3 2 2 2 3</clueStrip>
<! 3 > <clueStrip> 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 2</clueStrip>
<! 4 > <clueStrip> 2 3 2 1 2 1 2 4 2 1 2 1 2 1 2 1 2 1 2 1 2 2</clueStrip>
<! 5 > <clueStrip> 2 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 2 2 1 2 1</clueStrip>
<! 6 > <clueStrip> 2 1 2 1 2 1 2 1 2 1 2 4 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 7 > <clueStrip> 2 1 2 1 2 1 2 1 2 2 2 3 2 1 2 2 2 2 2 1 2 1 2 1</clueStrip>
<! 8 > <clueStrip> 2 2 2 1 2 1 2 3 2 4 2 1 2 3 2 1 2 1 2 1</clueStrip>
<! 9 > <clueStrip> 2 1 2 1 2 1 2 2 2 5 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 10 > <clueStrip> 2 1 2 1 2 1 2 3 2 7 2 1 2 2 2 1 2 1 2 1 2 1</clueStrip>
<! 11 > <clueStrip> 2 1 2 1 2 1 2 11 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1</clueStrip>
<! 12 > <clueStrip> 2 1 2 1 2 1 2 11 2 1 2 1 2 2 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 13 > <clueStrip> 2 1 2 1 2 1 2 7 2 3 2 1 2 1 2 2 2 1 2 1 2 1 2 1</clueStrip>
<! 14 > <clueStrip> 2 1 2 1 2 1 2 6 2 2 2 1 2 3 2 1 2 1 2 1 2 1</clueStrip>
<! 15 > <clueStrip> 2 2 2 1 2 1 2 5 2 2 2 1 2 2 2 1 2 1 2 1</clueStrip>
<! 16 > <clueStrip> 2 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 17 > <clueStrip> 2 1 2 1 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 18 > <clueStrip> 2 1 2 1 2 1 2 7 2 1 2 8 2 1 2 1 2 1</clueStrip>
<! 19 > <clueStrip> 2 2 2 6 2 2 2 1 2 3 2 5 2 1 2 1</clueStrip>
<! 20 > <clueStrip> 2 1 2 1 2 5 2 3 2 6 2 1 2 2</clueStrip>
<! 21 > <clueStrip> 2 1 2 1 2 8 2 3 2 1 2 4 2 6 2 1 2 1</clueStrip>
<! 22 > <clueStrip> 2 2 2 1 2 1 2 2 2 3 2 3 2 3</clueStrip>
<! 23 > <clueStrip> 2 1 2 1 2 25 2 8 2 1</clueStrip>
<! 24 > <clueStrip> 2 4 2 2 2 5 2 4</clueStrip>
<! 25 > <clueStrip> 2 2</clueStrip>
<! 26 > <clueStrip> 2 2</clueStrip>
</Clues>
</rowClues>
<columnClues>
<Clues>
<! 1 > <clueStrip> 2 3</clueStrip>
<! 2 > <clueStrip> 2 8 2 1</clueStrip>
<! 3 > <clueStrip> 2 8 2 1 2 2</clueStrip>
<! 4 > <clueStrip> 2 5 2 2 2 2 2 1</clueStrip>
<! 5 > <clueStrip> 2 1 2 7 2 1 2 1</clueStrip>
<! 6 > <clueStrip> 2 7 2 1 2 2</clueStrip>
<! 7 > <clueStrip> 2 1 2 10 2 1 2 1</clueStrip>
<! 8 > <clueStrip> 2 9 2 1 2 1 2 1</clueStrip>
<! 9 > <clueStrip> 2 1 2 4 2 1 2 1 2 1</clueStrip>
<! 10 > <clueStrip> 2 1 2 9 2 1 2 1 2 1</clueStrip>
<! 11 > <clueStrip> 2 1 2 2 2 8 2 1 2 1 2 1</clueStrip>
<! 12 > <clueStrip> 2 1 2 1 2 2 2 6 2 1 2 1 2 1 2 1</clueStrip>
<! 13 > <clueStrip> 2 2 2 2 2 7 2 1 2 7</clueStrip>
<! 14 > <clueStrip> 2 1 2 7 2 1 2 6</clueStrip>
<! 15 > <clueStrip> 2 1 2 1 2 9 2 1 2 1 2 1</clueStrip>
<! 16 > <clueStrip> 2 1 2 9 2 1 2 1 2 1 2 1</clueStrip>
<! 17 > <clueStrip> 2 1 2 11 2 1 2 1 2 1</clueStrip>
<! 18 > <clueStrip> 2 1 2 1 2 10 2 1 2 1 2 1</clueStrip>
<! 19 > <clueStrip> 2 2 2 3 2 7 2 1 2 1 2 1</clueStrip>
<! 20 > <clueStrip> 2 1 2 1 2 1 2 1 2 1 2 2</clueStrip>
<! 21 > <clueStrip> 2 1 2 1 2 3</clueStrip>
<! 22 > <clueStrip> 2 22</clueStrip>
<! 23 > <clueStrip> 2 1 2 1 2 3</clueStrip>
<! 24 > <clueStrip> 2 1 2 1 2 1 2 2</clueStrip>
<! 25 > <clueStrip> 2 2 2 1 2 1 2 1</clueStrip>
<! 26 > <clueStrip> 2 1 2 3 2 1 2 1 2 1</clueStrip>
<! 27 > <clueStrip> 2 1 2 2 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 28 > <clueStrip> 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 29 > <clueStrip> 2 1 2 1 2 3 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 30 > <clueStrip> 2 1 2 2 2 9 2 1 2 1 2 1</clueStrip>
<! 31 > <clueStrip> 2 1 2 1 2 3 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 32 > <clueStrip> 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 33 > <clueStrip> 2 1 2 2 2 1 2 1 2 1 2 1 2 1</clueStrip>
<! 34 > <clueStrip> 2 1 2 2 2 1 2 1 2 1</clueStrip>
<! 35 > <clueStrip> 2 1 2 1 2 1 2 1</clueStrip>
<! 36 > <clueStrip> 2 1 2 1 2 1 2 1</clueStrip>
<! 37 > <clueStrip> 2 5 2 1 2 1 2 1</clueStrip>
<! 38 > <clueStrip> 2 1 2 8 2 1 2 1 2 1</clueStrip>
<! 39 > <clueStrip> 2 3 2 7 2 1 2 1</clueStrip>
<! 40 > <clueStrip> 2 1 2 7 2 1 2 1</clueStrip>
<! 41 > <clueStrip> 2 1 2 7 2 1 2 1</clueStrip>
<! 42 > <clueStrip> 2 8 2 1 2 1 2 1</clueStrip>
<! 43 > <clueStrip> 2 7 2 1 2 1 2 1</clueStrip>
<! 44 > <clueStrip> 2 6</clueStrip>
</Clues>
</columnClues>
<BoardSettings>
<NonogramPalette>
<entry>none 0.80000 0.80000 0.80000 1</entry>
<entry>none 1.00000 1.00000 1.00000 1</entry>
<entry>none 0.00000 0.00000 0.00000 1</entry>
</NonogramPalette>
<!-- Note that the typeface must start with a capital letter! -->
<CCFont>
<fontFamily>TimesNewRomanPS</fontFamily>
<typeFace>BoldMT</typeFace>
<fontSize>10.500000</fontSize>
</CCFont>
<gameGridColor><CCColor>0.3 0.3 0.3 1.000000</CCColor></gameGridColor>
</BoardSettings>
</GameBoard>