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.

All files required to solve the assignments are available via the repository, so clone it first and follow the Readme instructions.

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

• Definition: assign colors to the vertices in a graph in the way that no adjacent vertices have the same color. In case of the planar graph you will require only four colors (why? there is a very famous proof of this fact). Otherwise you may need 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]

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.

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

• 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"];