Nonogram Solver
Andrew Polk  •  March 5, 2021  •  Python

What is a Nonogram?

A Nonogram is puzzle consiting of a grid with each cell in the grid being filled or unfilled. Each row and column has an associated number or set of numbers. These numbers tell how many filled cells there are in a row.

In the below example one of the rows has the values '2 9'. This means that the row will have 2 filled cells, one or more unfilled cell, then 9 more filled cells.

Unsolved Puzzle15x15 Nonogram Puzzle

The Science

The first step to solving is to look at it one row and one column at a time and determining the permutations of the values. We can start by considering a row with the key '13'

13 in a 15x15 puzzle has the following permutations. 🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔲🔲 🔲🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔲 🔲🔲🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳

Then taking the sum of each filled cell gives us. [1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1]

From this we can determine two things. One, each cell that equals the total number of permutations is required in the final answer. Two, each cell that sums to 0 cannot be in the final answer. 🔲🔲🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔳🔲🔲

We can then iterate over all the permutations for every column, deleting any permutation that do not satisfy the requirements for the chosen row

The same algorithm can be repeated switching columns and rows. If there is a unique solution then you will be able to cancel out row/column possibilities untill there is only one left for each row/column. Removing a possible solution changes the permutation sum the next time that row/column is checked.

The Code

The first step of coding an algorithm is converting the example puzzle into a format that can by used as an input into the code. Rows: 8, 6, 9, 2 9, 1 1 6, 10, 7, 9, 5 1, 2 2 1 1, 3 2 1, 5, 3 2, 6 1, 1 6 3 Columns: 2 1 1, 1 2, 3, 2 3, 2 1 4, 2 2 3, 8 3, 4 4 2, 9 3, 1 9 3, 1 9, 7, 4 1 1 1, 4 1 1, 2 4 2

The following code takes in a file name and parses it into a 3 dimensional array for processing.

Parse Puzzle

Next there needs to be a way to calculate all possible permutations for each row/column. The possible permutations are bound by the rules of the puzzle so an array representation can be created that limits the permutation calculation to only those that are possible.

The column key [4, 4, 2] can be thought of as ['4', '4', '2', '0', '0', '0', '0', '0']. Another requirement is at least one space between each filled cell grouping, so the array can be reduced to ['40', '40', '2', '0', '0', '0']

One final reduction can be done, we only need distince permutations where the non-zero values are in order. This can be achieved by replacing those values with place holders, resulting in ['x', 'x', 'x', '0', '0', '0']

After the permutations are calculated we can iterate through them and convert them to the un-compressed format, replacing the place holders with the actual values. ['0', 'x', 'x', '0', 'x', '0'] -> [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0]

Get Distinct Permutations

Running the puzzle through the previous code gets us all the possible array permutations for each row and column. The sum of those posibilities for all 15 rows/columns is printed below. Calculating the product of the Row array we get the total number of possible row combinations that could result in the solution. Fortunatly we do not have to iterate through all of them to solve the puzzle.

Output

Row Posibilities [8, 10, 7, 10, 56, 6, 9, 7, 45, 210, 120, 11, 55, 36, 20] Column Posibilities [220, 78, 13, 55, 84, 84, 10, 20, 6, 1, 15, 9, 126, 120, 56] Possible Solutions: 58,555,646,392,320,000,000

We continuously loop over the rows and columns, iterating both on each loop. As stated before, for each row/column we sum up the items per possibility array. If we're summing up rows then we iterate over column cells and vice versa. If we find a cell that was summed to 0 then we remove all possibilities that have that cell filled. If we find a cell that was summed to the max sum value then we remove all possibilities that don't have that cell filled. This runs until there no arrays removed during a loop.

Removing Posibilties
© 2019 Andrew Polk