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

31–40 of 89 posts

Re: Every 5x5 Nonogram

#31

Post by quuxplusone »

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…

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.

Re: Every 5x5 Nonogram

#32

Post by jaachan »

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…

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?

Re: Every 5x5 Nonogram

#33

Post by quuxplusone »

okayestjoel wrote: post #16
gus_massa wrote: post #5

Earlier quoted context omitted.

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

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?

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

Re: Every 5x5 Nonogram

#34

Post by curtisf »

jhanschoo wrote: post #28
stagger87 wrote: post #20

Earlier quoted context omitted.

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.

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.

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.

Re: Every 5x5 Nonogram

#35

Post by x-complexity »

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.

Re: Every 5x5 Nonogram

#36

Post by Traubenfuchs »

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…

...how do I start a game?

Re: Every 5x5 Nonogram

#37

Post by gus_massa »

okayestjoel wrote: post #16
gus_massa wrote: post #5

Earlier quoted context omitted.

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

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?

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

Re: Every 5x5 Nonogram

#38

Post by FabHK »

butz wrote: post #14

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?

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.

Re: Every 5x5 Nonogram

#39

Post by pimlottc »

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

Re: Every 5x5 Nonogram

#40

Post by gus_massa »

gus_massa wrote: post #37
okayestjoel wrote: post #16

Earlier quoted context omitted.

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?

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

*intermediately -> immediately
Post reply on HN