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

11–20 of 89 posts

Re: Every 5x5 Nonogram

#11

Post by purpleidea »

okayestjoel wrote: post #4
gus_massa wrote: post #3

Earlier quoted context omitted.

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.

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

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

Re: Every 5x5 Nonogram

#12

Post by dietr1ch »

purpleidea wrote: post #11
okayestjoel wrote: post #4

Earlier quoted context omitted.

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

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

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

Re: Every 5x5 Nonogram

#13

Post by scythe »

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.

Re: Every 5x5 Nonogram

#14

Post by butz »

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?

Re: Every 5x5 Nonogram

#16

Post by okayestjoel »

gus_massa wrote: post #5
okayestjoel wrote: post #4

Earlier quoted context omitted.

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

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?

Re: Every 5x5 Nonogram

#17

Post by curtisf »

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…

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?

Re: Every 5x5 Nonogram

#18

Post by ilikepi »

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 great! One thing that would be helpful is to be able to drag multiple adjacent tiles...

Re: Every 5x5 Nonogram

#19

Post by MrJohz »

purpleidea wrote: post #11
okayestjoel wrote: post #4

Earlier quoted context omitted.

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

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

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.

Re: Every 5x5 Nonogram

#20

Post by stagger87 »

curtisf wrote: post #17
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…

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?

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.
Post reply on HN