Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Every 5x5 Nonogram

pixelogic.app

Post reply on HN
Print view View original

71–80 of 89 posts

Re: Every 5x5 Nonogram

#71

Post by fph »

okayestjoel wrote: post #2

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?

Re: Every 5x5 Nonogram

#72

Post by okayestjoel »

duskwuff wrote: post #53
quuxplusone wrote: post #31

Earlier quoted context omitted.

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

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.

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

Re: Every 5x5 Nonogram

#73

Post by okayestjoel »

questerzen wrote: post #27
okayestjoel wrote: post #2

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

Re: Every 5x5 Nonogram

#74

Post by scotty79 »

okayestjoel wrote: post #2

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…

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.

Re: Every 5x5 Nonogram

#75

Post by bspammer »

quuxplusone wrote: post #44
quuxplusone wrote: post #31

Earlier quoted context omitted.

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

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…

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.

Re: Every 5x5 Nonogram

#76

Post by duskwuff »

okayestjoel wrote: post #72
duskwuff wrote: post #53

Earlier quoted context omitted.

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.

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…

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/

Re: Every 5x5 Nonogram

#77

Post by tocs3 »

bspammer wrote: post #26

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.

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

Re: Every 5x5 Nonogram

#78

Post by okayestjoel »

duskwuff wrote: post #76
okayestjoel wrote: post #72

Earlier quoted context omitted.

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…

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/

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

Re: Every 5x5 Nonogram

#80

Post by dietr1ch »

nosrepa wrote: post #79
dietr1ch wrote: post #10

Earlier quoted context omitted.

Just scroll down until you find an unsolved puzzle. I wish you could filter out and just play unsolved ones.

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

It seems it was added afterwards. I also noticed it when playing a few boards later at night.
Post reply on HN