Hope everyone had a great week. I’m recovered from Covid and thought it would be fun to return to the topic of puzzle solvability.
P.S.: As I work on Pixelogic for Steam, I realize I need something I have never added to Pixelogic before: background music. If you’re a composer or know someone who is, let me know!
What makes a nonogram puzzle “logically solvable”?
There are 25,309,575 5x5 nonogram puzzles that have a unique solution given their row and column clues. Some combinations of clues can have multiple valid answers. In nonograms, this is a big no-no, since there is no one right answer for a given board. Here is the smallest example with two possible solution states:
So what accounts for the 333,064 5x5 missing nonograms that have a unique solution but are not part of the 24,976,511 puzzles? This is due my more strict definition of logically solvable: the puzzle must have a unique solution given its clues andbe line-solvable, that is, it can be solved by iterating over each row and column in isolation. This ensures that solving the puzzle requires no back-tracking - the technique of employing trial-and-error guesses to test out scenarios for contradictions.
Here is the simplest example of a nonogram with a unique solution that is not line-solvable:
In this puzzle, you cannot solve line-by-line, otherwise you’ll get immediately stuck. Here you’ll need to try out various scenarios of placements in the “2” column to see which one leads to a valid end solution.
If a scenario leads to a contradiction, you’ll need to back-track and try another possible scenario until you find one that leads to no contradictions. In this example, only scenario ‘b’ leads to a valid end-state, so that is the solution.
Even though some back-tacking and trial-and-error are involved, you can probably make the argument that this puzzle is still “logically solvable”, just employing a new set of techniques. But things get hairier the larger the board size and more scenarios that need to be individually tested with increased levels of back-tracking. A computer nonogram solver can easily employe this technique with virtually no limit to the number of tested scenarios or levels of back-tracking needed, though I would argue this would be overly challenging for most human players and would lead to a generally unpleasant puzzle experience.
This is why the vast majority of puzzles you’ll find out there, especially those that are human made and result in an image at the end, are line-solvable and do not require trial-and-error and back-tracking techniques. This is also why my nonogram solver, which is optimized for validating human-created puzzles of large board sizes, also requires puzzles be line-solvable in addition to having a unique solution.
So you can see nonogram solvability is a bit of a grey area, and there are valid arguments to either arrive at the 24,976,511 or 25,309,575 total for the number of valid nonogram puzzles (or even a number in-between if you wanted to allow back-tracking but cap it at a certain amount). Though when optimizing for human play, Pixelogic uses the more strict line-solvable standard.
