Every 5x5 Nonogram
151 points by eieio 1 day ago | 68 comments- okayestjoel 1 day agoThis 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.
- fph 17 minutes agoPossibly 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?
- quuxplusone 1 day agoquesterzen (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 21 hours agoI don't know exactly how okayestjoel's solver works, but here's an example of a nonogram which I imagine it would consider "difficult":
This puzzle has a unique solution (141a706), but none of the clues immediately tell you anything about the state of any specific cell.1 1 1 2 1 1 2 1 2 . . . . . 2 . . . . . 11 . . . . . 2 . . . . . 11 . . . . .- gus_massa 17 hours agoThanks, 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".
- gus_massa 17 hours ago
- quuxplusone 1 day agoHere'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:
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 #__#_ 1 #xxxx 2 1 _#_x#
And from there we can solve column 2, row 1, row 3, and row 5, in that order.2 1 41131 1 2 ___#_ 2 1 ##x#x 1 2 #X_#_ 1 #xxxx 2 1 _#_x#
- duskwuff 21 hours ago
- curtisf 1 day agoWhat 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?
- 1 day ago
- stagger87 1 day agoNot 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 1 day agoYes, 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 1 day agoHot 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.
- vintermann 1 day ago
- 1 day ago
- ryani 12 hours agoI want to be able to click-and-drag. For example, in this row
if I left click the second cell and drag right it should mark all the blank cells black.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.
- questerzen 1 day agoI 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.
- ghusbands 1 day agoThe 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 22 hours agoThat'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.)
- duskwuff 22 hours ago
- ghusbands 1 day ago
- jaachan 1 day agoThis 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 20 hours agoUnder one of the hamburger menus or something, there was an unsolved and it took you right to the next.
- bombcar 20 hours ago
- pimlottc 1 day agoI 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.
- gschizas 1 day agoWhy do some puzzles have a green or red border? What does this signify?
EDIT: or purple border.
- JKCalhoun 21 hours agoSomeone is working on them.
- JKCalhoun 21 hours ago
- gus_massa 1 day agoHow 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 1 day agoI 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 1 day agoYou 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.
- purpleidea 1 day ago> 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.
- gus_massa 1 day ago
- okayestjoel 1 day ago
- ilikepi 1 day agoThis is great! One thing that would be helpful is to be able to drag multiple adjacent tiles...
- simonmysun 1 day agoGood job! So when a section is almost finished, how should I find the last few unsolved nonograms?
- shivbhatia 1 day agoThis is really cool!
- Traubenfuchs 1 day ago...how do I start a game?
- fph 17 minutes ago
- punty 16 hours agoSome 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 15 hours agoHow did you come to build this collection? They're all in different sections...
- punty 7 hours agoI 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!
- punty 7 hours ago
- ilikepi 15 hours ago
- bspammer 1 day agoThis 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.
- mdtrooper 17 hours ago
- tantalor 1 day agoNo but really how do I play. Do I click something to start a puzzle?
- dietr1ch 1 day agoJust scroll down until you find an unsolved puzzle.
I wish you could filter out and just play unsolved ones.
- dietr1ch 1 day ago
- scythe 1 day agoThis 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 1 day agoI went through 102 before i knew it.
- MaysonL 1 day ago
- Waterluvian 20 hours agoIt 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…
- manarth 11 hours agoLove this, but seeing "There was a problem communicating with the server." very often. Bots or HN hug of death?
- Waterluvian 21 hours agoI 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 21 hours agoThere's a button at the top with an arrow ->, which lets you find an unsolved puzzle.
- Waterluvian 21 hours agoAha!! Yes thanks!
I saw that icon and interpreted it as an export button or something.
- Waterluvian 21 hours ago
- treve 21 hours ago
- anxiousbuddhist 1 day agoThis 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 1 day agoWhen a row is completed it vanishes ... Tetris-style.
- JKCalhoun 1 day ago
- NooneAtAll3 1 day agoidk 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
- x-complexity 1 day agoI haven't seen anyone say this out loud, so here's my $0.02:
Since every box is either filled in (1) or not (0), a solved 5x5 nonogram can be encoded as a 25-bit unsigned integer. So would a 6x6 (36), 7x7 (49), 8x8 (64), etc.
... So if desired, an AES-256 key can be encoded as a solved 16x16 nonogram. The perimeter hints can then be derived by Alice and given to Bob as a weak form of information obfuscation.
- butz 1 day agoIn my youth I was considering drawing all possible 8x8 1bit color pixel icons and never got around to it. Probably it is the time to finally do it, and maybe even go further with 2 bit colors?
- FabHK 1 day agoWell, if you do a million per second, it'll take you less than a million years. So, now is as good a time to get started as any.
- FabHK 1 day ago
- fph 1 day agoThere must be a swastika picture in there, somewhere.
- punty 17 hours ago
- punty 17 hours ago
- marssaxman 19 hours agoI knocked out a hundred of these last night - what a fun concept.
- 01HNNWZ0MV43FF 1 day ago
- egoburnswell 21 hours agoSomewhere in there there's a 5x5 swastika
- charcircuit 17 hours agoI suspect it's being botted now. The solve rate when massively up while the user count went down.