W ramach laboratorium będziemy rozwiązywać standardowe problemy pojawiające się w literaturze dotyczącej programowania z ograniczeniami. Zaprogramowane modele będą następnie ulepszane poprzez stosowanie podstawowych technik modelowania w CSP.

• Treść problemu: w jaki sposób na szachownicy o wymiarach nxn umieścić n hetmanów w taki sposób, by żaden z nich nie mógł zbić innego w jednym ruchu (patrz: wikipedia).
• Ćwiczenia:
  1. Proszę uzupełnić poniższy model problemu n-hetmanów

       %%%%%%%%%%%%% 
       % DZIEDZINA %        
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % miejsce na dziedzinę           %
       % podpowiedź:                    %
       % var 1..N: x; deklaruje zmienną %
       % o dziedzinie 1..N;             % 
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       %%%%%%%%%%%%%%%%
       % OGRANICZENIA %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
       % miejsce na ograniczenia                    %
       % podpowiedź:                                %
       % row_i = row_j (-/+) (j - i)                % 
       % opisuje hetmanów stojących na              %
       % tej samej diagonali, gdzie:                %
       % - i,j - numery kolumn                      %
       % - row_n - pozycja hetmana w n-tej kolumnie %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       solve satify; 
       
       %%%%%%%%%%%%%%%%%%%%%%%%
       % PRZYKŁADOWE WYJŚCIE  %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % - rows[i] pozycja hetmana w i-tym wierszu %
       % - N - liczba hetmanów                     %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       output [ if fix(rows[j]) == i then "H" else "." endif ++
       if j == N then "\n" else "" endif | i,j in 1..N]

• Treść problemu: magicznym ciągiem nazywamy taki ciąg liczb x0, x1, x2,.., xN w którym wartość xi dla dowolnego i jest równa liczbie wystąpień i w tym ciągu. Przykładowy magiczny ciąg o długości 5 to 2, 1, 2, 0, 0 — na 0-wym miejscu znajduje się liczba wszystkich 0 w ciągu, na miejscu o indeksie 1 liczba 1 w ciągu, etc.
• Ćwiczenia:
  1. Zamodelować znajdywanie magicznych ciągów o zadanej długości w MiniZinc.

       %%%%%%%%%%%%% 
       % DZIEDZINA %        
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % miejsce na dziedzinę                 % 
       % - parametr określający długość ciągu %
       % - tablica zmiennych decyzyjnych      %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       %%%%%%%%%%%%%%%%
       % Ograniczenia %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % Podpowiedzi:                                 %
       % - sum(wyrażenie tablicowe) sumuje elementy   %
       % - bool2int(5==5) da w wyniku 1               %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       solve satisfy;
       
       %%%%%%%%%%%%%%%%%%%%%%%%
       % PRZYKŁADOWE WYJŚCIE  %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % - magic - magiczny ciąg     %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      output [ "magiczny ciag = ", show(magic),";\n"];

Jedną z najprostszych metod tworzenia dobrego modelu w programowaniu z ograniczeniami jest korzystanie z gotowych globalnych ograniczeń. Dzięki wyspecjalizowanym algorytmom i implementacji są one w stanie lepiej wykorzystać informacje na temat struktury problemu od ograniczeń na pojedynczych zmiennych. Niektóre z globalnych ograniczeń są nawet w stanie zamodelować dynamiczne zachowanie systemu, np. ograniczenie cumulative uniemożliwia równoczesne wykorzystanie zasobu przez kilka zadań.

• Treść problemu: należy zaimplementować solver sudoku (http://pl.wikipedia.org/wiki/Sudoku)
• Ćwiczenia:
  1. Proszę uzupełnić poniższy model sudoku:

       %%%%%%%%%%%%%%%%%
       % PRZYPOMNIENIE %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % Coś tu jeszcze powinno być.%
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       %%%%%%%%%%%%% 
       % DZIEDZINA %        
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % miejsce na dziedzinę, podpowiedź:  %
       % dwie oddzielne tablice, jedna      %  
       % odpowiedzialna z stan początkowy;  %
       % druga przechowuje zmienne decyzyjne% 
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       %%%%%%%%%%%%%%%%
       % Ograniczenia %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % - constraint alldifferent(tablica zmiennych);  %
       % dodaje ograniczenie, w którym wszystkie        %
       % zmienne z tablicy muszą mieć różną wartość     %
       % - należy zapewnić, aby wartości zmiennych były %
       %   równe odpowiednik polom stanu początkowego   %   
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       
       solve satisfy;
       
       %%%%%%%%%%%%%%%%%%%%%%%%
       % PRZYKŁADOWE WYJŚCIE  %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
       % - puzzle - dwuwumiarowa tablica zmiennych %
       %            o rozmiarze NxN                %
       % - N - rozmiar planszy, równy S*S          %
       % - S - rozmiar sektora planszy             %
       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      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. Poniżej przykładowe dane wejściowe:

       % 0 to pola o nieznanej wartości
     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
     ]);

  3. Poszę zastosować globalne ograniczenie do problemu n-hetmanów i magicznych ciągów.