0

A Nonogram or a Griddler is a puzzle that can be explained here.

I noticed that while solving a few nonograms, some nonograms cannot be solved. These might include a 2x2 nonogram which looks like:$ \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} $ where the $1$s are filled in squares and the $0$s are empty. This nonogram is unsolvable because it would have the same clues as: $ \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} $ and so cannot be solved.

My question is that for a $\mathrm{n}\!\cdot\!\mathrm{m}$ rectangle, how many shapes would be unsolvable?

I first realized that if $n$ or $m$ is $1$, then there are no unsolvable shapes, because the clue would be exactly the same as the solution, for example $\begin{bmatrix} 0 & 1 &1&1&0&1\\ \end{bmatrix}$ would have a vertical clue of $\begin{bmatrix} 3,1\\ \end{bmatrix}$ and a horizontal clue of $\begin{bmatrix} 0 & 1 &1&1&0&1\\ \end{bmatrix}$ which would easily give the answer to the problem. Next I tried getting data for how many there are on small rectangles, by brute force, I found there to be $2$ unsolvable shapes in a $2$x$2$ and $10$ in a $2$x$3$. I attempted to get the amount in a $3$x$3$, but there are too many possibilities for me to keep track of. Can you please share your thoughts on this?

Ketchup Packet
  • 3

1 Answers1

1

Unfortunately, even the problem of determining whether a particular nonogram has a solution is almost certainly NP-complete, meaning that there is no computationally efficient method known to solve it.

I suspect that, broadly speaking, it will be almost as efficient to approach the problem from the other direction - generate all $2^{m \times n}$ possible grids, determine what their nonogram representations would be by counting the squares in the rows and columns, and then seeing how many of those are duplicates.

You can put some loose lower bounds on the problem by building larger puzzles from smaller ones - for example, any puzzle that has completely empty rows and columns can be broken up into independent sub-puzzles, and the overall puzzle can only be uniquely solvable if all the sub-puzzles are.

ConMan
  • 24,300