[HN Gopher] Every 5x5 Nonogram
___________________________________________________________________
Every 5x5 Nonogram
Author : eieio
Score : 114 points
Date : 2025-05-31 00:14 UTC (22 hours ago)
(HTM) web link (pixelogic.app)
(TXT) w3m dump (pixelogic.app)
| okayestjoel wrote:
| 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.
| gus_massa wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > _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!)
| gus_massa wrote:
| *intermediately -> immediately
| jsmith45 wrote:
| 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.
| ghusbands wrote:
| 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 wrote:
| > 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.
| dietr1ch wrote:
| 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 . .
| MrJohz wrote:
| 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.
| curtisf wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| jhanschoo wrote:
| 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 wrote:
| 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.
| ilikepi wrote:
| This is great! One thing that would be helpful is to be able to
| drag multiple adjacent tiles...
| gschizas wrote:
| Why do some puzzles have a green or red border? What does this
| signify?
|
| EDIT: or purple border.
| JKCalhoun wrote:
| Someone is working on them.
| shivbhatia wrote:
| This is really cool!
| questerzen wrote:
| 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.
| ghusbands wrote:
| 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 wrote:
| 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 wrote:
| That's great, thanks. I've also independently verified
| the 25,309,575 using similar techniques.
| quuxplusone wrote:
| 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.
| quuxplusone wrote:
| 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.
| duskwuff wrote:
| 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.
| jaachan wrote:
| 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?
| Traubenfuchs wrote:
| ...how do I start a game?
| pimlottc wrote:
| 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.
| simonmysun wrote:
| Good job! So when a section is almost finished, how should I
| find the last few unsolved nonograms?
| anxiousbuddhist wrote:
| This 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 wrote:
| When a row is completed it vanishes ... Tetris-style.
| tantalor wrote:
| No but really how do I play. Do I click something to start a
| puzzle?
| dietr1ch wrote:
| Just scroll down until you find an unsolved puzzle.
|
| I wish you could filter out and just play unsolved ones.
| 01HNNWZ0MV43FF wrote:
| https://en.wikipedia.org/wiki/Nonogram
| scythe wrote:
| This 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 wrote:
| I went through 102 before i knew it.
| butz wrote:
| In 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 wrote:
| Well, 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.
| NooneAtAll3 wrote:
| idk 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
| bspammer wrote:
| 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.
| fph wrote:
| There must be a swastika picture in there, somewhere.
| x-complexity wrote:
| I 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.
| egoburnswell wrote:
| Somewhere in there there's a 5x5 swastika
| Waterluvian wrote:
| I 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 wrote:
| There's a button at the top with an arrow ->, which lets you
| find an unsolved puzzle.
| Waterluvian wrote:
| Aha!! Yes thanks!
|
| I saw that icon and interpreted it as an export button or
| something.
___________________________________________________________________
(page generated 2025-05-31 23:00 UTC)