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

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"];
en/dydaktyka/csp/lab1.txt · Last modified: 2017/07/17 08:08 (external edit)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0