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

41–50 of 89 posts

Re: Every 5x5 Nonogram

#41

Post by simonmysun »

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…

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

Re: Every 5x5 Nonogram

#42

Post by jsmith45 »

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…

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.

Re: Every 5x5 Nonogram

#43

Post by ghusbands »

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.

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?

Re: Every 5x5 Nonogram

#44

Post by quuxplusone »

quuxplusone wrote: post #31
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 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 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.

Re: Every 5x5 Nonogram

#45

Post by ghusbands »

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?

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.

Re: Every 5x5 Nonogram

#46

Post by duskwuff »

ghusbands wrote: post #43
questerzen wrote: post #27

Earlier quoted context omitted.

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.

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?

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

Re: Every 5x5 Nonogram

#47

Post by ghusbands »

duskwuff wrote: post #46
ghusbands wrote: post #43

Earlier quoted context omitted.

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?

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…

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

Re: Every 5x5 Nonogram

#49

Post by JKCalhoun »

gschizas wrote: post #22
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…

Why do some puzzles have a green or red border? What does this signify? EDIT: or purple border.

Someone is working on them.

Re: Every 5x5 Nonogram

#50

Post by Waterluvian »

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.

Post reply on HN