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

===== Rozgrzewka =====

==== Problem n-hetmanów ====

  * 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: [[http://pl.wikipedia.org/wiki/Problem_o%C5%9Bmiu_hetman%C3%B3w|wikipedia]]). 
  * Ćwiczenia:
    - Proszę uzupełnić poniższy model problemu n-hetmanów <code>
%%%%%%%%%%%%% 
% 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]</code>

<WRAP center round tip 70%>
Przykładowe złożone wyrażenie agregujące:\\
''forall([tablica[i,j] = z | i,j in 1..M, z in 1..N where j < i])''\\
lub równoważnie:\\
''forall(i,j in 1..M, z in 1..N where j < i)(tablica[i,j] = z)''
</WRAP>

==== Kolorowanie grafów ====

  * 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). [[http://en.wikipedia.org/wiki/Four_color_theorem|Twierdzenie o czterech barwach]] [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|Kolorowanie na angielskim wiki]].
  * Ćwiczenia:
    - Proszę uzupełnić poniższy model kolorowania grafu ({{:pl:dydaktyka:csp:csp_coloring_data.dzn.zip|przykładowe dane wejściowe}}): 
<code>
%%%%%%%%%%%%%
% 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]
</code>


<WRAP center round tip 60%>
Definicja tablicy dwuwymiarowej booli:
<code>
array[1..2,1..3] of bool: bool_array = [|true, true, true | true, true, true|];
</code>

Konstrukcja warunkowa:
<code>
if bool then val1 else val2 endif
</code>

Operatory logiczne:
<code>
/\ -- i, \/ -- lub, != -- różne, == -- równe 
</code>
</WRAP>







===== Globalne ograniczenia =====

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ę: <code>include "cumulative.mzn";</code>


==== Sudoku ====

  * Treść problemu: należy zaimplementować solver sudoku (patrz: [[http://pl.wikipedia.org/wiki/Sudoku|wikipedia]])
  * Ćwiczenia:
    - Proszę uzupełnić poniższy model sudoku: <code>
%%%%%%%%%%%%%%%%%
% 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"];
</code>
    - Poniżej przykładowe dane wejściowe: <code>  % 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
]);
</code>
    - Proszę zastosować globalne ograniczenia do problemu n-hetmanów
    

<WRAP center round tip 60%>
Lista globalnych ograniczeń dostępnych w MiniZinc:
http://www.minizinc.org/downloads/doc-latest/mzn-globals.html
</WRAP>


==== Zadanie Dodatkowe: Magiczne ciągi ====

  * 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:
    - Zamodelować znajdywanie magicznych ciągów o zadanej długości w MiniZinc. 
    - Zastosować globalne ograniczenia. <code>

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