Teaching Computers to Solve Nonograms for a Discord Coding Contest

And make some cool visualisations along the way

SiriusSome guy on internet

I was recently invited to a French CS community which was running monthly coding contests, the current one was about solving nonograms. Around the same time I got into making JavaScript based visualisations, so I submitted an animated Nonogram solver as my entry to the contest, and created a new Markdown flavour which is used to write this article.

Nonograms are really similar to the 90s hit game Sudoku, in the sense that they both involve filling up a grid. Instead of filling the grid with numbers 1 to 9, a completed Nonogram consists of cells coloured black and white - making it far more visually appealing as they can be made to show an image when completed.

Have a look at this cool Nonogram of a rabbit!

What you are seeing now are the steps that the solver took to complete the Nonogram.

Before writing that, we need to teach the human how to solve Nonograms.

Let's start with something simpler.

The Rules of a Nonogram

An unsolved Nonogram is an empty grid with rows of numbers to the left and above - each of these rows gives the requirement on how the row should be filled.

See the example below

Focus just on the first row, the rule for it is just 3 - meaning there are 3 connected black cells on this row.

Colouring the 3 black cells as so would satisfy the rule.

Moving on, the second row has 4 connected black cells, this is one way to colour the cells.

The third row has a 2-block and a 1-block, which are both present.

Continue until the entire grid is filled.

Then verify that the rules for each vertical column are satisfied as well.

Now that we know the rules of a Nonogram, let's figure out some specific techniques used to solve it, so we can use them in the solver.

Oh, looks like we need a new board for that.

Techniques in Solving Nonograms

Similar to Sudoku, most Nonograms can be solved by repeatedly taking obvious steps until it is solved completely.

The Really Obvious Steps

The Empty and Full Row

Starting from the most obvious one, a row with 0 black squares is just an empty row. We mark a cell empty to indicate we are certain it is white.

Similarly, a row with 5 black squares would just be a full row.

The Filled Row

Consider a 2-2 row, there is only one way to colour this row.

This is also true for a 1-3 row, or a 1-1-1 row. In general, there is only one way to fill a row with $n$ cells if $b+(c-1)=n$ .

$b$ is the number of black cells.
$c$ is the number of chunks (rule entries).

A full row is just a special case of this.

The Moderately Obvious Steps

Partially Solving Rows by Cases

Consider a 4 row, there are two ways to fill it.

We colour (or mark) only the cells that we are certain of. Although we don't know which is the correct way of filling the row, we are certain about what's common in both the cases - the middle three squares.

Convince yourself a that similar process can be used to partially solve a 3 row or a 2-2 row. The Really Obvious Steps is just a special case of this (with only one case).

Starting from a Partially Filled Row

Consider the following row.

Since the forth cell is white, it is obvious the only one way to fill this row is as below. How can a computer know this?

Examples

Have a go at some examples that can be fully or partially solved.

Actually Solving a Nonogram

With what's said, let's see how these techniques are used to solve a Nonogram.

Look at the entire board to see if there is a row that can be solved.

For example, this 3-1 row.

The 4-column gives three black cells.

The 2 row can be partially solved. How? (hint: make a list of all possible ways to fill the row)

As exercise, try solve for each row before revealing the solution to it.

Filling in the rest of the board.

Which is our completed Nonogram.

Writing the Solver

As a quick recap, we just solved a Nonogram in three simple steps:

Check all rows (and columns) to find a row that can be fully or partially solved.
Fully or partially solve the row using one of the techniques above.
Repeat the previous two steps until the entire Nonogram is solved.

Representing the Board

Starting with the smallest item each cells can have three states:

1enum CellState {
2    Blackened,
3    Marked,
4    Empty
5}

For a Nonogram of dimension $m\times n$

Its dimensions: width = $m$ and height = $n$ .
The list of rules, each rule can be represented as a list of integers int[]. The first $m$ rules are the rules for the horizontal rows, the rest of the $n$ lines are the rules for the vertical columns.
Its state: which is a 2D grid of CellState.

1struct Board {
2    width: u32,                  // int
3    height: u32,                 // int
4    rules: Vec<Vec<u32>>,        // int[][]
5    state: Vec<Vec<CellState>>,  // CellState[][]
6}

We also declare a few helper functions, which implementation will be omitted. Invalid Rust code is also used for better readability. The actual solver include some optimisations which are not shown here.

1impl Board {
2    // Create an empty board given dimensions and rules.
3    fn new(w: u32, height: u32, rules: Vec<Vec<u32>>) -> Board;
4
5    // Returns true if there are no empty cells
6    fn is_solved() -> bool;
7
8    // Returns the value of m + n
9    fn row_count(&self) -> u32;
10
11    // If i < n, return the rule of a row
12    // If n ≤ i, return the rule of a column
13    fn get_rule(&self, i: u32) -> Vec<u32>;
14
15    // If i < n, return the cells of a row
16    // If n ≤ i, return the cells of a column
17    fn get_row(&self, i: u32) -> Vec<CellState>;
18
19    // Returns None if there is a conflict
20    // Returns a copy of Board otherwise,
21    // so the original copy is never modified.
22    fn with_row(&self, i: u32, state: Vec<CellState>) -> Option<Board>;
23}

Notice that with_row may fail. This is because a cell is only filled if we are absolutely sure of its colour - if a cell is shaded black (it is certainly black) then later marked white (it is certainly white), this would not be valid! In this case, either

The rules of the board do not give a Nonogram, or
One of the cells are shaded wrong, which will good to know when it happens.

Determining if a Row can be Solved

How do we know if a row can be fully or partially solved?

If we make a list of all possible ways to fill a row, and find what's common between all those cases, those are the cells we can fill in for now.

Step 1: Enumeration

Create a function that returns a list of all possible ways to fill the row given the rules.

Approach: recursion
Time complexity: $O(n^r)$ where $n$ is the width of the row and $r$ is the number of rules (why?)

1fn possible_cases(rule: &Vec<u32>, row_length: u32)
2        -> Vec<Vec<CellState>> {
3    // If the rule is just a `0`
4    // The only possible fill is
5    // a list of `row_length` white cells
6    if rule == vec![0] {
7        return vec![ vec![CellState::Marked; row_length] ]
8    }
9
10    let first_chunk: u32 = rule.first();
11
12    // If the chunk is wider than there are space left,
13    // There are 0 possible ways to fill the row,
14    // So the list of ways is empty.
15    if first_chunk > row_length {
16        return vec![]
17    }
18
19    let mut possible_cases = vec![];
20
21    if rule.len() == 1 {
22        // If this is the only chunk in the rule,
23        // Then you can put it anywhere in the row.
24        let possible_locations = 0..(row_length - first_chunk + 1);
25
26        // [marked cells] [black cells] [marked cells]
27        // <----------- width = row_length ---------->
28        // <------------> = start_location
29        for start_location in possible_locations {
30            let mut single_possibility = vec![];
31            let blank_cells_after = row_length - first_chunk
32                                    - start_location;
33
34            single_possibility.append(
35                vec![CellState::Marked; start_location]);
36            single_possibility.append(
37                vec![CellState::Blackened; first_chunk]);
38            single_possibility.append(
39                vec![CellState::Marked; blank_cells_after]);
40            possible_cases.push(single_possibility)
41        }
42    } else {
43        // There are chunks after this,
44        // You need to leave at least one empty space afterwards
45        // to separate the next chunk from the current one
46        let possible_locations = 0..(row_length - first_chunk);
47        let mut possible_cases = vec![];
48
49        for start_location in possible_locations {
50            let row_length_remaining = row_length - first_chunk
51                                       - start_location - 1;
52
53            // This holds the row with the chunks at start_location
54            // And a marked cell afterwards to
55            // separate it from the next chunk.
56            let mut incomplete_row = vec![];
57            incomplete_row.append(
58                vec![CellState::Marked; start_location]);
59            incomplete_row.append(
60                vec![CellState::Blackened; first_chunk]);
61            incomplete_row.push(CellState::Marked);
62
63            // Recursion!
64            // Get a list of possible ways to
65            // fill the remaining chunks in the remaining space
66            let possible_cases_remaining =
67                possible_cases(rules[1..], row_length_remaining);
68
69            // For each of those ways,
70            // Append it to the incompleted row
71            for remaining_case in possible_cases_remaining {
72                let completed_row = incomplete_row.clone();
73                completed_row.append(remaining_case);
74                possible_cases.push(completed_row)
75            }
76        }
77
78        possible_cases
79    }
80}

Step 2: Filtering

The row may already be partially filled, from the list of all possible cases, get rid of the ones that conflicts with the partially filled row, since once shaded, the colour of the cell cannot be changed.

Approach: basic iteration
Time complexity: $O(n)$

1// Returns false if there is a conflict between the current row
2// Otherwise true
3fn no_conflict(
4    current_row: &Vec<CellState>,
5    possibile_row: &Vec<CellState>)
6        -> bool {
7    for (current, possible) in current_row.zip(possibile_row) {
8        // Do not allow if trying to assign
9        // a different value to a non-empty cell
10        if current != CellState::Empty && current != possible {
11            return false
12        }
13    }
14
15    true
16}
17
18// Use step 1 to get a list of all valid possibilities
19fn valid_possibilities(
20    current_row: &Vec<CellState>,
21    rule: &Vec<u32>)
22        -> Vec<Vec<CellState>> {
23    possible_cases(rule, current_row.len())
24        .filter(|possibile_row|
25            no_conflict(current_row, possibile_row))
26        .collect()
27}

Step 3: Apply Changes

Find what's common between the possible cases, and apply them to the row.

Approach: iteration
Time complexity: $<O(n^r)$ where worst case when all rows from step 1 are valid.

1// Find cells shaded the same in all possibilities
2fn common_cells(current_row: &Vec<CellState>, rule: &Vec<u32>)
3        -> Option<Vec<CellState>> {
4    let possibilities = valid_possibilities(current_row, rule);
5
6    // There are no valid ways to fill the row
7    if possibilities.is_empty() {
8        return None
9    }
10
11    let mut commons = vec![CellState::Empty; rule.len()];
12
13    // If a cell is the same as the first possibility
14    // in all possibilities
15    for (i, cell) in possibilities.first().enumerate() {
16        if commons.all(|row| row[i] == cell) {
17            commons[i] = cell;
18        }
19    }
20
21    Some(commons)
22}
23
24// Apply common_cells to progress the row
25fn progress_row(current_row: &Vec<CellState>, rule: &Vec<u32>)
26        -> Option<Vec<CellState>> {
27    // Return None if common_cells returns None
28    let commons = common_cells(current_row, rule)?;
29    let progressed_row = current_row.clone();
30
31    // Apply changes
32    for (common, new_state) in commons.zip(progress_row.iter_mut()) {
33        if common != CellState::Empty {
34            *new_state = common;
35        }
36    }
37
38    Some(progress_row)
39}

Since each of these function is ran only once when progress_row is called, the overall time complexity of progress_row is just $O(n^r)$ .

Progressing the Board

We now have a function progress_row that will try to progress a row as far as possible, we will use it to write a function that progress the board as far as possible.

Approach: repeat until complete
Time complexity: $O(n^3\times\texttt{progress\_row})$ for a $n\times n$ board, since each iteration colour at least one cell, and each iteration tries to progress $2n$ rows using the progress_row function. This overwhelmingly becomes $O(n^r)$ considering the huge time complexity of progress_row compared to other parts of the algorithm.

1fn progress_board(board: &Board) -> Option<Board> {
2    let mut board = board.clone();
3
4    // Iterate through all the rows and columns, and repeat
5    loop {
6        let mut changed_rows = 0;
7
8        for i in 0..board.row_count() {
9            let current_row = board.get_row(i);
10            let rule = board.get_rule(i);
11
12            // Return None if progress_row returns None
13            let progressed_row = progress_row(current_row, rule)?;
14
15            // Only update if the row has been changed
16            if progress_row != current_row {
17                board = board.with_row(i, progress_row);
18                changed_rows += 1;
19            }
20        }
21
22        // Stops the function either when the board is solved fully
23        // Or if the last iteration did not change anything
24        // If we dont quit the function,
25        // it will change nothing in the next iteration, and so on
26        if board.is_solved() || changed_rows == 0 {
27            return Some(board);
28        }
29    }
30}

What would cause progress_board to be stuck and exit without solving the board completely? For most Nonograms, including the $20\times20$ Nonogram showcased at the beginning, progress_board can solve them by repeatedly taking obvious steps.

Not all Nonograms can be solved by taking obvious steps, for example:

This is one possible solution of the Nonogram.

And here is another possible solution.

Focusing on only one row, the two solutions have no cells in common.

The progress_row function works by finding common cells between different ways of filling the row, and therefore will fail in this situation.

In this case, we resort to blind guessing.

This square is either black or white.

Suppose it is white, then the row has an obvious solution, and so does the board. At which point we can run progress_board to solve the board completely.

If the guess wasn't correct (although in this case it is), we can simply roll that back and try it with a black cell instead.

Since a cell is either black or white, one of the two guesses has to be correct.

The Final Solver Algorithm

We allow guessing the shading of one cell if the algorithm failed to make any progress. Then apply progress_board to see if the board can be progressed without guessing.

Approach: use progress_board to go as far as possible, then alternate between blind guessing (backtracking) and progress_board until the board is solved.
Time complexity: Between $O(n^r)$ (lower: no backtracking required) and $O(2^{n^2})$ (upper: full backtracking).

1// This function solves a board completely
2// Returns None if it is impossible to do so
3fn solve(board: &Board) -> Option<Board> {
4    // If progress_board returns None,
5    // then the board cannot be solved,
6    // So return None
7    let progressed_board = progress_board(board)?;
8
9    // progress_board stops only for 2 reasons:
10    // - the board is solved
11    // - there are no obvious steps
12    if progressed_board.is_solved() {
13        Some(progressed_board)
14    } else {
15        // Pick an empty cell, implementation omitted
16        let cell_x = todo!();
17        let cell_y = todo!();
18
19        // If the board is possible to solve
20        // One of these guesses must be correct
21        let possibility_1 = board.blacken(cell_x, cell_y);
22        let possibility_2 = board.mark(cell_x, cell_y);
23
24        let solved_1 = solve(possibility_1);
25        if solved_1.is_some() {
26            // Possiblitly 1 is correct
27            // And here's the solved board
28            return solved_1
29        } else {
30            return solve(possibility_2)
31        }
32    }
33}

Implementation Specifics

The specifics in implementation could improve performance of the algorithm.

When finding all possible ways to fill a row, do not place chunks in places which is already marked as white.
When guessing, do it on a cell where 50% of the ways to fill it are white, 50% are black, just because 2 is a magic number.

There may also be faster ways to find common cells, who knows.

Nonogram Playground

You can define your own Nonogram below and watch the solver solve it:

The first line m n states the number of rows m and columns n of the Nonogram.
The next m lines are the rules for rows, followed by n lines of rules for columns.

Then just scroll down to see the solver does its work.

Scroll down to see the Nonogram.

Almost there...

This is a submission to the Devos Code Contest. Article source code available on GitHub.