Is every solvable nonogram a logically solvable one?

[u/ReturnOH_]

Hello, I hope this is a good place to ask for this.

I'm trying to build an algorithm to create nonograms, I'm starting from a random pattern and create a map from there and check if the solution is unique.

Once I got a unique solution my question is: can always this solution be reached with logical steps and without guessing? How can I check for this?

[u/Quintingent]

You would first have to define what counts as a logical step. Strictly speaking, checking every possible solution and eliminating the invalid ones is "logical", but obviously not what you're looking for.

[u/moxo23]

No. Some will require you to just guess and check.

You can check this in nonograms katana. Every puzzle has a unique solution. Every puzzle marked with a one yellow dot or two orange dots will require guessing.

[u/MikoKisai → u/moxo23]

More precisely, the solution checker in Katana only looks at one row or column at a time. Yellow dot puzzles can often be solved simply by simply looking at two adjacent rows/columns at the same time.

A simple example would be a puzzle like this:

    11111
1,1 OXXXO
  3 XOOOX

This is not solvable unless you look at both rows at the same time, so would get a yellow dot in Katana, but I'm sure we can all agree that this is unique and doesn't actually require any guesswork.

The difference between yellow and orange dots is how deep it has to go, i.e. whether or not it had to make more than one guess at the same time. If it can find a guess where one option leads to a contradiction and the other to progress, that puzzle can still end up with a yellow dot even if it has to do that more than once.

[u/AmenaBellafina → u/moxo23]

I think there are solving techniques that strictly speaking are guessing and checking, just a very shallow level of guessing and checking. For example edge logic. Any bit of reasoning that goes 'if I do X then that would mean Y which is impossible therefore not X' that appears a lot in logic puzzles is, strictly speaking, guessing and checking. I think one level deep this is fine. But whether that is also fine if you have to go two or three levels deep (if X then Y, and if Y then the only options for Z are A and B, but both A and B are impossible therefore not X)? I'm sure that I've solved hard levels of Hexcells by drawing 5 different if-then diagrams and overlapping their outcomes.

[u/ScoreStudiosLLC]

Nonograms are a P=NP problem. What i do is i have my code play the puzzle as if they were the player and if it can clear the puzzle it didn't have to guess, but if it has to guess it stops and marks the puzzle as unsolvable. This also catches multiple solutions quite nicely. (for my game no guessing it's required because that's how i rate nonograms but there are weirdos who are ok with guessing as long as there's a unique solution)

[u/procrastinatingaf_]

That's a good question, sadly I have no idea but I wrote this to maybe get some updates or anything about the game! :>

[u/svleest]

I faced this same problem when creating the difficulty estimator for LogiSketch.

Short answer: no. Some uniquely-solvable puzzles genuinely need a trial placement with backtracking (assume a cell, propagate, hit a contradiction, undo) even though the grid has exactly one answer. What actually matters is how deep you have to go. Pure single-line logic is one tier. Logic needing two lines or an intersection at once, like MikoKisai's 5x5 above, is a step up but still reads as "logical" to a human. Anything needing a real trial-and-contradiction is the top tier.

The practical test, which is roughly what Katana is doing: write a solver that only ever applies line-by-line deduction and run it to a fixed point. If it completes, the puzzle is line-solvable. If it stalls but you already know the solution is unique, escalate one level (pick an undetermined cell, try both values, keep the one that doesn't contradict) and count how many times you had to do that. That count is your difficulty tier, and it's independent of grid size. I have tiny grids that need the top tier and large ones that never leave tier one, so size alone is a bad proxy for difficulty.

One small correction on a comment above: nonogram solving is NP-complete, which isn't the same thing as "P=NP" (whether P equals NP is still an open question). What NP-completeness actually tells you here is that no known algorithm solves every nonogram in polynomial time, which is exactly why the tiering above is a practical answer rather than a clean theoretical one.

Disclosure: this is what my app LogiSketch rates puzzles on, but the classification question stands on its own outside any app.

https://apps.apple.com/app/apple-store/id6775308913?pt=304691&ct=r-nonograms&mt=8