# Constraint Programming: Basic Problems

In this laboratory we will solve some toy problems from the constraint programming literature. The created models will be later improved using some basic constraint programming techniques.

## Warm Up

### N-Queens

• Definition: you have to place n queens on the chess board of size nxn in the way the won't attack each other (see: https://en.wikipedia.org/wiki/Eight_queens_puzzle).
• Assignment:
1. Fill missing elements in the model shown below
```%%%%%%%%%%%%%
% VARIABLES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% add variables with correct domains
% tip:
% var 1..N: x; declares a variable with domain 1..N
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%
% CONSTRAINTS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tip:
% row_i = row_j (-/+) (j - i)
% matches queens placed on the same diagonal, where:
% - i,j - column index
% - row_n - queen's position in the nth col
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solve satisfy;

%%%%%%%%%%%%%%%%%%%
% OUTPUT EXAMPLE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - rows[i] - queen's position in the ith row
% - N - number of queens
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
output [ if fix(rows[j]) == i then "H" else "." endif ++
if j == N then "\n" else "" endif | i,j in 1..N]```

If you have problems with the MiniZinc syntax, please refer to the examples
in the MiniZinc Cheat Sheet. (`MiniZincIDE → Help → Cheat Sheet…`)

### Graph Coloring

• Definition: assign colors the vertices in a graph in the way that no adjacent vertices have the same colors. In case of the planar graph you will require only four colors (why? there is a very famous proof of this fact). Otherwise you can require even as many colors as there are vertices. More on the wikipedia page.
• Assign:
1. Fill missing elements in the model shown below (example data files):
```%%%%%%%%%%%%%
% PARAMETERS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Should be loaded from the data file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%
% VARIABLES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variables with correct domains
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%
% CONSTRAINTS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tip:
% - number of used colors = the highest used color number
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%
% GOAL
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Minimize the number of used colors
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
solve minimize colorsNumber;

%%%%%%%%%%%%%%%%%%%%%%%%
% OUTPUT EXAMPLE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - colorsNumber - number of used colors
% - nodes - array of vertices with assigned colors
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
output [show(colorsNumber), " colors\n",] ++
[show(nodes[i]) ++ " " | i in 1..nodesNumber]```

## Global Constraints

One of the simplest (and also the best) methods to write a good model is to make use of the global constraints. The global constraints are different from the normal constraints in two aspects:

1. they may constraint many (more than two) variables at once;
2. they are implemented using very efficient algorithms, which may take advantage of the problem structure in a better way than the many separate normal constraints.

In order to use a global constraint, first you've to find it in the global constraints' library. Then you've to import in in the model, e.g. in order to use `cumulative` constraint, you've to add the `include cumulative.mzn;` line to the model.

### N-Queens + Global Constraints

• The `alldifferent` global constraint takes an array of variables as an argument and makes sure that no every variable in the array has a different value.
• Assignment: use the `alldifferent` in the N-Queens model.

### Sudoku

• Definition: implement a sudoku solver (see: wikipedia)
• Assignment:
1. Fill missing elements of the model:
```%%%%%%%%%%%
% REMINDER
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% There's something missing here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%
% PARAMETERS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Initial state of the board
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%
% VARIABLES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% You know...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%
% Constraints
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - you know the sudoku rules
% - remember, that you have to preserve the initial state of the board
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solve satisfy;

%%%%%%%%%%%%%%%%%%%%
% OUTPUT EXAMPLE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - puzzle - 2d array of nxn variables
% - N - size of the board, equal S*S
% - S - size of a single sector
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

output [ show(puzzle[i,j]) ++ " " ++
if j mod S == 0 then " " else "" endif ++ if j == N /\ i != N then
if i mod S == 0 then "\n\n" else "\n" endif else "" endif
| i,j in PuzzleRange ] ++ ["\n"];```
2. Input data example:
```  % 0 - field with an unknown value
board = array2d(1..9, 1..9, [
0,  0,  0,  2,  0,  5,  0,  0,  0,
0,  9,  0,  0,  0,  0,  7,  3,  0,
0,  0,  2,  0,  0,  9,  0,  6,  0,
2,  0,  0,  0,  0,  0,  4,  0,  9,
0,  0,  0,  0,  7,  0,  0,  0,  0,
6,  0,  9,  0,  0,  0,  0,  0,  1,
0,  8,  0,  4,  0,  0,  1,  0,  0,
0,  6,  3,  0,  0,  0,  0,  8,  0,
0,  0,  0,  6,  0,  8,  0,  0,  0
]);```

### Magic Sequence

• Definition: a sequence `x0, x1, x2,.., xN` is called magic when (for every `i`) `xi` is equal to the number of `i` occurrences in the sequence. An example of the magic sequence with 5 elements is `2, 1, 2, 0, 0` — at `0` index you can see how many `0` occur in the sequence, at index `1` how many `1` occur in the sequence, etc.
• Ćwiczenia:
1. Fill the model below
2. Use a global constraint (search the library)
```%%%%%%%%%%%%%%
% PARAMETERS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Length of the sequence
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%
% VARIABLES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The sequence itself
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%
% Constraints
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tips:
% - sum(array) return sum of the array's elements
% - you can use bool's like integers
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solve satisfy;

%%%%%%%%%%%%%%%%%%%%%%%%
% EXAMPLE OUTPUT
%%%%%%%%%%%%%%%%%%%%%%%%
% - magic - magic sequence
%%%%%%%%%%%%%%%%%%%%%%%%
output [ "magic sequence = ", show(magic),";\n"];```