The Magic of Nonogram Solving

By Víctor Franco-Sánchez
Note: This article has animations! They reproduce by clicking on the canvases. If you can't see them refresh the webpage or try a Chromium-based browser.

What are Nonograms?

I used to obsess over nonograms a few years ago. Back in my undergrad, I commuted by train for more than two hours each day, and I needed something to keep my mind busy. I found a free nonogram app, and soon I was hooked, grinding through puzzle after puzzle until I had solved every single one in the app.

A Nonogram (also called Picross or Griddlers) is a constraint satisfying logic puzzle game, not unlike Sudoku. The game is defined in a rectangular grid, each row and column having a sequence of numbers (called clues or blocks) describing how many consecutive black cells must appear in that line. For example, the clue [3, 2] means "three black cells, then at least one white cell, then two black cells." The challenge is to fill the grid so that all rows and columns match their clues.

Another obsession of mine is computer science, and the first instinct of a CS nerd when faced with a puzzle is: how could I automate solving this? Since nonograms belong to the same class of problems as Sudoku, one might try using the classic backtracking approach. But it doesn’t take long to realize that naïve backtracking is far too slow for real nonograms.

In this article I plan to explain my solution to the problem of solving nonograms algorithmically, and tie it back to a field of computer science called Constraint Satisfaction Problem (CSP) Solving.

Focusing on a Single Row

Every time you see a big, difficult problem, start by asking yourself if you can solve the smallest non-trivial subproblem. For this purpose, let's take a look at what happens when we try to solve a singular row. Suppose we have a row of length n = 5 with clue A = [2, 1]. Each cell can be either black (TRUE) or white (FALSE).

Now, suppose I give you a row partially filled. Some cells have been painted white, some cells have been painted black, and for the rest of cells no choice has been made one way nor the other. The question I now ask you is: Is there any way to fill the row that satisfies the clue?

This is a good moment to pause and think how would you solve this problem. It's not the hardest problem, but getting a truly efficient solution is non-trivial, so give it a go.

The Naïve Approach: Sliding Windows

A professor once told me that is better to have slow code than no code at all, so my first instinct is to write the simplest algorithm I know will work, even if it’s slow. In our case, there's a trivial algorithm! Just try every placement of blocks, and see if any of those placements match. Rudimentary, and extremely slow for large puzzles, but it works!

For our n = 5, A = [2, 1] case, all the possible placements are:
1. ■■□■□
2. ■■□□■
3. □■■□■

If none of the cells are specified to be painted black nor white, any of the three strategies would work, so we could confidently say that this problem is satisfiable. Not only that, but notice that on all three solutions, the second cell is always painted black. Do you realize what this means? It means that regardless of what the actual solution ends up being, the second cell will always have to be painted black. Keep this idea in the back of your head, it will help us later.

But what if some cells were painted beforehand? No problem. Let's see some interesting cases:

If the third cell was painted white beforehand, cases 1 and 2 would be valid. Because we still have valid cases, our problem is still satisfiable. Remember that before we were able to ensure that cell number 2 had to be black? Notice how if only cases 1 and 2 are valid, the first cell is also always black. This means we can ensure that these two cells will be painted black in the final solution.

If the fourth cell was painted white, same logic applies, but now only cases 2 and 3 would be valid. Now, instead of ensuring that cells 1 and 2 must be black, we would now ensure that cells 2 and 5 must be black.

And, of course, if it is the second cell the one that was painted white, now none of the cases fit, so this problem would be unsolvable.

As an algorithm, it works, and for small nonograms it's not terrible. Unfortunately, for large nonograms the number of combinations is roughly O(nk) in the worst case, exponential in the number of blocks, and since you have to generate all those combinations explicitly, the runtime can’t be better than their sheer number. For decently-sized n and k, this is far too prohibitive, so if we want something that scales, we need to think of something smarter.

The Dynamic Programming Approach

Did you know the concept of "Dynamic Programming" existed before the days of computers? The word "programming," in this context, just means "find an optimal program," in the sense of a military schedule for training or logistics. Or maybe not. Some sources claim Bellman named it "Dynamic Programming" to upstage Dantzig's Linear Programming by adding "Dynamic" to it. Who knows!

Sorry for this brief detour. History aside, the key idea is divide and conquer: break the problem into smaller subproblems, solve those, and combine the answers. Here’s one way to do it.

Definition: Let R(x, i) mean: "The first x cells can be filled using only the first i blocks."

There are only n + 1 possible values of x and k + 1 possible values of i. So if we built a DP table storing all answers, its size would be (n + 1) × (k + 1).

For our recurrence, we need to find a way to compute R(x, i) from smaller subproblems. Lucky for us, at every step, we need only two cases: Do we place the i-th block of the clue in our last available space (ending on position x), or do we not? With this in mind, we may define a recurrence:

Figure: A visualization of execution of the algorithm for the n = 5, A = [2, 1] case with a blank tile in position 3. Black arrows represent placing the last block at the end, dashed arrows represent not doing so.

Now, what is the cost of this algorithm? Well, the cost of a DP algorithm is just the cost per cell times the number of cells. We have O(n × k) cells, and some cases, like cases 1 and 3b require us to check for a stretch of values, which may be worse case O(n), so... O(n2 k). That's great! We've managed to reduce the cost from exponential to polynomial, which is a huge improvement. But, can we do even better?

Yes! Because, notice: These checks really just ask "is there any forbidden cell in [a, b]?". We can precompute, for each cell, the distance to the nearest forbidden cell. That takes O(n) time once, and reduces each query to O(1).

With this, now the compute done at every cell is O(1), and having O(n × k) cells, this gives us a final cost of O(n × k). This is quite possibly asymptotically optimal, although one can never say for sure. It's infamously hard to prove computational lower bounds like this. Nevertheless, this is already an outstanding cost, much better than our original, exponential cost.

Constraint Programming and Arc Consistency

Sometimes it’s much easier to describe what a solution looks like than to actually find one. Take Sudoku: searching for a solution is challenging, but describing the rules of a valid solution is simple. A valid Sudoku grid is a 9×9 table filled with numbers 1-9, with no duplicates in any row, column, or 3×3 block, plus some pre-filled cells. Wouldn't it be great if we could just tell a computer these rules, and let it figure out a solution? That’s exactly what Constraint Satisfaction Problems (CSPs) are about.

A CSP consists of variables (think of them as boxes) and their domains (the possible values that can go into each box). For example, in Sudoku, the variables are the cells, and their domains are the numbers 1-9. Each variable must eventually be assigned exactly one value from its domain.

Variables are linked by constraints, which restrict which combinations of values are valid. In Sudoku, constraints enforce "no repeated numbers in rows/columns/blocks" and "these cells must contain the given values."

We can also view Nonograms as CSPs. Each cell is a variable with domain {TRUE, FALSE} (or {BLACK, WHITE}), and each row/column is constrained to match its clue.

At a minimum, constraints in CSPs must be able to check consistency: given a full assignment of all variables, the constraint should say whether it is satisfied or not. But if this were all they did, a solver would struggle enormously, because it would have to explore a huge search space blindly.

Ideally, constraints should also enforce arc consistency. Informally, this means removing elements from the domains of variables (pruning) so that every remaining value is part of some complete, valid assignment. More precisely:

Arc consistency is powerful because it eliminates impossible values early, dramatically shrinking the search space. In the Nonogram case, a row (or column) is arc consistent if, for every cell:

If we want a solver capable of handling decently sized Nonograms, we need to design an arc consistency algorithm for these row/column constraints.

From Satisfiability To Arc Consistency

Wait... Don’t we already have an arc consistency algorithm? Not quite. What we developed earlier was a satisfiability algorithm: In time O(n × k) it can tell us whether there exists some assignment of values that satisfies the constraint. But satisfiability alone doesn't tell us how to prune domains, which is what arc consistency requires.

Fortunately, there’s a simple trick for turning satisfiability into arc consistency: Go variable by variable, and for each value in its domain, temporarily assign it. If the satisfiability algorithm reports "infeasible," we can safely remove that value. This transforms any O(C) satisfiability algorithm into an O(n × d × C) arc consistency algorithm, where n is the number of variables and d is the maximum domain size.

In our Nonogram setting, each cell has a domain of size 2 ({TRUE, FALSE}). So, with C = O(n × k), the resulting complexity is O(n2 × k).

Is it awful? Not at all! We're still in polynomial time territory, no exponential blowup has happened. But, of course, the natural question is: Can we do better? And the answer is yes! In fact, in the following section I will argue that we can construct a O(n × k) arc consistency algorithm, matching the efficiency of the satisfiability algorithm itself!

The Better Approach: Backwards Traversal of the DP Table

Take a look back at our previous algorithm. At every step, R(x, i) is asking two questions: Can we place the i-th block at the end of x? And, can we leave the x-th cell empty? These are questions that are about whether some cells can be filled or not, and that is precisely what we want in an arc consistency algorithm.

We use this piece of knowledge to get a solution by traversing the DP table backwards, starting from R(n, k). We will explore backwards, only looking at cells of the form R(x, i) that are true.

Start by initializing n cells with empty domains. This will store all the possible placements we find. Also, initialize a stack with the tuple (n, k) as its only element. In this stack we will add every element we need to process.

Pop from the stack the tuple (x, i). If both x and i are greater than 0, this is equivalent to Case 3 in the previous DP algorithm. We now check for cases 3a and 3b, checks we can do in O(1) time thanks to our previous result.

If case 3a is true, meaning we can set the x-th cell empty, we can add FALSE to the domain of cell x, and then we add (x - 1, i) to the stack to keep iterating the table.

If case 3b is true, meaning we can place the i-th block so that the end overlaps with the x-th cell, we can add TRUE to the domain of the last ai cells, and FALSE to the cell right before that if it exists. We next add (x - ai - 1, i - 1) to the stack.

For the base cases, if you ever reach Case 1, R(x, 0), this means that you can add FALSE to the domain of the first x cells, since that's the only possibility that makes R(x, 0) true. If you reach Case 2, R(0, i) for i > 0, you made a mistake in your code, since R(0, i) is always false.

Figure: Iterating the DP table to generate the arc consistent assignment.

With this we have managed to get the arc consistent domain with one single pass. However, we are still not done. Yes, if you write this algorithm as it's written it will be, in practice, faster than the previously mentioned, naïve algorithm. But notice that when processing Cases 1 and 3b we're modifying the domain of chunks of size up to O(n), and if we do this for a sizeable proportion of the total cells, this still unfortunately yields an asymptotic cost of O(n2 k), the same asymptotic cost as the trivial approach. Can we do better? Yes! By noticing that we have two types of "modifying domain runs," and we have ways to make them more efficient.

For Case 1, we are always modifying domains from the first cell to some other value. To avoid paying O(n) every time you can just remember the largest "some other value" you find, and doing the writing just once at the end.

For Case 3b, intervals are of the form [y, x], where y ≤ x. By traversing the DP table in strictly decreasing order of x, we can maintain at most one "active interval" at a time. When a new interval overlaps the current one, we merge them in O(1). When it does not, we finalize the old interval by adding TRUE to the required domains and replace the old interval with the new one. This yields O(n) amortized time since we never add TRUE more than once per cell.

To be able to traverse the elements in decreasing order of x, we notice that there are exactly n + 1 distinct values x can take. And so, we can, instead of keeping one single stack, keep n + 1 stacks, one per different value of x. This way we avoid an extra O(log n) cost per iteration needed for keeping a priority queue.

With these optimizations, our algorithm is now the DP part (O(n × k)) plus the backwards traversal (O(n × k)) plus the amortized runs (O(n)), for a final, total cost of O(n × k) time.

The CSP Algorithm

Unfortunately, mere arc consistency is not sufficient to solve all nonograms. Nonograms are NP-Complete[1], which means that no polynomial time algorithm will suffice to fully solve them. That is, unless P = NP, which most computer scientists heavily doubt. For example, this nonogram is one arc consistency alone can't solve:

But wait... The algorithm solved it. How is that possible? The secret: Backtracking.

"But, I thought you said backtracking didn't work for this problem!" No. I said backtracking alone doesn't work for this problem. But if you tie backtracking with arc consistency, you get an incredibly powerful algorithm that is capable to solve rather sizeable nonograms. Even when doing the simplest form of backtracking, our algorithm can already solve many nonograms:

def solve(nonogram): stack = [] apply_arc_consistency_until_you_can_no_more(nonogram) # Remember, empty domain means there is a contradiction if some_cell_has_empty_domain(nonogram): return UNSOLVABLE while has_cells_with_no_assigned_value(nonogram): cell = get_cell_with_no_assigned_value(nonogram) stack.append([copy(nonogram), cell]) cell.domain = {EMPTY} apply_arc_consistency_until_you_can_no_more(nonogram) while some_cell_has_empty_domain(nonogram): if len(stack) == 0: return UNSOLVABLE [nonogram, cell] = stack.pop() cell.domain = {FULL} apply_arc_consistency_until_you_can_no_more(nonogram) return assignment(nonogram)

This is the CSP Algorithm. As you can see, it is a backtracking algorithm, but just with some extra arc consistency methods for aggressive search space pruning. There are many possible improvements we could implement. Good variable selection heuristics (changing the method get_cell_with_no_assigned_value to choose most important variables), some good assignment heuristics (instead of initializing the variable's domain to {EMPTY}, initializing it to the most likely value), adding symmetry-breaking constraints, and many other possible optimizations, but the fact that this very bare-bones implementation works so well just goes to show the incredible power this paradigm has.


Conclusions

I have always been fascinated by constraint programming. The idea that you can simply describe what a solution should look like and let the solver find it feels almost magical. SAT solvers and logic programming share this trait, but what makes CSP especially compelling is the ability to define your own constraints and propagation methods. This flexibility turns CSP into a toolbox for building systems that can solve highly complex problems with surprising elegance.

The Nonogram case may seem trivial, but it illustrates the principle clearly. At the other extreme, constraints like AllDifferent, which appear everywhere from timetabling to resource allocation, can be enforced with clever algorithms that achieve arc consistency in
a not-too-dissimilar-to-oursThe cost for the AllDifferent GAC algorithm is O(d n √n), with d being the size of the domain and n being the number of variables.
time [2, pp. 218-222]. This highlights the deeper lesson: even with general-purpose automated reasoning tools, nothing rivals the power of domain-specific knowledge.

References

1. Nagao, Tadaaki, et al. NP-completeness results for nonogram via parsimonious reductions. Technical report, Tokyo Institute of Technology, 1996.
2. Rossi, Francesca, Peter Van Beek, and Toby Walsh, eds. Handbook of constraint programming. Elsevier, 2006.

Aside: Regular Expression Constraints

Nonogram rows actually belong to a more general and well-studied family of constraints: Regular expression constraints[2, pp. 215-216]. For example, a clue like [3, 2, 5] can be encoded by requiring the row's variables to match the regular expression False* True3 False+ True2 False+ True5 False*.

Arc consistency for regular expressions can be enforced using a dynamic programming method very similar to the one presented earlier in this article in O(n × |Σ| × |Q|) time [2, pp. 222-224], where |Σ| is the alphabet size (2 for Nonograms) and |Q| is the number of states in the automaton. In this case, |Q| = O(S), where S is the total number of filled cells specified by the clue (for [3, 2, 5], S = 10). This yields a complexity of O(n × S).

Since S can be much larger than the number of blocks k (up to n in the worst case), this bound can be worse than our specialized O(n × k) approach. Nevertheless, the regex perspective is quite powerful and good enough for many applications, even if not asymptotically optimal here.

Aside: Heuristic Search for Nonograms

Have you tried running that last nonogram? You may have noticed that, first, it took longer than for most nonograms in this article. This is because this last nonogram, even though it has one singular solution, is a very difficult one, one that mere arc consistency is insufficient to solve, and it needs quite a few decisions to get solved.

You may have also noticed that it's not making the most trivial algorithmic decisions. It is not simply picking the first unassigned cell, it is doing something smarter. The solver, indeed, is making non-trivial decisions to decide which variable to decide on next when arc consistency propagation is insufficient.

In particular, the algorithm for deciding the satisfiability of a row can be adapted to count the number of solutions instead of just merely telling you if a row is satisfiable or not. With this, we may, heuristically, decide on the cell with the lowest sum of the total number of solutions for the row and column the cell is in. We’ll call this the solution-count heuristic: Pick the cell that has the fewest possible sum of solutions for all involved constraints. The intuition is that if there are few valid solutions in the row and columns that cell is on, assigning a value to this variable will most cleanly split the search space in two, and if it is unsatisfiable, hopefully, by choosing such a constrained variable we will find out soon, fail fast, and backtrack quickly into the right track.

This is a very common technique in CSP Solving, choosing the most constrained variable to propagate next. A very common heuristic for this is Minimum Remaining Values (or MRV), which tries to decide on the cell with the smallest domain available. While, for general problems, this heuristic often works well, for our particular problem this heuristic is rather silly. I mean, think of the possibilities: The domains can have size two (TRUE and FALSE), one (which means we have already decided its value) or zero (which means we've found a contradiction). There is only one case in which we need to decide a variable, and that is the domain of size two case. For our nonogram case, the MRV heuristic does nothing.

Without this heuristic, the last nonogram would not solve, or, at least, not on a reasonable time. There is a valuable lesson to be learned here, namely that on these kinds of very difficult search problems, traversing and pruning are only one part of the fight. Another, almost equally important, part is choosing the right order of exploration. A good heuristic can make the difference between instant success and hopeless flailing.