Live data from Hacker News

Every 5x5 Nonogram

pixelogic.app

81–89 of 89 posts

Re: Every 5x5 Nonogram

#81

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 o…

Love the idea! I do agree with others that have made the case for click and drag support.

I got a bit sidetracked and wrote a userscript implementing this feature. It's a little hacky but works pretty well (at least, until the site changes):

https://gist.github.com/DanielCausebrook/3836be4b5804fabe997...

If anyone would find this useful, you can run this on the site using an extension like Tampermonkey. Obviously be careful when adding userscripts in general.

Re: Every 5x5 Nonogram

#82

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 o…

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.

Re: Every 5x5 Nonogram

#83

Earlier quoted context omitted.

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…

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.

Re: Every 5x5 Nonogram

#84

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 o…

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

The sequential constraint solver fails here even though the deduction required is trivial. The first row can only be 10010 or else the 2 in the second row isn't possible.

A more difficult problem is the following:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|.111.
    0|00000

There are two choices at this point. One option is:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|01111
    0|00000
And we immediately run into a problem with the 3rd row, 1st col which needs to be both 1 and 0.

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

Compared to most sudoku solves, I think this is pretty straightforward (you only need to look ahead one move to one other square). I think this would be fair game to give as a problem.

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.

Re: Every 5x5 Nonogram

#85
post #71

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 o…

Possibly silly question... I played more than 100 puzzles and casually browsed many more, but I couldn't find one with a symmetry axis. Is it just because they are extremely uncommon, or did you exclude them for some reason?

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

Re: Every 5x5 Nonogram

#86
post #66
post #63

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

How did you come to build this collection? They're all in different sections...

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.

Re: Every 5x5 Nonogram

#87
post #18

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 o…

This is great! One thing that would be helpful is to be able to drag multiple adjacent tiles...

Woohoo, thanks! :)

Re: Every 5x5 Nonogram

#88

Earlier quoted context omitted.

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 t…

Now I wonder if there are any 5x5 nonograms which can be proven to require multiple levels of backtracking, i.e. where you have to make at least two guesses before reaching a contradiction, no matter where you put those guesses.

This nonogram should require at least 2 guesses, no matter where you put them:

     1 1 1   
     1 1 1 2 1
   2 . . . . .
   2 . . . . .
  11 . . . . .
  11 . . . . .
   1 . . . . .

Re: Every 5x5 Nonogram

#89

Earlier quoted context omitted.

Now I wonder if there are any 5x5 nonograms which can be proven to require multiple levels of backtracking, i.e. where you have to make at least two guesses before reaching a contradiction, no matter where you put those guesses.

This nonogram should require at least 2 guesses, no matter where you put them: 1 1 1 1 1 1 2 1 2 . . . . . 2 . . . . . 11 . . . . . 11 . . . . . 1 . . . . .

That puzzle has two solutions no?

     1 1 1   
     1 1 1 2 1
   2 x x . . .
   2 . . x x .
  11 x . . x .
  11 . x . . x
   1 . . x . .
and

     1 1 1   
     1 1 1 2 1
   2 x x . . .
   2 . . x x .
  11 . x . x .
  11 x . . . x
   1 . . x . .
(found these with an SMT solver :D)
Post reply on HN