This is the twenty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hello! Today we are going to solve nonograms using ILP.

Table of Contents

Task description

Nonograms are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. Images are usually black and white, however, they can be colored. Below is an example of a nonogram (by wikipedia):

We will solve black and white nonogram, so we assume that numbers describe blocks of black fields whit at least one white field between every block.

Variables

As with most of the riddles we start with defining binary variables representing decisions. Let’s assume that the picture has size $w \times h$ (width and height). For every field we define a binary variable meaning whether we fill this field or no:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w}\displaystyle\mathop{\forall}_{1 \le j \le h} v_{i,j} \end{gather*}$

We also need to define variables representing top-left blocks’ corners. Let’s introduce the following notation: $c_{i}$ means number of blocks in $i$ -th column, $c_{i, t}$ means length of $t$ -th block in $i$ -th column. Analogously, $r_i$ means number of block in $i$ -th row, $r_{i, t}$ means length of $t$ -th block in $i$ -th row. We define the following binary variables:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{1 \le t \le c_{i}} C_{i,j,t} \\ \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{1 \le t \le r_{j}} R_{i,j,t} \end{gather*}$

Variable $C_{i, j, t}$ means whether $t$ -th block in $i$ -th column starts (e.g., its top-left field is) in field $(i, j)$ . Analogously, $R_{i, j, t}$ means whether $t$ -th block in $j$ -th row starts in field $(i, j)$ .

After solving the problem we obtain the solution from variables $v_{i,j}$ . Other variables are used only to specify constraints.

Constraints

We start with two obvious constraints: number of selected fields in each row and each column must match the blocks’ lengths:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\sum}_{1 \le j \le h} v_{i,j} = \displaystyle\mathop{\sum}_{1 \le t \le c_i} c_{i, t} \\ \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\sum}_{1 \le i \le w} v_{i,j} = \displaystyle\mathop{\sum}_{1 \le t \le r_j} r_{j, t} \end{gather*}$

Now we need to make sure that in every field there starts at most one block:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\sum}_{1 \le t \le c_i} C_{i, j, t} \le 1 \\ \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\sum}_{1 \le t \le r_j} R_{i, j, t} \le 1 \\ \end{gather*}$

Next, we need to make sure that if the block starts in particular field, all fields of this block are selected:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{1 \le t \le c_i} C_{i, j, t} \rightarrow \displaystyle\mathop{\wedge}_{0 \le k \le c_{i,t}-1}v_{i,j+k} \\ \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{1 \le t \le r_j} R_{i, j, t} \rightarrow \displaystyle\mathop{\wedge}_{0 \le k \le r_{j,t}-1}v_{i+k,j} \end{gather*}$

When a particular column block starts in field $(i,j)$ (which means that $C_{i,j,t}$ is true) then all fields $(i,j), (i, j+1), \ldots, (i, j + c_{i, t} - 1)$ must be true so we use conjunction. The same idea goes for row blocks. We also need to make sure that block does not start close to the boundary:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le t \le c_i} \displaystyle\mathop{\forall}_{ c_{i, t} \le j \le h} v_{i,j} = 0\\ \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{1 \le t \le r_j} \displaystyle\mathop{\forall}_{ r_{j, t} \le i \le w} v_{i,j} = 0 \end{gather*}$

Finally, we need to take care of blocks ordering. We need to make sure that block occur in proper order. We use the following idea: if some column block starts in field $(i,j)$ which means that $C_{i, j, t+1}$ is true, previous block must start in some field $(i, j')$ where $j' < j$ . So the sum of variables indicating start of the block must be true. The following constraints take care of this:

$\begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{2 \le t \le c_{i}} C_{i, j, t} \le \displaystyle\mathop{\sum}_{1 \le j' \le j-1} C_{i, j', t-1} \\ \displaystyle\mathop{\forall}_{1 \le i \le w} \displaystyle\mathop{\forall}_{1 \le j \le h} \displaystyle\mathop{\forall}_{2 \le t \le r_{j}} R_{i, j, t} \le \displaystyle\mathop{\sum}_{1 \le i' \le i-1} R_{i', j, t-1} \end{gather*}$

If $C_{i,j,t}$ is true then sum of $C_{i, j', t-1}$ must be true in order to fulfill the constraint. On the other hand, if $C_{i,j,t}$ is false, then sum of $C_{i, j', t-1}$ can have any value. The same goes for rows.

Summary

As we can see implementation is rather easy. The most difficult part is related to ordering the blocks, the rest is pretty straightforward. Next time we will solve sudoku.