# AIwiki

## Menu

## Dla Studentów

## HeKatE

## Public

- The KESE workshop
*(EN only)* - Mindstorms
*(archive)*

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.

- 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:
- 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % add 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…`

)

- 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:
- 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]

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:

- they may constraint many (more than two) variables at once;
- 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.

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

- Definition: implement a sudoku solver (see: wikipedia)
- Assignment:
- 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"];

- 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 ]);

- 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:
- Fill the model below
- 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"];