# Solving a nonogram puzzle¶

Description: Model for solving nonogram puzzles autogenerated using nonogram.mod, nonogram.dat and nonogram.run.

Tags: ampl-only, mip

Model author: Juan Jesús Losada del Olmo

References:

• Goldner, K., Kimura, R. and Schwartz, A. (no date). Nonokenken: solving puzzles using integer programs. University Research. University of Washington.

```# Install dependencies
%pip install -q amplpy
```
```# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
modules=["highs"],  # modules to install
)  # instantiate AMPL object and register magics
```

Consider the problem of solving a nonogram puzzle.

Parameters:

• `filas`

• `columnas`

• `fila_tam_bloque_datos[i,t]`

• `columna_tam_bloque_datos[j,t]`

• `num_bloques_fila[i]`

• `num_bloques_columna[j]`

• `fila_tam_bloque[i,t]`

• `columna_tam_bloque[j,t]`

• `mas_izquierda[i,t]`

• `mas_derecha[i,t]`

• `mas_superior[j,t]`

• `mas_inferior[j,t]`

Variables:

• `x[j,t,i]`

• `y[i,t,j]`

• `z[i,j]`

Objective function:

We do not seek to maximise or minimise anything, we simply aim to solve the nonogram and a solution of the nonogram puzzle is one that satisfies the constraints that we are going to impose below, so any feasible point is a solution of the nonogram. Constant objective function.

Constraints:

• `bloques_fila_una_vez[i,t]`

• `bloques_columa_una_vez[j,t]`

• `bloques_derecha[i,t,j]`

• `bloques_debajo[j,t,i]`

• `cobertura_filas[i,j]`

• `cobertura_columnas[i,j]`

• `cuadrados_blancos_fila[i,j,t,k]`

• `cuadrados_blancos_columna[i,j,t,k]`

Parameters, variables and constraints noted are commented as part of the code in the following cell.

```%%writefile nonogram.mod

# MODEL SETS: For the proposed resolution we do not make use of sets.

# ------------------------------ MODEL PARAMETERS ------------------------------

# - Stores the number of rows in the nonogram. There must be at least one.

param filas, integer, >= 1;

# - Stores the number of columns in the nonogram. There must be at least one.

param columnas, integer, >= 1;

# - Stores the size of the blocks in each row.

# - The parameter 't' is bounded at the top by '(columnas + 1) div 2', because as there
# must be a blank space between each block, a row can have at most '(columnas + 1) div 2'
# blocks of size one. The div operator returns the integer part of the division,
# therefore, we make '(columnas + 1) div 2' so that we can correctly delimit the maximum
# possible blocks that a row can have for an even or odd number of columns.

# - They must be integer values and greater than or equal to 0, by default they are
# initialised to 0. This means that when defining the values for this parameter in the
# .dat file, we can indicate with a '.' those values that we want to indicate as 0, this
# is interpreted as there is no block, and allows us to generalise different configurations
# easily and comfortably.

param fila_tam_bloque_datos {i in 1 .. filas, t in 1 .. (columnas + 1) div 2}, integer, >= 0, default 0;

# - Stores the size of the blocks in each column.

# - The parameter 't' is bounded at the top by '(filas + 1) div 2', because as there
# must be a blank space between each block, a column can have at most '(filas + 1) div 2'
# blocks of size one. The 'div' operator returns the integer part of the division,
# therefore, we make '(filas + 1) div 2' so that we can correctly delimit the maximum
# possible number of blocks that a column can have for an even or odd number of rows.

# - They must be integer values and greater than or equal to 0, by default they are
# initialised to 0. This means that when defining the values for this parameter in the
# .dat file, we can indicate with a '.' those values that we want to indicate as 0, this
# is interpreted as that there is no block, and allows us to generalise different
# configurations easily and comfortably.

param columna_tam_bloque_datos {j in 1 .. columnas, t in 1.. (filas + 1) div 2}, integer, >= 0, default 0;

# The parameters that we have just defined, 'fila_tam_bloque_datos' and 'columna_tam_bloque_datos'
# are in charge of storing the information provided in the .dat file. Using the information
# contained in these parameters, the following parameters are defined:

# - Stores the number of blocks owned by each row 'i'.

# - If the block 't' of row 'i' has a size greater than 0 (default value) we understand
# that it is a block and add 1 to it. We thus go through all the blocks 't' for each
# row 'i' and save the total.

param num_bloques_fila {i in 1 .. filas} :=
sum {t in 1 .. (columnas + 1) div 2: fila_tam_bloque_datos [i,t] > 0} 1;

# - Stores the number of blocks owned by each column 'j'.

# - If the block 't' of column 'j' has a size greater than 0 (default value), we
# understand that it is a block and add 1 to it. We thus go through all the blocks
# 't' for each column 'j' and save the total.

param num_bloques_columna {j in 1 .. columnas} :=
sum {t in 1 .. (filas + 1) div 2: columna_tam_bloque_datos [j,t] > 0} 1;

# - Stores the size of the blocks in each row 'i'.

# - We make use of the parameter 'num_bloques_fila [i]' to define the upper bound of
# the parameter 't'.

# - We make use of the parameter 'fila_tam_bloque_datos [i,t]' that collects from the .dat
# file the information related to the size of the block 't' of row 'i'.

# - Must be values greater than or equal to 1, as size 0 is not considered now, there are
# no blocks of size 0.

param fila_tam_bloque {i in 1 .. filas, t in 1 .. num_bloques_fila [i]} :=
fila_tam_bloque_datos [i,t], integer, >= 1;

# - Stores the size of the blocks in each column 'j'.

# - We make use of the parameter 'num_bloques_columna [j]' to define the upper bound of
# the parameter 't'.

# - We make use of the parameter 'columna_tam_bloque_datos [j,t]' that collects from
# the .dat file the information related to the size of block 't' of column 'j'.

# - Must be values greater than or equal to 1, as size 0 is not considered now,
# there are no blocks of size 0.

param columna_tam_bloque {j in 1 .. columnas, t in 1 .. num_bloques_columna [j]} :=
columna_tam_bloque_datos [j,t], integer, >= 1;

# Once we have stored both the total number of blocks in each row and column and the sizes
# of these blocks, it would be convenient, in order to make sure that the board that we have
# introduced is well defined and meets the conditions necessary to be a nonogram, to that
# the board we have introduced is well defined and fulfils the necessary conditions to be a
# nonogram, to carry out some checks before continuing with the problem.

# ----------------------------------- CHECKS -----------------------------------

# - The sum of the sizes of all the blocks in each row must be valid. That is, each row 'i'
# must verify that the sum of the sizes of the blocks it presents is less than or equal to
# the total number of columns minus the total number of blocks in that row plus one. This
# property must be satisfied in order to verify the fact that The fact that between each
# block of the same row there is a blank space must be verified.

check {i in 1 .. filas}:
sum {t in 1 .. num_bloques_fila [i]}
fila_tam_bloque [i,t] <= columnas - num_bloques_fila [i] + 1;

# - The sum of the block sizes of all blocks in each column must be valid. That is, each
# column 'j' must verify that the sum of the sizes of the blocks it contains is less than
# or equal to the total number of rows minus the total number of blocks in that column
# plus one. This property must be satisfied in order to verify the fact that between
# each block in the same column there is a blank space.

check {j in 1 .. columnas}:
sum {t in 1 .. num_bloques_columna [j]}
columna_tam_bloque [j,t] <= filas - num_bloques_columna [j] + 1;

# - The sum of the sizes of all blocks in all rows must match the sum of the sizes of all
# blocks in all columns. This property is required.

check: sum {i in 1 .. filas, t in 1 .. num_bloques_fila [i]} fila_tam_bloque [i,t] =
sum {j in 1 .. columnas, t in 1 .. num_bloques_columna [j]} columna_tam_bloque [j,t];

# ------------------------------- END OF CHECKS --------------------------------

# Once we have checked the above properties, and ensured that the nonogram board
# to be solved is well defined, we can move on to declare the last four parameters
# without any problems.

# - Stores for each block 't' of each row 'i', the smallest value of 'j' where such
# block 't' can be placed in row 'i' by verifying that the leftmost square of block
# 't' occupies position 'j'.

# - If it is the first block ('t'=1) of row 'i', the smallest position of 'j'
# where such a block can be placed in row 'i', is directly 'j'=1.

# - In case 't' is not the first block of row 'i', the position 'j' in question is
# calculated by adding to the smallest position 'j´' where the previous block 't-1'
# of row 'i' can be placed in that row occupying its leftmost square position 'j´',
# the size of that block 't-1' plus one. This one represents the white separation
# square that must be between two blocks.

param mas_izquierda {i in 1 .. filas, t in 1 .. num_bloques_fila [i]} :=
if t = 1 then 1
else mas_izquierda [i,t-1] + fila_tam_bloque [i,t-1] + 1;

# -	Stores for each block 't' of each row 'i', the largest value of 'j' where such
# block 't' can be placed in row 'i' by verifying that the leftmost square of block
# 't' occupies position 'j'.

# - If 't' is the last block in row 'i', the largest position of 'j' where such a
# block can be placed in row 'i', provided that the leftmost square of such a block
# is in position 'j', matches the total number of columns minus the size of such
# a block plus one.

# - In case 't' is not the last block of row 'i', the position 'j' in question is
# calculated by subtracting from the largest position 'j´' where the next block 't+1'
# of row 'i' can be placed in that row occupying its leftmost square position 'j´',
# the size of that block 't' minus one. This one represents the white separation
# square that must be between two blocks.

param mas_derecha {i in 1 .. filas, t in 1 .. num_bloques_fila [i]} :=
if t = num_bloques_fila [i] then columnas + 1 - fila_tam_bloque [i,t]
else mas_derecha [i,t+1] - fila_tam_bloque [i,t] - 1;

# Now we define two analogous parameters referring to the columns. In this case,
# we understand that the blocks are placed vertically and therefore we will use
# the term "top" instead of "left" as before.

# - Stores for each block 't' in each column 'j', the smallest value of 'i' where
# such block 't' can be placed in column 'j' by verifying that the uppermost square
# of block 't' occupies position 'i'.

# - If it is the first block ('t'=1) of row 'j', the smallest position of 'i' where
# such a block can be placed in column 'j', is directly 'i'=1.

# - In case 't' is not the first block of column 'j', the position 'i' in question is
# calculated by adding to the smallest position 'i´' where the previous block 't-1'
# of column 'j' can be placed in that column occupying its uppermost square the position
# 'i´', the size of that block 't-1' plus one. This one represents the white separation
# square that must be between two blocks.

param mas_superior {j in 1 .. columnas, t in 1 .. num_bloques_columna [j]} :=
if t = 1 then 1
else mas_superior [j,t-1] + columna_tam_bloque [j,t-1] + 1;

# - Stores for each block 't' in each column 'j', the largest value of 'i' where
# such block 't' can be placed in column 'j' by verifying that the topmost square
# of block 't' occupies position 'i'.

# - If 't' is the last block in column 'j', the largest position of 'i' where such
# a block can be placed in column 'j', provided that the uppermost square of such a
# a block is in position 'i', coincides with the total number of rows minus the size
# of such a block plus one.

# - In case 't' is not the last block of column 'j', the 'i' position in question is
# calculated by subtracting from the largest 'i´' position where the next block 't+1'
# of column 'j' can be placed in that column occupying its uppermost square the 'i´'
# position, the size of that 't' block minus one. This one represents the white
# separation square that must be between two blocks.

param mas_inferior {j in 1 .. columnas, t in 1 .. num_bloques_columna [j]} :=
if t = num_bloques_columna [j] then filas + 1 - columna_tam_bloque  [j,t]
else mas_inferior [j,t+1] - columna_tam_bloque [j,t] - 1;

# -------------------------- END OF MODEL PARAMETERS	--------------------------

# -------------------------- MODEL DECISION VARIABLES --------------------------

# x[j,t,i] = 1 : If block 't' in column 'j' is placed in column 'j' with its uppermost
# block in position 'i'.
# x[j,t,i] = 0 : Otherwise.

# - We restrict the variable 'i' to the possible positions that the uppermost square
# of block 't' can occupy.

var x {j in 1 .. columnas, t in 1 .. num_bloques_columna [j], i in mas_superior [j,t] .. mas_inferior [j,t]}, binary;

# y [i,t,j] = 1: If block 't' of row 'i' is placed in row 'i' with its leftmost
# block in position 'j'.
# y [i,t,j] = 0: Otherwise.

# - We restrict the variable 'j' to the possible positions that the leftmost square
# of block 't' can occupy.

var y {i in 1 .. filas, t in 1 .. num_bloques_fila [i], j in mas_izquierda [i,t] .. mas_derecha [i,t]}, binary;

# z [i,j] = 1 : If square 'j' in row 'i' is painted black, it is equivalent to having
# a square of a block at coordinate ('i','j') on the board.
# z [i,j] = 0 : If square 'j' in row 'i' is painted white, it is equivalent to there
# being no square of a block at coordinate ('i','j') on the board.

var z {i in 1 .. filas, j in 1 .. columnas}, binary;

# ----------------------- END OF MODEL DECISION VARIABLES ----------------------

# OBJECTIVE FUNCTION: We do not seek to maximise or minimise anything, we simply aim
# to solve the nonogram and a solution of the nonogram puzzle is one that satisfies
# the constraints that we are going to impose below, so any feasible point is a
# solution of the nonogram. Constant objective function.

# ------------------------------ MODEL CONSTRAINTS -----------------------------

# - The block 't' in row 'i' must appear in row 'i' only once.

s.t. bloques_fila_una_vez {i in 1 .. filas, t in 1 .. num_bloques_fila [i]}:
sum {j in mas_izquierda [i,t] .. mas_derecha [i,t]}
y[i,t,j] = 1;

# - The block 't' in column 'j' must appear in column 'j' only once.

s.t. bloques_columa_una_vez {j in 1 .. columnas, t in 1 .. num_bloques_columna [j]}:
sum {i in mas_superior [j,t] .. mas_inferior [j,t]}
x [j,t,i] = 1;

# - The block 't+1' in row 'i' must appear to the right of the block 't' preceding
# it in row 'i'.

s.t. bloques_derecha {i in 1 .. filas, t in 1 .. num_bloques_fila [i] - 1, j in mas_izquierda [i,t] .. mas_derecha [i,t]}:
y [i,t,j] <= sum {k in j + fila_tam_bloque [i,t] + 1 .. mas_derecha [i,t+1]}
y [i,t+1,k];

# - The block 't+1' in column 'j' must appear below the block 't' preceding it
# in column 'j'.

s.t. bloques_debajo {j in 1 .. columnas, t in 1 ..  num_bloques_columna [j] - 1, i in mas_superior [j,t] .. mas_inferior [j,t]}:
x [j,t,i] <= sum {k in i + columna_tam_bloque [j,t] + 1 .. mas_inferior [j,t+1]}
x [j,t+1,k];

# - If square 'j' of row 'i' is painted black, at least one block of row 'i' must
# be placed so as to cover square 'j' of row 'i'.

s.t. cobertura_filas {i in 1 .. filas, j in 1 .. columnas}:
z [i,j] <= sum {t in 1 .. num_bloques_fila [i], k in mas_izquierda [i,t] .. mas_derecha [i,t]: j - fila_tam_bloque [i,t] + 1 <= k and k <= j}
y [i,t,k];

# - If square 'j' of row 'i' is painted black, at least one block of column 'j'
# must be positioned to cover square 'j' of row 'i'.

s.t. cobertura_columnas {i in 1 .. filas, j in 1 .. columnas}:
z [i,j] <= sum {t in 1 .. num_bloques_columna [j], k in mas_superior [j,t] .. mas_inferior [j,t]: i - columna_tam_bloque [j,t] + 1 <= k and k <= i}
x [j,t,k];

# - To prevent the squares to be painted white from being covered by a block in a
# row, as the fact of being painted white symbolises that no square in any block
# covers that position.

s.t. cuadrados_blancos_fila {i in 1 .. filas, j in 1 .. columnas, t in 1 .. num_bloques_fila [i], k in mas_izquierda [i,t] .. mas_derecha [i,t]:
j - fila_tam_bloque [i,t] + 1 <= k and k <= j}:  y [i,t,k] <= z [i,j];

# - To prevent the squares to be painted white from being covered by a block in a
# column, as the fact of being painted white symbolises that no square in any block
# covers that position.

s.t. cuadrados_blancos_columna {i in 1 .. filas, j in 1 .. columnas, t in 1 .. num_bloques_columna [j], k in mas_superior [j,t] .. mas_inferior [j,t]:
i - columna_tam_bloque [j,t] + 1 <= k and k <= i}: x [j,t,k] <= z [i,j];

# -------------------------- END OF MODEL CONSTRAINTS --------------------------
```
```Writing nonogram.mod
```
```%%writefile nonogram.dat

param filas := 20;

param columnas := 20;

param fila_tam_bloque_datos : 1	2 3 4 5 6 7 8 9 10 :=
1   12 . . . . . . . . .
2   14 . . . . . . . . .
3    4 4 . . . . . . . .
4    3 2 2 3 . . . . . .
5    4 1 1 4 . . . . . .
6    2 2 2 2 2 2 . . . .
7    1 1 1 2 2 1 1 1 . .
8    1 1 1 1 1 3 1 . . .
9    1 1 2 4 1 . . . . .
10    1 5 1 1 5 1 . . . .
11    1 2 2 1 . . . . . .
12    4 1 1 4 . . . . . .
13    2 4 2 . . . . . . .
14    3 1 1 3 . . . . . .
15    2 2 2 . . . . . . .
16    4 5 . . . . . . . .
17    3 4 5 . . . . . . .
18    3 5 . . . . . . . .
19    3 5 . . . . . . . .
20    3 6 . . . . . . . .;

param columna_tam_bloque_datos : 1	2 3 4 5 6 7 8 9 10 :=
1    5 . . . . . . . . .
2    2 1 2 . . . . . . .
3    1 4 1 3 . . . . . .
4    5 3 4 . . . . . . .
5   14 3 . . . . . . . .
6    4 2 6 . . . . . . .
7    3 1 1 3 . . . . . .
8    2 1 2 1 1 . . . . .
9    2 1 3 2 1 . . . . .
10   2 1 1 1 1 . . . . .
11   2 1 1 1 . . . . . .
12   2 1 2 1 2 1 . . . .
13   2 1 3 1 1 . . . . .
14   3 1 1 3 . . . . . .
15   4 2 6 1 . . . . . .
16  14 5 . . . . . . . .
17   5 5 5 . . . . . . .
18   1 4 1 4 . . . . . .
19   2 1 4 . . . . . . .
20   5 3 . . . . . . . .;
```
```Writing nonogram.dat
```
```%%ampl_eval

reset;
model nonogram.mod;
data nonogram.dat;
option solver highs;
solve;

# Print the solution on the screen:

for {i in 1 .. filas + 1 + (filas + 1) div 2} {
if i <= (filas + 1) div 2 then {
for {j in 1 .. (columnas + 1) div 2} {
printf "   ";
}
printf "|";
for {j in (columnas + 1) div 2 + 1 .. columnas + (columnas + 1) div 2} {
if columna_tam_bloque_datos [j - (columnas + 1) div 2,i] == 0 then printf "  .";
if columna_tam_bloque_datos [j - (columnas + 1) div 2,i] > 0 and columna_tam_bloque_datos [j - (columnas + 1) div 2,i] < 10
then printf "  %d", columna_tam_bloque_datos [j - (columnas + 1) div 2,i];
if columna_tam_bloque_datos [j - (columnas + 1) div 2,i] > 0 and columna_tam_bloque_datos [j - (columnas + 1) div 2,i] >= 10
then printf " %d", columna_tam_bloque_datos [j - (columnas + 1) div 2,i];
if j == columnas + (columnas + 1) div 2 then printf "\n";
}
}

if i == (filas + 1) div 2 + 1 then {
for {j in 1 .. columnas + 1 + (columnas + 1) div 2}{
printf "---"
}
printf "\n"
}

if i > (filas + 1) div 2 + 1 then {
for {j in 1 .. (columnas + 1) div 2} {
if fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j] == 0 then printf "  .";
if fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j] > 0 and fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j] < 10
then printf "  %d", fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j];
if fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j] > 0 and fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j] >= 10
then printf " %d", fila_tam_bloque_datos [i - (filas + 1) div 2 - 1,j];
}
printf "|";
for {j in (columnas + 1) div 2 + 1 .. columnas + (columnas + 1) div 2} {
printf " %s", if z [i - (filas + 1) div 2 - 1,j - (columnas + 1) div 2] == 1 then " X" else "  ";
if j == columnas + (columnas + 1) div 2 then printf "\n";
}
}
}
```
```HiGHS 1.2.2: HiGHS 1.2.2: optimal solution
0 branching nodes
|  5  2  1  5 14  4  3  2  2  2  2  2  2  3  4 14  5  1  2  5
|  .  1  4  3  3  2  1  1  1  1  1  1  1  1  2  5  5  4  1  3
|  .  2  1  4  .  6  1  2  3  1  1  2  3  1  6  .  5  1  4  .
|  .  .  3  .  .  .  3  1  2  1  1  1  1  3  1  .  .  4  .  .
|  .  .  .  .  .  .  .  1  1  1  .  2  1  .  .  .  .  .  .  .
|  .  .  .  .  .  .  .  .  .  .  .  1  .  .  .  .  .  .  .  .
|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
|  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
---------------------------------------------------------------------------------------------
12  .  .  .  .  .  .  .  .  .|              X  X  X  X  X  X  X  X  X  X  X  X
14  .  .  .  .  .  .  .  .  .|           X  X  X  X  X  X  X  X  X  X  X  X  X  X
4  4  .  .  .  .  .  .  .  .|           X  X  X  X                    X  X  X  X
3  2  2  3  .  .  .  .  .  .|           X  X  X     X  X        X  X     X  X  X
4  1  1  4  .  .  .  .  .  .|     X  X  X  X     X                    X     X  X  X  X
2  2  2  2  2  2  .  .  .  .|  X  X     X  X        X  X        X  X        X  X     X  X
1  1  1  2  2  1  1  1  .  .|  X     X     X        X  X        X  X        X     X     X
1  1  1  1  1  3  1  .  .  .|  X     X     X           X           X        X  X  X     X
1  1  2  4  1  .  .  .  .  .|  X     X     X  X                          X  X  X  X     X
1  5  1  1  5  1  .  .  .  .|  X     X  X  X  X  X        X     X     X  X  X  X  X     X
1  2  2  1  .  .  .  .  .  .|     X     X  X                                X  X     X
4  1  1  4  .  .  .  .  .  .|        X  X  X  X     X              X     X  X  X  X
2  4  2  .  .  .  .  .  .  .|              X  X        X  X  X  X        X  X
3  1  1  3  .  .  .  .  .  .|              X  X  X     X        X     X  X  X
2  2  2  .  .  .  .  .  .  .|                 X  X        X  X        X  X
4  5  .  .  .  .  .  .  .  .|              X  X  X  X              X  X  X  X  X
3  4  5  .  .  .  .  .  .  .|           X  X  X        X  X  X  X        X  X  X  X  X
3  5  .  .  .  .  .  .  .  .|        X  X  X                                X  X  X  X  X
3  5  .  .  .  .  .  .  .  .|     X  X  X                                   X  X  X  X  X
3  6  .  .  .  .  .  .  .  .|     X  X  X                                X  X  X  X  X  X
```

You can find further information about nonograms resolution in Goldner, K., Kimura, R. and Schwartz, A. Nonokenken: solving puzzles using integer programs. University of Washington, where the authors use an Integer Programming model to first formulate the puzzle, and then speed up the solving process by translating it to a SAT instance.