Every 5x5 Nonogram (opens in new tab)

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 . . . . .

This puzzle has a unique solution (141a706), but none of the clues immediately tell you anything about the state of any specific cell.

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#

I believe at this point the tactic of "just find a cell that must be black based only on data from its row or column" fails. We can continue only by "using our heads" (i.e. "backtracking"), or by starting to mark cells that must be empty based on data from only their row or column. The cell with the capital X below must be empty because of data in row 3. But the JavaScript didn't auto-mark it with an X. Maybe this is just a logic bug in the JavaScript?:

         2  1
        41131
    1 2 ___#_
    2 1 ##x#x
    1 2 #X_#_
      1 #xxxx
    2 1 _#_x#

And from there we can solve column 2, row 1, row 3, and row 5, in that order.

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.

Under one of the hamburger menus or something, there was an unsolved and it took you right to the next.

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.

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.

https://news.ycombinator.com/item?id=44153840

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?

I believe none of the other 9 million have a unique solution. 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). A good example is a 5x5 puzzle where each row and column clue is "1": there are many possible 5x5 pixel grids that share those set of clues. Let me know if I'm misunderstanding your question.

Someone is working on them.

There are a couple examples linked in another comment[1], so they do exist. The author of the game has stated[2] they excluded about 1/4 of all possible configurations to avoid including puzzles that required too much trial and error. Perhaps symmetry leads to more ambiguity than asymmetry, and therefore more than ~1/4 of symmetrical configurations were excluded?

Your comment made me curious about how often symmetry occurs in the full set of all possible 5x5 configurations. I took a shot at calculating this as an exercise, but I am a bit rusty when it comes to combinatorics...

First consider mirror symmetry via the center column. There are 2^5 configurations of the center column, and for each of those, there are 2^10 configurations of the left two columns. Since we are mirroring the right two columns from the left two, the number of configurations exhibiting mirror symmetry via the center column is 2^5 * 2^10 = 2^15. Rotating these 90 degrees gives us mirror symmetry via the center row, which is another 2^15 configurations. Mirror symmetry via the corner-to-corner axes, which also have 5 squares, is another pair of 2^15 configurations. So now we're at 2^17 configurations for mirror symmetry for the four axes.

Radial symmetry is slightly harder to describe, but it involves similar partitioning. You can partition the 5x5 grid into two 12-square subsets excluding the center square:

    x x x x x
    x x x x x
    x x . o o
    o o o o o
    o o o o o

For any given configuration of the x-subset, you flip and reverse that to get the configuration of the o-subset. There are 2^12 possible configurations of the x-subset. Since there are two possible values of the center square, that gives us 2^13 configurations of two-subset radial symmetry. I believe rotating 90 or 180 degrees simply produces another configuration that has already been accounted for.

There is also four-subset radial symmetry:

    a a a B B
    a a B B B
    D a . c B
    D D D c c
    D D c c c

however, I think these would all be special cases of two-subset radial symmetry. If I pick a random configuration for the a-partition and apply it to the other subsets, it matches a configuration that would appear in the two-subset group:

    a a a B B    X X o B B    X X o o X
    a a B B B    o X B B B    o X X X X
    D a . c B => D X . c B => o X . X o
    D D D c c    D D D c c    X X X X o
    D D c c c    D D c c c    X o o X X

So between mirror symmetry and radial symmetry we have: 2^17 + 2^13 = 139,264. There are a total of 2^25 = 33,554,432 configurations irrespective of symmetry, so that's 17/4096 or roughly 0.415% that are symmetric...a bit more than 1/256.

EDIT: And by some hilarious bit of fate, I just went to go knock out a few puzzles to reset my brain, and the first one I completed[3] exhibits mirror symmetry in one of the diagonal axes. I'm pretty sure this is the first one I've hit in over 1000 solves.

[1]: https://news.ycombinator.com/item?id=44148396

[2]: https://news.ycombinator.com/item?id=44141047

[3]: https://pixelogic.app/every-5x5-nonogram#3328511

EDIT: formatting; add link to symmetric puzzle

Woohoo, thanks! :)

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

If you concatenate all the clues_*.txt files, in order, to a single file, you can search through it to get the number of a pattern using standard tools, e.g.

    $ grep -n $(echo c222c c222c | xxd -ps -r | base64) clues.txt 
    452085:wiLMIiw=

Which is the nonogram at https://pixelogic.app/every-5x5-nonogram#452085.

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.

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!

You can. There's a button to jump to the next unsolved.

Aha!! Yes thanks!

I saw that icon and interpreted it as an export button or something.