%%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 --------------------------