[okayestjoel]

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.

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

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

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

[duskwuff]

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.

[SkiFire13]

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

[barbarr]

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)

[qbane]

If you assume that a cell is full and then get a contradiction, this is pretty much a backtracking to a computer. So it is reasonable that the solver does not do this trick.

[gus_massa]

I agree they are the same. It's just that if the try is short enough, I consider it a valid trick.

[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 :).

[duskwuff]

Out of curiosity, are you familiar with Simon Tatham's Portable Puzzle Collection [1]? It includes a nonogram puzzle, under the name "Pattern" - I believe it guarantees that the puzzles are solveable without backtracking. It can generate puzzles up to 40x40 or so in a reasonable amount of time.

[1]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

[okayestjoel]

Yes, I am familiar! I didn't play his games growing up, but I see it as a great reference for various logic puzzle game implementations and one of the few examples of quality logic puzzle collections.

I think one thing missing from my 5x5 puzzle thing is that good nonograms are not just those that have a unique solution and require no guessing, but also create a compelling image when the puzzle is complete. My game, Pixelogic, features user-submitted puzzles in addition to in-house ones, and I'm often blown away how creative the pixel art creations are given the constraints of solvability under my game's standards and just on and off pixels.

I wrote about what makes a good nonogram puzzle (in my opinion) in my weekly nonogram newsletter, if anyone is interested: https://weekly.pixelogic.app/p/pixelogic-weekly-4

[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#

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.

[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?

[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

[jobigoud]

In summary the only ones that don't let you put a square immediately are "0", "1", "2" and "1, 1". And as soon as you put a square you can put some crosses (right click). In the end it becomes fairly mechanic.

[Ancapistani]

100 puzzles in, and I've not had the need for a manually-placed cross, either.

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

[curtisf]

If I recall correctly, it's actually possible to implement this in O(n) (or maybe O(n^2)) time and space using a "dynamic programming" algorithm.

But in general, Nonogram solving, like most pen-and-paper puzzles, is NP-Complete for large enough puzzles, so even such a high-powered rule isn't guaranteed to completely solve a (large) puzzle.

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

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

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

[ghusbands]

That's great, thanks. I've also independently verified the 25,309,575 using similar techniques.

[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

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.

[ryani]

I want to be able to click-and-drag. For example, in this row

    1 2 |x x  |

if I left click the second cell and drag right it should mark all the blank cells black.

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.

[gus_massa]

How many of the other 9 millions have a unique solution? I played minesweeper and sometime you can think a while and deduce a square that is not obvious.

[okayestjoel]

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.

[gus_massa]

You can try to codify for example https://pixelogic.app/every-5x5-nonogram#10725003 as "11-31-1-12-0+11-3-1-11-11" (is there an standard in the community?) and add the 9 million "unsolvable" codified strings to a vector and sort the vector, and then look for not repeated consecutive. For example, your case "1-1-1-1-1+1-1-1-1-1" should appear exactly 120 consecutive times in the sorted 9 million vector. Is there one that is not repeated?

Feature request: It would be nice to have a jump to unsolved puzzle. In section 1 it's difficult to find an empty one. Also, there is something weird with scrolling.

[okayestjoel]

In my mind, a well-formed nonogram is one that requires no backtracking. It's an interesting question though. I'll write some code in the next few days to check to see if my set of "unsolvable" puzzles include those with unique solutions given the clues.

Yeah, a "jump to unsolved" seems like its going to be essential. I'll work on that. I haven't heard of the scrolling issue. What device/browser are you using?

[quuxplusone]

On Android Chrome, "flinging" the scroll really far really fast sometimes keeps scrolling long beyond when I would have expected it to stop. But the page is so gigantic that that might just be the expected behavior.

FYI, I've also noticed that on Android (but not on desktop Chrome) sometimes single-tapping to remove a black square will leave a stray X behind. I think this is not a logic bug but rather a mobile input-recognition problem — that on mobile a single-tap is sometimes being recognized as a single-tap followed by a double-tap. (Quickly double-tapping an empty cell usually marks it with an X; although quickly double-tapping a filled cell usually just clears it, no X. So the symptom here is "I meant to single-tap a filled cell, but the game acted as if I'd single-tapped and then double-tapped the same cell again.")

[gus_massa]

> Scrolling

Chrome on Windows 10, nothing fancy. I move pick the scroll bar on the right with the mouse and move slowly down, perhaps to the middle and try to find a empty range, and when I release mouse it goes back near the top. As a guess: Have you tire to scroll at the ame time that other player is solving puzles in the same section? Try section 1.

> requires no backtracking

I have more background in Math Olympiads and plain Math. You can do backtracking to find a unique solution if you write all the options and discard all-1 of them. It sounds fancier if you call it "Reductio ad absurdum" :) . It's an usual trick, and my recommendation is that if you are in the middle of a problem that ask to fill a board and you have two(or more) options, first copy the board as many times as necessary and intermediately fill the two(or more) possibilities, to avoid forgetting one of them.

For games like minesweeper, sudoku or nonogram, my personal criteria is that if I can run the backtracking in my head, it's "thinking", but if I have to draw the two(or more) boards it's "backtracking".

For me it's probably only two options in a square, no further branching and only two or three steps deep before the contradiction. (If your name is Magnus, everything is "thinking".)

(By the way: Nice game implementation!)

[jsmith45]

Yeah, while large portions of the online logic puzzle communities tend to agree that puzzles should not require backtracking (after all one can often trivialize the intended logical solve path like that), it has proven difficult to define what should count as backtracking vs a simple obvious contradiction that should count as a logical step.

Ability to visualize it in your head, without needing to copy the board, or make temporary marks is certainly not unreasonable for complicated puzzles. That is the same rule as Simon uses for logic puzzles (mostly variant sudoku) on the YouTube channel Cracking the Cryptic.

It isn't the most satisfying way to delineate the dividing line, since how much a person can track in their head can vary, but coming up with other rules can be absurdly tricky. Especially if one wants to make a set of rules applicable to multiple types of logic puzzles. After all simple two to three step contradictions may be unusually powerful for some types of logic puzzles, while they can be the basic deduction type for a different one.

[gus_massa]

*intermediately -> immediately

[ghusbands]

It's common to assume that your solver encodes all the techniques that a human might reasonably use (without backtracking) but it's rarely the case. Someone could look at the clues in two columns and two rows at the same time, for example, and work out whether they together constrain something. (It's easier to see cases in minesweeper where quite long-range deductions can be made, especially when you're down to the last few mines.)

Look elsewhere in the thread and you'll see that there are 333,064 uniquely-solution grids that you have excluded.

[purpleidea]

> there is ambiguity about what the next move is

It's common to have situations where you need to guess between two possibilities, and then you'll find out that one is wrong and you need to backtrack.

So I hope the algo you implement only excludes puzzles with more than one solution. As long as there is exactly one solution, it's completely logical and fair game.

[MrJohz]

This is a philosophical point about what's considered solveable. For example, in the sudoku community, there's this idea of bifurcation, which is when you get to a point in a puzzle where there are two options to take, and you step through each option manually until you figure out which one is correct, and backtrack if necessary.

You can do an entire puzzle this way (just keep on trying options and seeing if they work), but this is generally not on. If you build a puzzle that can only be solved this way, then you've built a bad puzzle, at least by the standards of the sudoku solving community. On the other hand, most complex or variant sudoku puzzles will have moments where there are two or three possibilities for a cell, and you need to look at the immediate effects of those possibilities to figure out which one is correct. So clearly some amount of bifurcation and backtracking is fine.

Fwiw, in the nonograms I've done in various apps, there's almost never a need to guess between different possibilities. I don't know if that's because the puzzle format itself is fairly constrained, or if the apps typically try to exclude these cases. But typically, it's always possible to see a next step, without needing to try things out and guess.

[dietr1ch]

I really don't like the wording about multiple solutions not being logical. I get that instances where resolution doesn't lead you to the unique solution are annoying and don't scratch the right part of your brain, but I feel this audience could be more precise.

Here's a simple Nonogram to annoy everyone

# 1 1

1 . .

1 . .

[gschizas]

Why do some puzzles have a green or red border? What does this signify?

EDIT: or purple border.

[JKCalhoun]

Someone is working on them.

[fph]

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?

[ilikepi]

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

[ilikepi]

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

[ilikepi]

Woohoo, thanks! :)

[simonmysun]

Good job! So when a section is almost finished, how should I find the last few unsolved nonograms?

[tauneutrin0]

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.

[shivbhatia]

This is really cool!

[Traubenfuchs]

...how do I start a game?