Is It Easy to Make a Nonogram

How to get from left to right? This article explains it all. Image by author.

Solving Nonograms with 120 Lines of Code

Puzzles, combinations and solution gifs.

In this post, a way to solve Nonograms without any errors is shown by calculating the options for every line. It's not the most efficient way to come to a solution, in the end you can find more information about the fastest way. In my opinion, this is the most fun way because it leaves no room for mistakes. And as a bonus, you'll learn a bit more about counting problems! Let's jump in!

Game Explanation

A Nonogram (aka Griddler, Paint By Numbers, Hanjie or Picross) is a puzzle in which you try to reveal a picture. It's a logic puzzle with simple rules. You have a grid with squares, and every square should become black or white. Numbers on the side and top of the grid reveal the groups of black squares that should be in every row and column.

Solving Process

Let's start with an empty Nonogram:

The third column has the values 5, 2 and 6. This indicates there are sets of five, two, and six filled squares, in that order, with at least one blank square between successive sets. Because 5 + 1 (white square) + 2 + 1 (white square)+ 6 is equal to 15, this line is easy to solve, there is only one possible solution:

Only one possible solution for the third column, because the values and empty squares add up to 15. Image by author.

The dots are helping marks to indicate that these squares should be empty.

Let's continue. The lowest line contains a group of 14 black squares, and because the total line is 15 squares long, we can fill all squares besides the first and the last one:

Filling up the squares of the last row: because there should come a group with 14 filled squares, we can be certain about filling these squares. Image by author.

We can use these filled squares, because they correspond with the column values on the bottom:

Using the black squares on the bottom row: they can only belong to the column values on the bottom. So the second column gets five black squares, the fourth column three, and so on. Image by author.

Got it? By using some logic it's pretty easy to solve this Nonogram! You can try this one by yourself or continue reading and let the computer solve it for you.

Spoiler alert: a gif will show the solving process of this Nonogram at the end.

Solving a Nonogram Programmatically

After understanding the rules of the game, how can we let the computer solve Nonograms using math?

The program consists of three steps. The first step only happens at the beginning and is the most complicated one, while step 2 and step 3 are easy to understand and will be repeated until the puzzle is solved.

Step 1. Calculate all options for every row and column

We start by calculating all options to select black squares for every row and column (the next section explains how to do this if things get more complicated). This only happens at the beginning of the game. Let's say we have a row of five squares and we want to fill it with one group of three:

All options for a group of 3 black squares. Image by author.

This gives us the three options on the right.

Step 2. Fill squares that have only one possibility

If you look at the options for one row and you discover that there is only one possibility for a certain square, because in all options the square is black or in all options the square is white, the square can only be filled with this color. This example illustrates this:

Placing a group of 3 in a row with 5 squares, on the left you see all options to place the group, in the middle you see the middle square marked, because for all options this square is filled. This square should be black. Image by author.

Step 3. Remove options from the corresponding row or column

After filling a square (or making it white), we can look at the corresponding row or column and remove all options in which this square is the other color. Because these options aren't possible anymore. Example:

If we are certain about the last square (we discover it should be white because of the column values), the third option isn't possible anymore, so we remove it from our options for this row. Image by author.

How to calculate all options for every row and column?

The calculation of options was easy in the example above, we slide the group of three to the left until we reach the end of the row. But what happens if we take a more complicated list with values and try to find all possible options? Another example:

All options for placing groups with 3, 2 and 6 black squares in a row with 15 squares. Image by author.

In the example above we place the groups 3, 2 and 6 in a row with 15 squares. We need at least 13 squares for this combination of groups:
6 + 1 white square + 3 + 1 white square + 2 = 13
This means we have 2 empty squares left (15 minus 13 = 2).

An interesting thing to notice is that for the number of total options you only need to know the number of empty squares left and the number of groups you got. An intuitive proof:

Taking three groups with ones and two empty squares at the end gives us the exact same number of options as the example with group values 3, 2 and 6. Do you see the pattern? Image by author.

Okay, we are making progress! In this example we see that if we got three groups with values (6, 2, 3 on the left and 1, 1, 1 on the right), and two empty squares left, the total number of possible options is 10.

If we forget about the white squares between groups (those should be there no matter what), we can calculate the number of options using combinations. We got 5 places (3 groups + 2 empty squares) and need to select 3 out of 5 (we want to place 3 groups). Here you can find a bit more about combinations. It's easy to calculate all combinations using python and itertools.

            from itertools import combinations            opts = combinations(range(n_groups+n_empty), n_groups)

Translation from the combination, to the options to the visualization of the options. Image by author.

This also works for the 3, 2, 6 values, except we now place more ones at the places:

The groups become a bit larger, but the combinations are exactly the same as before.

That's it! This works for all groups of values. We only need the number of empty squares left and the number of groups to create all possible options using combinations.

Solution GIFs

There's no need to solve a Nonogram by hand after the creation of this program. Let's solve some Nonograms! 🤓

Let's start with a small one:

Can it solve the Nonogram we started with?

Yes, of course!

And the final one, what about a really large Nonogram?

Works pretty fast too! 😀👌

Code

Want to solve Nonograms using this program? Below you can find a gist with python code. You only need to specify the row values as a list of lists and the column values as a list of lists. If you call the NonogramSolver class it will start solving your Nonogram. You can choose to save all the steps by specifying the savepath variable.

Conclusion

The Nonogram solver we created has some benefits: it will never fill a square it's not completely certain about. The downside of this approach is computation time. If the puzzles become larger, more options are available for the rows and columns and the time it takes to solve the puzzle will become longer. Another downside is that it can't solve Nonograms with multiple solutions.

Luckily, some people already solved these problems. So if you are looking for a super fast Nonogram solver that can handle Nonograms with more solutions, you might find this article interesting.

Don't forget to subscribe if you'd like to get an email whenever I publish a new article.

cairndufftruiessinter.blogspot.com

Source: https://towardsdatascience.com/solving-nonograms-with-120-lines-of-code-a7c6e0f627e4

Cairnduff Truiessinter