Lab CSP: Podstawowe problemy

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 satisfy; 
       
     %%%%%%%%%%%%%%%%%%%%%%%%
     % 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: problem kolorowania grafu polega na przyporządkowaniu wierzchołkowom grafu odpowiednich kolorów tak, aby wierzchołki o wspólnej krawędzi miały różne kolory. W najgorszym przypadku (klika) będzie potrzebne tyle kolorów, ile jest wierzchołków. W przypadku grafu planarnego zawsze wystarczą cztery (sławny dowód matematyczny, warto sprawdzić, dlaczego). Twierdzenie o czterech barwach Kolorowanie na angielskim wiki.
• Ćwiczenia:
  1. Proszę uzupełnić poniższy model kolorowania grafu (przykładowe dane wejściowe):

%%%%%%%%%%%%%
% PARAMETRY %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Powinny być wczytane z pliku z danymi.%
% Traktujmy graf jako tablicę booli     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%% 
% DZIEDZINA %        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% miejsce na dziedzinę           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%
% OGRANICZENIA %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% miejsce na ograniczenia                    %
% podpowiedź:                                %
% - warto użyć if'a, by sprawdzić, czy dwa   % 
% wierzchołki są połączone                   %
% - liczba kolorów to może być maksymalny    %
% numer użytego koloru                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%
% CEL  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zminimalizuj użytą liczbę kolorów %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
solve minimize coloursNumber;

%%%%%%%%%%%%%%%%%%%%%%%%
% PRZYKŁADOWE WYJŚCIE  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - coloursNumber - liczba użytych kolorów  %
% - nodes - tablica wierzchołków grafu z    %
%           ich kolorami                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
output [show(coloursNumber), " colours\n",] ++
       [show(nodes[i]) ++ " " | i in 1..nodesNumber]

array[1..2,1..3] of bool: bool_array = [|true, true, true | true, true, true|];

if bool then val1 else val2 endif

/\ -- i, \/ -- lub, != -- różne, == -- równe 

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ń. W MiniZinc, aby korzystać z globalnego ograniczenia, należy je najpierw zaimportować, np. aby korzystać z ograniczenia cumulative należy wcześniej dopisać do kodu linijkę:

include "cumulative.mzn";

• Treść problemu: należy zaimplementować solver sudoku (patrz: wikipedia)
• Ć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);  %
     % globalne 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. Proszę zastosować globalne ograniczenia do problemu n-hetmanów

• 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.
  2. Zastosować globalne ograniczenia.

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