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: http://pl.wikipedia.org/wiki/Problem_o%C5%9Bmiu_hetman%C3%B3w).
• Ć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]

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ę zamodelować sudoku w MiniZinc korzystając z ograniczenia alldiferent. Aby móc korzystać z ograniczenia należy na początku pliku dopisać include „alldifferent.mzn”;
  2. Proszę rozszerzyć model tak, by obsługiwał jedną z rozszerzonych wersji Sudoku (również opisane na wikipedii), np. Sudoku o rozmiarze innym niż 9×9.
  3. Czy wcześniej opracowany model n hetmanów można usprawnić wykorzystując globalne ograniczenia?
• 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
]);

• Kod wypisujący winik (zmienne w tablicy puzzle, parametry zadeklarowane powyżej kodu wypisującego):

  int: S;
  int: N = S * S;
  set of int: PuzzleRange = 1..N;
  
  ....
  
 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"];

Mówimy, że dany problem przejawia symetrię, jeśli istnieją dla niego rozwiązania symetryczne, tj. takie, które pomimo różnych wartości zmiennych decyzyjnych, są sobie równoważne. Przykładem może być problem kolorowania wierzchołków grafu przedstawiony na poprzednim laboratium — w każdym rozwiązaniu tego problemu możemy bez przeszkód zamienić ze sobą dwa kolory, wszystkie wierzchołki zielono przemalować na niebieskie, niebieskie zaś na zielone. Tak powstałe rozwiązania w niczym nie ustępuje oryginalnemu, niemniej istnienie symetrii niesie ze sobą jedną zasadniczą wadę, mianowicie ogromną przestrzeń rozwiązań, w której wiele stanów jest nadmiarowych. Usunięcie ich prowadzi do znacznie efektywniejszego przeszukiwania naprawdę interesujących rozwiązań.

• Ćwiczenia:
  1. Proszę się zastanowić, jak w prosty sposób można wyeliminować symetrię w problemie kolorowania wierzchołków grafu.
  2. Proszę uzupełnić model kolorowania grafu z poprzednich zajęć o prostą redukcję symetrii.

Jedną z podstawowych zasad programowania z ograniczeniami mówi, że ograniczenia są jak pieniądze — nawet jeżeli jest ich wystarczająco, przydałoby się więcej. Załóżmy, że udało nam się opisać wszystkie ograniczenia konieczne do opisu zadanego problemu (tj. spełnione tylko i wyłącznie przez rozwiązania prawidłowe oraz nie eliminujące żadnych rozwiązań prawidłowych); nie oznacza to wcale, że powinniśmy na nich zaprzestać. Każde kolejne ograniczenie, które dodaje jakąś informację, pozwala na zmniejsze przestrzeni przeszukiwania — solver jest dzięki nim w stanie wcześniej „odciąć” gałęzie przeszukiwania niedające nadziei na przyszłość.

• 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 zadadnej długości w MiniZinc.
  2. Proszę zastanowić się nad nadmiarowymi ograniczeniami, które można dodać do modelu.
  3. Czy dodanie dodatkowych ograniczeń przyśpieszyło rozwiązanie problemu?

Jedną z technik dodawania dodatkowych ograniczeń jest wykorzystanie kilku modeli tego samego problemu równocześnie. Pomimo tego, że wszystkie te modele mogą wskazywać na te same rozwiązania, zawarte w nich ograniczenia w innej kolejności zawężają dziedziny zmiennych. Kombinacja kilku modeli pozwala na ograczenie przestrzeni przeszukiwania z kilku „perspektyw” równocześnie.

1. Ćwiczenie: Proszę połączyć ze sobą dwa intuicyjne modele problemu n hetmanów. Czy skróciło to czas rozwiązywania problemu?

1. Zadanie z gwiazdką: proszę napisać w MiniZinc prosty solver do gry typu saper. Przykładowe dane wejściowe:

% -1 to pola o nieznanej zawartości

w = 6;
h = 6;
game = array2d(1..w, 1..h, [
  -1,-1,2,-1,3,-1,
  -1,-1,-1,-1,-1,-1,
  -1,-1,2,4,-1,3,
   1,-1,3,4,-1,-1,
  -1,-1,-1,-1,-1,3,
  -1,3,-1,3,-1,-1,
    ]);