Every 5x5 Nonogram
88 comments
·May 31, 2025okayestjoel
quuxplusone
questerzen (below) is correct: there are 25,309,575 solvable nonograms, not 24,976,511.
This is OEIS sequence A242876 — https://oeis.org/A242876
okayestjoel (below) wrote:
> My nonogram solver goes over every possible configuration for each row and column based on the clues, and either fills in squares that must be filled (all possibilities overlap) or marks squares that must be empty. So if the solver reaches a point where there is ambiguity about what the next move is, then it is deemed not solvable (without guessing).
It would be (mildly) interesting to see an example of one of the 333064 solvable 5x5 nonograms that cannot be solved by okayestjoel's solver's heuristics.
duskwuff
I don't know exactly how okayestjoel's solver works, but here's an example of a nonogram which I imagine it would consider "difficult":
1 1 1
2 1 1 2 1
2 . . . . .
2 . . . . .
11 . . . . .
2 . . . . .
11 . . . . .
gus_massa
Thanks, it's a nasty example.
[spoiler alert]
Naming the coumns ABCDE from left to right, and the rows 12345 from top to bottom. Let's consider B2 near the top left. If B2 full:
Then B1 is empty because B has "only" ones. Then the "two" block in row 1 must make D1 full. Then D2 is also full because D has a "two". Now B2 and D2 are full, but that's impossible because B has only a "two".
So the B2 must be empty. From that point it's possible to fill all the others without "guessing".
So no branches and 3 steps to get a contradiction. I can run that in my head, so I call it "thinking" instead of "backtracking".
okayestjoel
I think you're exactly right. I might be being a little loose with the terminology here. "Well-formed" may be a better term than "solvable" for what I consider a valid puzzle. Even if a computer program can find the solution to one of these difficult puzzles, it would be a very frustrating experience for a human player in most cases. For small 5x5 sizes you could get away with it, though imagine a larger 25x25 puzzle where you have to make one of these branching decisions (a guess) early on. Some may enjoy this challenge, though from my experience of running a nonogram game for 15 years I can tell you most will not.
I'm a little underwater handling the surge of traffic to my game, though when I get a quiet moment I'll run my solver so I can give some more precise answers. Basically my solver iterates over every row and column, marking cells that must be empty and painting cells that must be filled by going over every possible configuration for that row or column and finding the overlap. It does this in multiple passes and generally the more passes it takes, the more challenging the puzzle is. If it makes a pass and is unable to mark or paint any additional cells, then it considers the puzzle to be invalid if the end state is not solved (all clues are not satisfied).
I do find this discussion really interesting. Maybe I should have reserved "Section 666" for these puzzles with unique solution but require a branching strategy :).
quuxplusone
Here's a reverse example: Nonogram #18,950,614 (in section 759) is "21-1-12-21-12+4-21-1-3-11". If we fill in every cell that absolutely must be filled in based only on the data shown in a single row or column (plus the Xs that the JavaScript shows us), we get to this point:
2 1
41131
1 2 ___#_
2 1 ##x#x
1 2 #__#_
1 #xxxx
2 1 _#_x#
2 1
41131
1 2 ___#_
2 1 ##x#x
1 2 #X_#_
1 #xxxx
2 1 _#_x#
bspammer
Isn't that situation covered in the original description? They said that marking squares that must be empty is fair game. The only thing not permitted is forced backtracking.
I don't think it's a bug in the javascript either, it seems intentional that it only fills in the x's automatically if you've filled in the squares for that row/column.
curtisf
What do you mean by "purely with logic, no guessing"?
"Guess and backtrack" is a totally valid form of deduction for pen-and-paper puzzles, it's just not very satisfying. But often (always?) there is a satisfying deduction technique that could have replaced the guess-and-check, it may just be fairly obtuse.
Or do you just mean where the clues for the raster don't result in a unique solution?
null
stagger87
Not OP, but you don't ever have to guess and backtrack, you can always work out the next move. After playing about 100 boards several simple "rules" emerge which allow for this.
vintermann
Yes, 5x5 is small enough that all backtracking can be codified into easily human-accessible rules.
* 5, 0, 1 1 1, 2 2, 3 1 and 3 1 are immediately solved
* 4 lets you set 3 squares immediately
* 3, 2 1 and 1 2 let you set 1 square immediately
jhanschoo
Hot take: Some valid rules are just brute-force search in an altered state space.
For example, a valid "advanced" rule is this: consider a line, then consider all permutations of ways to complete it given the current state of the line. If a square is filled in/crossed out in all these permutations, then it you may fill it in/cross it out.
This is an O(n!) algorithm! In practice you only have <5 permutations.
jaachan
This is fun! But with more progress made, finding a puzzle to solve will become the hardest path.
Maybe a heat map of all sections based on completion percentage? And maybe a way to jump to the first or a random unsolved puzzle once you've opened a section?
bombcar
Under one of the hamburger menus or something, there was an unsolved and it took you right to the next.
questerzen
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.
questerzen
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.
questerzen
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.
okayestjoel
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.
ghusbands
The number of unique 5x5 grids is 33,554,432 (2^25) and the number if you ignore rotation or reflection is 4,211,744. What is 28,781,820?
duskwuff
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.)
questerzen
Here is an example of a case that backtracking is required where there is only one solution:
11110
-----
11|....0
2|....0
0|00000
0|00000
0|00000
A more difficult problem is the following:
11 1
11211
-----
1|..0..
2|..0..
11|.010.
4|.111.
0|00000
11 1
11211
-----
1|..0..
2|..0..
11|.010.
4|01111
0|00000
The other solves the problem immediately as all remaining squares are immediately specified by a single constraint.
11 1
11211
-----
1|00010
2|11000
11|00101
4|11110
0|00000
Of all the games with a unique solution that the sequential solver can't do that I looked at, almost all fell somewhere in the range of difficulty between these two. I didn't find any that require more than one move lookahead.
ryani
I want to be able to click-and-drag. For example, in this row
1 2 |x x |
Similarly in the inverted case, if I have marked cells and right-click-and-drag next to them it should mark the empty spots I cross over with Xs.
Important: this doesn't change the state of any cell that wasn't blank to start out. You should have to click on a marked cell to clear it (or right click to replace it with an X). And similarly to above, if you drag, it should change only the cells you touch that match the starting state of your original cell to the new state.
scotty79
If you start with all possible pixel arrangements, generate numbers from them then all unique sets of number are puzzles uniquely solvable only with logic. Those that were generated from multiple arrangements of pixels have multiple solutions.
Logic has two modes, one is going forward and the other is "assuming conversely" and finding if it leads to contradiction to eliminate that possibility. Both are equally valid and logical. There's no guessing involved. You simply pick any option to eliminate, assume it and try to lead to contradiction. If you don't find the contradiction you don't keep your assumption and the following steps that ended in a state that is not a contradiction, instead you try to eliminate another option instead in the same manner. Only when you successfully eliminate at least one you come back to trying forward logic again. The ultimate trick is not to search the contradiction using only the forward logic, but recursively using the entire solver to find if you landed in a contradiction.
Those two modes are basically the only logic that math uses for bulk of its proofs.
pimlottc
I was surprised that it automatically fills in the blank spaces once you mark all the filled ones, I haven't seen that in other PBN games. As a test, I tried solving one by only marking all the blanks, sadly it didn't fill in the remaining squares for me... :)
One minor UI suggestion: you should allow filling (or marking empty) multiple boxes by holding the mouse button down. This makes it easier to fill in entire rows or columns.
punty
Some fun boards:
The empty board: https://pixelogic.app/every-5x5-nonogram#21035201
The full board: https://pixelogic.app/every-5x5-nonogram#13821100
A greeting board: https://pixelogic.app/every-5x5-nonogram#4282670
A checkerboard: https://pixelogic.app/every-5x5-nonogram#24204839
A board of love: https://pixelogic.app/every-5x5-nonogram#14090887
Question block: https://pixelogic.app/every-5x5-nonogram#18519948
ilikepi
How did you come to build this collection? They're all in different sections...
clues
You can download all the nonogram clues by iterating through https://pixelogic-5x5-puzzles.storage.googleapis.com/clues/c... to https://pixelogic-5x5-puzzles.storage.googleapis.com/clues/c.... Each file has 250 lines (except for the last one which has 11 lines) and each line has five bytes which are base64 encoded.
Each nibble (four bits) in those five bytes is a row or column of the board, top to bottom then left to right, encoded as:
0: 0
1: 1
2: 1 1
3: 1 1 1
4: 1 2
5: 1 3
6: 2
7: 2 1
8: 2 2
9: 3
a: 3 1
b: 4
c: 5
$ grep -n $(echo c222c c222c | xxd -ps -r | base64) clues.txt
452085:wiLMIiw=
I have uploaded and archived a copy of that combined clues.txt file at https://web.archive.org/web/20250604215009id_/https://litter..., to help anyone else who would like to explore this without having to download those tens of thousands of files.
punty
I don't want to ruin the game for the community so will hold off on saying too much. I will say this- this game is very well designed so it's pretty straightforward to understand how it works without using anything more than the network tab of chrome :). No js, frontend puppeteering, etc. are needed. I might write it up when the game is close to completion!
scythe
This is a downright hazard. I scrolled down to find one that wasn't solved yet, and the next thing I knew it was 30 minutes later and I had solved a hundred of them.
MaysonL
I went through 102 before i knew it.
bspammer
This is great, but someone is going to ruin the fun with a bot eventually, I hope you have a way to remove “solves” by IP.
tocs3
The solutions are NP-Completeeate[1]. Someone may write something to solve the 5x5 nongrams (I think there only 33,554,432) but there is always 6x6 nonograms to work with.
[1]https://medium.com/smith-hcv/solving-hard-instances-of-nonog...
tantalor
No but really how do I play. Do I click something to start a puzzle?
fph
There must be a swastika picture in there, somewhere.
anxiousbuddhist
This is a ton of fun!
A really useful feature would be to hide finished and/or in progress ones so I don't have to scroll forever.
Great work, nicely polished, cool idea.
JKCalhoun
When a row is completed it vanishes ... Tetris-style.
NooneAtAll3
idk if it's a bug or smth, but it keeps resetting the page to the top of the section
I can't start solving from the middle
Waterluvian
It seems that this has every 5x5 nonogram. And that none of them require guesswork. Ie. You can derive the answer by following an algorithm without ever having to undo a step.
That means that no 5x5 requires guesswork.
Surely there’s got to be a maths video about this. It seems like an incredible little quirk…
Waterluvian
I love this idea of collectively solving some set of puzzles.
But I don’t understand how I can. The UI design seems broken.
First I couldn’t interact with any puzzles until I realized these were already finished. But how do I get to unfinished ones? I scrolled forever and didn’t find one.
treve
There's a button at the top with an arrow ->, which lets you find an unsolved puzzle.
Waterluvian
Aha!! Yes thanks!
I saw that icon and interpreted it as an export button or something.
This is my game! I was recently curious about how many 5x5 nonograms can be solved purely with logic, no guessing. After running my nonogram solver on all 33,554,432 possible pixel combinations in a 5x5 grid, it turns out the answer is 24,976,511.
Inspired by One Million Checkboxes, I thought it would be cool to create a realtime, collaborative nonogram game where we can collectively try to complete all ~25 million of these puzzles. Just launched it this afternoon and its already at 65k solved!
Let me know if you have any feedback.