Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:dydaktyka:psi:labs:lab_csp [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +===== LAB: Constraint satisfaction problems =====
 +
 +Laboratorium przygotował Mateusz Baran (2012) na podstawie podręcznika
 +[[http://​www.cs.toronto.edu/​~hector/​|Hectora Levesque]] [[https://​mitpress.mit.edu/​books/​thinking-computation|Thinking as Computation]] ({{http://​www.cs.toronto.edu/​~hector/​PublicTCSlides.pdf|slajdy}}). | 
 +//Based on [[http://​www.cs.toronto.edu/​~hector/​|Hector'​s Levesque]] [[https://​mitpress.mit.edu/​books/​thinking-computation|Thinking as Computation]] ({{http://​www.cs.toronto.edu/​~hector/​PublicTCSlides.pdf|slides}})//​.
 +
 +Celem ćwiczenia jest wprowadzenie do tematyki CSP i zapoznanie się z możliwościami wykorzystania Prologu do rozwiązywania zadań z ograniczeniami.
 +
 +==== - Wprowadzenie ====
 +
 +Problem spełniania ograniczeń (ang. //​Constraing satisfaction problem//) składa się z trzech elementów:
 +  * (skończonego) zbioru zmiennych, których wartości są do znalezienia,​
 +  * skończonych dziedzin dla każdej ze zmiennych (każda zmienna może przyjmować wartość tylko z określonego,​ skończonego zbioru; różne zmienne mogą przyjmować wartości z różnych zbiorów),
 +  * ograniczeń,​ które muszą być spełniane przez odpowiednie podzbiory zmiennych.
 +
 +Ogólną wersję CSP można zapisać w postaci następującego pseudokodu:
 +
 +<​code>​
 +solution(Variable_1,​ Variable_2, ..., Variable_n) :-
 +  domain_1(Varaible_1),​
 +  ...
 +  domain_n(Variable_n),​
 +  constraint_1(Variable,​...,​Variable),​
 +  ...
 +  constraint_m(Variable,​...,​Variable),​
 +</​code>​
 +
 +Pierwsze linie określają dziedziny poszczególnych zmiennych, następne zaś ograniczenia na nie nakładane. **Rozwiązaniem** problemu spełniania ograniczeń jest przypisanie wartości poszczególnym zmiennym. Zadanie może mieć oczywiście wiele rozwiązań,​ dokładnie jedno, lub też nie mieć ich wcale.
 +
 +Przedstawiony pseudokod może posłużyć jako szablon predykatu rozwiązujący dowolny problem programowania z ograniczeniami. Generowałby on po kolei wszystkie możliwe przypisania wartości zmiennym i sprawdzał, czy spełniają ograniczenia. Nie jest to zbyt efektywna metoda. Poniższe przykłady pokażą, jak można projektować szybsze algorytmy dla pewnych problemów.
 +
 +
 +==== - Kolorowanie mapy ====
 +
 +{{ :​pl:​prolog:​prolog_lab:​map_coloring.png|}}
 +
 +Zadanie kolorowania mapy polega na przypisaniu każdemu z regionów jednego z wybranych kolorów w taki sposób, aby żadne dwa sąsiadujące regiony nie miały takiego samego koloru. Można pokazać ([[wp>​Four_color_theorem|twierdzenie o czterech barwach]]), że w przypadku regionów na płaszczyźnie wystarczą cztery kolory.
 +
 +Dla podanej na rysunku mapy można napisać następujący program wyznaczający jej kolorowanie:​
 +<code prolog>
 +solutionMC(A,​B,​C,​D,​E) :-
 +  color(A), color(B), color(C), color(D), color(E),
 +  \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.
 +
 +color(red).
 +color(white).
 +color(blue).
 +</​code>​
 +
 +Porównaj predykat solutionMC z tym ze wstępu. Pierwsza linia określa dziedziny poszczególnych zmiennych (A,​B,​C,​D,​E),​ druga zaś zawiera siedem ograniczeń,​ każde na pewną parę zmiennych.
 +
 +=== Zadania ===
 +  - Uruchom załączony program. Ile różnych kolorowań generuje predykat solutionMC (użyj średnika w SWI-Prologu)?​
 +  - Narysuj inną mapę z sześcioma obszarami tak, aby potrzeba było czterech kolorów do jej pokolorowania. Odpowiednio zmodyfikuj solution tak, aby generował kolorowanie dla twojej mapy.
 +
 +==== - Sudoku ====
 +
 +Jednym z popularnych problemów z ograniczeniami jest łamigłówka Sudoku. Najczęściej jest opisywana w wersji 9x9, jednak dla uproszczenia rozwiążemy wersję 4x4.
 +
 +{{ :​pl:​prolog:​prolog_lab:​sudoku.png|Sudoku 4x4.}}
 +
 +W pola szachownicy 4x4, spośród których niektóre są już wypełnione,​ trzeba wpisać liczby od 1 do 4 w taki sposób, aby spełnione były następujące ograniczenia:​
 +  * liczby w każdej kolumnie są różne,
 +  * liczby w każdym wierszu są różne,
 +  * liczby w każdym z kwadratów 2x2 (NW, NE, SW, SE) są różne.
 +
 +Problem rozwiązywany jest przez predykat sudoku z następującego pliku: {{ :​pl:​prolog:​prolog_lab:​sudoku.pl|}}. Predykat uniq jest jednak niepoprawnie napisany -- powinien on sprawdzać, czy zmienne P, Q, R, S są różne. Przyjrzyj się jednak predykatowi solution z tego pliku. Używa on predykatu uniq nie tylko do testowania, ale także do generowania rozwiązań. Napisz ten predykat tak, aby unifikował zmienne z odpowiednimi liczbami w razie potrzeby.
 +
 +Z poprawnym predykatem uniq predykat solution będzie mógł sprawdzać, czy w poszczególnych wierszach, kolumnach i kwadratach 2x2 są różne liczby. Przetestuj działanie programu wywołując następujący cel:
 +<code prolog>
 +sudoku(
 +1, 4, _, _,
 +_, _, 4, _,
 +2, _, _, _,
 +_, _, _, 3).
 +</​code>​
 +
 +Zmodyfikuj program tak, aby wypisywał komunikat o braku rozwiązań,​ jeśli zagadka ich istotnie nie posiada.
 +
 +=== Przestrzeń rozwiązań ===
 +
 +Spróbujmy się teraz zastanowić,​ czy powyższy program zadziałałby (po odpowiednich,​ łatwych do wyobrażenia modyfikacjach) dla normalnego sudoku 9x9. Na pierwszy rzut oka nie ma powodu, aby było inaczej. Spróbujmy się jednak zastanowić,​ jak długo taki predykat mógłby być liczony.
 +
 +Do porównywania problemów programowania z ograniczeniami wprowadza się pojęcie **przestrzeni rozwiązań**. Jest to zbiór wszystkich możliwych przypisań wartości zmiennym, bez uwzględniania ograniczeń.
 +  * W Sudoku 4x4 każda z 16 zmiennych może przyjmować jedną z 4 wartości, co daje 4<​sup>​16</​sup>​ możliwych przypisań (około 4 miliardy). Taka wartość jest uznawana za małą dla komputerów.
 +  * W Sudoku 9x9 każda z 81 zmiennych może przyjąć jedną z 9 wartości, dając 9<​sup>​81</​sup>​ możliwych przypisań (około 2x10<​sup>​77</​sup>​). Wartość ta jest ogromna.
 +
 +Porównując wielkości przestrzeni rozwiązań,​ powolne działanie analogicznego programu dla Sudoku 9x9 nie byłoby zaskoczeniem.
 +
 +Aby rozwiązać większe Sudoku, potrzeba bardziej wyrafinowanych metod niż proste generowanie rozwiązań i sprawdzanie,​ czy spełniają ograniczenia. Człowiek, mierząc się z Sudoku nigdy tak nie robi. Jedną z najprostszych metod jest korzystanie z **wymuszonych wartości (ang. //forced values//)** -- jeśli w pewnym wierszu, kolumnie lub kwadracie wszystkie zmienne poza jedną mają ustalone wartości, wówczas wartość tej ostatniej można jednoznacznie wyliczyć.
 +
 +
 +==== - Problemy kryptoarytmetyczne ====
 +
 +Problemy kryptoarytmetyczne są klasą zagadek, w których musimy odgadnąć, jakim cyfrom odpowiadają litery umieszczone w pewnym równaniu. Klasycznym przykładem takiego problemu jest SEND+MORE=MONEY:​
 +<​code>​
 +  SEND
 + +MORE
 +------
 + ​MONEY  ​
 +</​code>​
 +Za poszczególne litery (S,​E,​N,​D,​M,​O,​R,​Y) musimy wstawić różne cyfry od 0 do 9 tak, aby przedstawione dodawanie było poprawne. Zmiennym S i M muszą odpowiadać przy tym wartości różne od zera.
 +
 +Uruchom i przeanalizuj działanie poniższego programu:
 +<code prolog>
 +% solution(...) holds for a solution to SEND+MORE=MONEY.
 +solution(S,​E,​N,​D,​M,​O,​R,​Y) :- 
 +   ​uniq_digits(S,​E,​N,​D,​M,​O,​R,​Y),​ S > 0, M > 0, 
 +   Y is (D+E) mod 10, C1 is (D+E) // 10, 
 +   E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
 +   N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
 +   O is (S+M+C100) mod 10, M is (S+M+C100) // 10.
 +
 +% uniq(...) holds if the arguments are all distinct digits.
 +uniq_digits(S,​E,​N,​D,​M,​O,​R,​Y) :-
 +   ​dig(S),​ dig(E), dig(N), dig(D), dig(M), dig(O), dig(R), dig(Y),
 +   \+ S=E, \+ S=N, \+ S=D, \+ S=M, \+ S=O, \+ S=R, \+ S=Y,
 +           \+ E=N, \+ E=D, \+ E=M, \+ E=O, \+ E=R, \+ E=Y,
 +                   \+ N=D, \+ N=M, \+ N=O, \+ N=R, \+ N=Y,
 +                           \+ D=M, \+ D=O, \+ D=R, \+ D=Y,
 +                                   \+ M=O, \+ M=R, \+ M=Y,
 +                                           \+ O=R, \+ O=Y,
 +                                                   \+ R=Y.
 +% The digits
 +dig(0). dig(1). dig(2). dig(3). dig(4). ​
 +dig(5). dig(6). dig(7). dig(8). dig(9). ​
 +</​code>​
 +
 +Pierwsza linia predykatu solution generuje, jak w poprzednich przykładach,​ przypisania wartości do zmiennych, których zgodność z ograniczeniami jest następnie sprawdzana. Zmienne C1, C10 i C100 reprezentują przeniesienie.
 +
 +Zaprezentowany program działa poprawnie, jednak pewnym problemem jest szybkość działania. Oblicz wielkość przestrzeni rozwiązań dla tego problemu. Istnieją jednak pewne metody przyspieszenia działania. Zaprezentujemy dwie z nich.
 +
 +=== Zasada 1. ===
 +
 +Jeśli wartość zmiennej jest w pełni wyznaczona przez określone już wartości innych zmiennych (wartość wymuszona), nie próbuj jej zgadnąć i sprawdzać, czy jest poprawna. Dla przykładu zamiast pisać
 +<code prolog>
 +uniq3(A,​B,​C), ​    % zgaduje wartości A,B,C
 +B is (A+C) mod 10 % sprawdza, czy B spełnia ograniczenie
 +</​code>​
 +lepiej napisać
 +<code prolog>
 +uniq2(A,​C), ​       % zgaduje wartości A i C
 +B is (A+C) mod 10, % wyznacza B
 +uniq3(A,​B,​C) ​      % sprawdza, czy wartości zmiennych są różne
 +</​code>,​
 +gdzie uniq2 i uniq3 sprawdzają (lub generują) odpowiednio dwie lub trzy różne wartości. Przestrzeń rozwiązań drugiego przykładu jest 10 razy mniejsza.
 +
 +=== Zasada 2. ===
 +
 +Nie umieszczaj niezależnej generacji wartości pomiędzy generowaniem i sprawdzaniem innych wartości. Dużo jaśniejszy niż opis na pewno będzie przykład. Zamiast pisać
 +<code prolog>
 +dig(A), dig(B), % generuje A i B
 +dig(C), dig(D), % generuje C i D
 +A > B           % sprawdza ograniczenie na A i B
 +</​code>​
 +lepiej zamienić linię drugą i trzecią:
 +<code prolog>
 +dig(A), dig(B), % generuje A i B
 +A > B           % sprawdza ograniczenie na A i B
 +dig(C), dig(D), % generuje C i D
 +</​code>​.
 +Dzięki temu zabiegowi znowu ograniczamy rozmiar przestrzeni rozwiązań.
 +
 +=== Szybsze rozwiązanie problemu SEND + MORE = MONEY ===
 +Stosując powyższe reguły spróbuj samodzielnie zoptymalizować kod tego problemu.
 +
 +==== - Problem ośmiu hetmanów ====
 +
 +Problem ośmiu hetmanów polega na rozmieszczeniu na szachownicy 8x8 ośmiu hetmanów (królowych) tak, aby żadna nie biła dowolnej innej. Aby to zachodziło,​ wszystkie muszą być w różnych wierszach, kolumnach, lewych oraz prawych przekątnych.
 +
 +Do opisania tego problemu użyjemy ośmiu zmiennych: C<​sub>​1</​sub>,​ ..., C<​sub>​8</​sub>,​ gdzie C<​sub>​i</​sub>​ oznacza kolumnę w której znajduje się hetman z i-tego rzędu. Ten sposób kodowania zapewnia, że żadni dwaj hetmani nie znajdę się w tym samym wierszu. Pozostałe warunki trzeba jednak sprawdzać. Niezajmowanie tej samej kolumny sprawdzić jest prosto. Można również wykazać, że dla pól na tej samej lewej czy prawej przekątnej odpowiednio różnica i suma współrzędnych są stałe.
 +
 +Przestrzeń rozwiązań jest dość duża (8<​sup>​8</​sup>​ > 16 mln), zatem warto od razu zastosować usprawnienia z poprzedniego przykładu. W istocie będziemy generować pozycje dla kolejnych hetmanów i sprawdzać, czy nie biją któregoś z już umieszczonych -- jeśli tak się dzieje, to następuje backtracking i obierane jest inne rozstawienie wcześniejszych hetmanów.
 +
 +<code prolog>
 +% Solve the 8-queens problem.
 +solution(C1,​C2,​C3,​C4,​C5,​C6,​C7,​C8) :-
 +  col(C1), ​
 +  col(C2), \+ cap(2,​C2,​1,​C1),​
 +  col(C3), \+ cap(3,​C3,​1,​C1),​ \+ cap(3,​C3,​2,​C2),​
 +  col(C4), \+ cap(4,​C4,​1,​C1),​ \+ cap(4,​C4,​2,​C2),​ \+ cap(4,​C4,​3,​C3), ​
 +  col(C5), \+ cap(5,​C5,​1,​C1),​ \+ cap(5,​C5,​2,​C2),​ \+ cap(5,​C5,​3,​C3), ​
 +      \+ cap(5,​C5,​4,​C4),​
 +  col(C6), \+ cap(6,​C6,​1,​C1),​ \+ cap(6,​C6,​2,​C2),​ \+ cap(6,​C6,​3,​C3), ​
 +      \+ cap(6,​C6,​4,​C4),​ \+ cap(6,​C6,​5,​C5), ​
 +  col(C7), \+ cap(7,​C7,​1,​C1),​ \+ cap(7,​C7,​2,​C2),​ \+ cap(7,​C7,​3,​C3), ​
 +      \+ cap(7,​C7,​4,​C4),​ \+ cap(7,​C7,​5,​C5),​ \+ cap(7,​C7,​6,​C6),​
 +  col(C8), \+ cap(8,​C8,​1,​C1),​ \+ cap(8,​C8,​2,​C2),​ \+ cap(8,​C8,​3,​C3), ​
 +      \+ cap(8,​C8,​4,​C4),​ \+ cap(8,​C8,​5,​C5),​ \+ cap(8,​C8,​6,​C6), ​
 +           \+ cap(8,​C8,​7,​C7).
 +
 +% The columns
 +col(1). col(2). col(3). col(4). col(5). col(6). col(7). col(8). ​
 +
 +% cap(R1,​C1,​R2,​C2):​ a queen on (R1,C1) can capture one on (R2,C2).
 +cap(R,​_,​R,​_). ​                           % Note the use of the _ here 
 +cap(_,​C,​_,​C). ​                           % and here, too.
 +cap(R1,​C1,​R2,​C2) :- R1-C1 =:= R2-C2.
 +cap(R1,​C1,​R2,​C2) :- R1+C1 =:= R2+C2.
 +</​code>​
 +
 +Uruchom i zrozum powyższy kod.
 +
 +==== - Problemy logiczne ====
 +
 +Problemy logiczne stanowią klasę problemów, w których mamy zestaw wskazówek odnośnie tożsamości osób z pewnej grupy. Najłatwiej zademonstrować to przez przykład:
 +
 +Andrzej, Barbara i Celina ustalają w toku rozmowy, że wykonują trzy różne zawody (lekarz, prawnik, inżynier) i grają na trzech różnych instrumentach (fortepian, flet, skrzypce). Wiedząc, że:
 +  - Barbara jest żoną lekarza,
 +  - prawnik gra na fortepianie,​
 +  - Barbara nie jest inżynierem,​
 +  - Andrzej jest pacjentem skrzypka
 +ustal kto gra na flecie. ​  
 +
 +W przypadku problemów logicznych trzeba się najpierw zastanowić,​ jakie będą zmienne, a jakie ich dziedziny. W powyższym przypadku musimy ustalić osobę wykonującą pewien zawód i grającą na określonym instrumencie,​ zatem rozsądnym wyborem jest:
 +  * określenie zmiennych Lekarz, Prawnik, Inżynier, Pianista, Flecista i Skrzypek,
 +  * określenie wspólnej dziedziny dla zmiennych: {andrzej, barbara, celina}.
 +
 +Do napisania programu potrzeba jeszcze formalnego określenia znaczenia faktów 1 i 4. Należy to zrobić w następujący sposób:
 +  * jeśli x jest żoną y, to \+ x=y (jesteśmy nowocześni i nie sprawdzamy, czy płcie małżonków są różne),
 +  * jeśli x jest pacjentem y, to  \+ x=y oraz y jest lekarzem.
 +
 +Otrzymujemy (po zapisaniu tych warunków) następujący program:
 +<code prolog>
 +% A logic puzzle involving jobs and musical instruments,​
 +solution(Flute) :-
 +
 +   % Distinct occupations and instruments
 +   ​uniq_people(Doctor,​Lawyer,​Engineer),​
 +   ​uniq_people(Piano,​Violin,​Flute),​
 +
 +   % The four clues
 +   \+ barbara = Doctor, ​    % Barbara is married to the doctor.
 +   ​Lawyer = Piano, ​       % The lawyer plays the piano.
 +   \+ Engineer = barbara, ​  % The engineer is not Barbara.
 +   ​Violin = Doctor, ​      % Andrzej is a patient of 
 +   \+ andrzej = Violin. ​    ​% ​   the violinist.
 +
 +% uniq(...) is used to generate three distinct people.
 +uniq_people(A,​B,​C) :- person(A), ​ person(B), ​ person(C),  ​
 +                      \+ A=B, \+ A=C, \+ B=C. 
 +
 +% The three given people
 +person(andrzej). ​  ​person(barbara). ​  ​person(celina).
 +</​code>​
 +
 +Zmodyfikuj program, i sprawdź, czy Barbara wyszła za Andrzeja, czy też wybrała drugą z możliwych opcji.
 +
 +Jednym z problemów pojawiających się podczas rozwiązywania tego typu problemów jest wykrywanie ukrytych zmiennych. Jeśli na przykład trzecie ograniczenie brzmiałoby "​Celina nie jest żoną inżyniera",​ można wprowadzić dodatkowe zmienne Małżonek_Andrzeja,​ Małżonek_Barbary,​ Małżonek_Celiny o odpowiedniej dziedzinie i ograniczane predykatem malzonkowie/​3 określającym możliwe trójki wartości nowych zmiennych (pamiętaj -- jedna osoba może być na raz w związku z co najwyżej jedną inną osobą). Zmodyfikuj odpowiednio program i przetestuj.
 +
 +=== Zagadka Einsteina ===
 +Przeanalizuj problem i jego rozwiązanie (tzw. zagadka Einsteina) przedstawione [[pl:​prolog:​prolog_lab:​reprezentacja_wiedzy#​zagadka_einsteina|tutaj]].
 +Jest to nieco inny sposób reprezentowania wiedzy w tego typu zagadkach logicznych.
 +
 +==== - Harmonogramowanie ====
 +
 +Ostatnim przykładem programowania z ograniczeniami jest harmonogramowanie. Obejmuje ono między innymi przypisywanie ludzi do prac czy spotkań do pokoi. Rozpatrzymy przykład, w którym poszczególnym zajęciom będą przypisywane czasy -- tak, aby bezkonfliktowo mogły się odbyć w jednej sali.
 +
 +Przyjmiemy następujące definicje:
 +  * zmienne: P1, P2, P3, P4, P5, gdzie Pi oznacza czas dla i-tego zajęcia,
 +  * dziedziny: każdy czas jest pewną godziną pewnego dnia; zostanie on zakodowany jako liczba (100xdzień)+godzina,​ na przykład wtorek, 14:00 to 214,
 +  * ograniczenia:​ wszystkie czasy muszą być dostępne (zajęcia nie mogą na przykład odbywać się w nocy), zajęcia nie mogą następować po sobie, zaś w każdym dniu mogą się odbywać najwyżej dwa zajęcia.
 +
 +Następująca funkcja generuje dostępne czasy:
 +<code prolog>
 +% Monday: only 11am and 1pm are available.
 +taken(X) :- X // 100 =:= 1, \+ X=111, \+ X=113. ​
 +% Tuesday: only 1pm and 2pm are available.
 +taken(X) :- X // 100 =:= 2, \+ X=213, \+ X=214. ​
 +% Wednesday: nothing available.
 +taken(X) :- X // 100 =:= 3. 
 +% Thursday: all available, except for 10am, 12pm, and 2pm.
 +taken(410). taken(412). taken(414). ​
 +% Friday: nothing available.
 +taken(X) :- X // 100 =:= 5.
 +
 +uniq_periods(P1,​P2,​P3,​P4,​P5) :-
 +   ​per(P1),​ per(P2), per(P3), per(P4), per(P5),
 +   \+ P1=P2, \+ P1=P3, \+ P1=P4, \+ P1=P5, \+ P2=P3,
 +   \+ P2=P4, \+ P2=P5, \+ P3=P4, \+ P3=P5, \+ P4=P5.
 +  ​
 +per(P) :- day(D), time(T), P is 100*D+T, \+ taken(P).
 +
 +day(1). day(2). day(3). day(4). day(5).
 +
 +time(9). time(10). time(11). time(12).
 +time(13). time(14). time(15). time(16).
 +
 +% This program solves a classroom scheduling problem.
 +solution(P1,​P2,​P3,​P4,​P5) :​-  ​
 +  uniq_periods(P1,​P2,​P3,​P4,​P5), ​      % All different periods.
 +  not_2_in_a_row(P1,​P2,​P3,​P4,​P5), ​    % Not two consecutive hrs. 
 +  not_3_same_day(P1,​P2,​P3,​P4,​P5). ​    % Not three on the same day.
 +
 +not_2_in_a_row(P1,​P2,​P3,​P4,​P5) :-
 +  \+ seq(P1,P2), \+ seq(P1,P3), \+ seq(P1,P4), \+ seq(P1,P5),
 +  \+ seq(P2,P3), \+ seq(P2,P4), \+ seq(P2,P5), \+ seq(P3,P4),
 +  \+ seq(P3,P5), \+ seq(P4,P5).
 +
 +seq(A,B) :- A =:= B-1.
 +seq(A,B) :- A =:= B+1.
 +
 +not_3_same_day(P1,​P2,​P3,​P4,​P5) :-
 +  \+ eqday(P1,​P2,​P3),​ \+ eqday(P1,​P2,​P4),​ \+ eqday(P1,​P2,​P5),​
 +  \+ eqday(P1,​P3,​P4),​ \+ eqday(P1,​P3,​P5),​ \+ eqday(P1,​P4,​P5),​
 +  \+ eqday(P2,​P3,​P4),​ \+ eqday(P2,​P3,​P5),​ \+ eqday(P2,​P4,​P5),​
 +  \+ eqday(P3,​P4,​P5).
 +
 +eqday(A,​B,​C) :- Z is A // 100, Z is B // 100, Z is C // 100.
 +</​code>​
 +
 +Uruchom i przeanalizuj powyższy kod.
 +
 +==== - Zadania fakultatywne ====
 +
 +  * Przepisz szablon predykatu z wprowadzenia na prawdziwy predykat (z wykorzystaniem list oraz [[pl:​prolog:​prolog_lab:​prolog_lab_metaprog|meta programowania]] w Prologu) tak, aby rozwiązywał dowolny, zadany w argumentach problem z ograniczeniami. Twój predykat powinien być wołany w następujący sposób:
 +<code prolog>
 +solution([Variable_1,​ ..., Variable_n],​ [domain_1, ..., domain_n], [constraint_1,​ ..., constraint_m]).
 +</​code>​
 +Przetestuj swój predykat na jednym z opisywanych problemów.
 +  * Przypomnij sobie, ile kolorowań mapy wygenerował predykat solutionMC. Czy dla pewnych ograniczeń wynikających z sąsiedztwa ten predykat może dać dowolną liczbę kolorowań (np. 5)? Uzasadnij swoje przypuszczenia. Napisz predykat generujący wszystkie kolorowania bez przeglądania całego zbioru rozwiązań.
 +rozwiązanie:​
 +<code prolog>
 +% helper for gen1n
 +gen1p(1, [1]).
 +gen1p(N, [N|T]) :- Nm is N-1, gen1p(Nm, T).
 +
 +% generates list [1..N]
 +gen1n(1, [1]).
 +gen1n(N, L) :- gen1p(N, Lp), reverse(Lp,​L).
 +
 +% assigns successive elements from DomainL to V and fills the VT in
 +% similar fashion; it's intented to iterate first argument over [1..1]
 +% to [1,​2..,​n-1,​n,​..,​n]
 +memberizeImpl([],​ _, _).
 +memberizeImpl([V|VT],​ DomainL, [HR|TR]) :-
 +    append(DomainL,​ [HR], DL2),
 +    member(V, DL2),
 +    memberizeImpl(VT,​ DL2, TR).
 +memberizeImpl([V|VT],​ DomainL, []) :-
 +    member(V, DomainL),
 +    memberizeImpl(VT,​ DomainL, []).
 +
 +memberize(Vars,​ Domain) :- memberizeImpl(Vars,​ [], Domain).
 +
 +% checks if imposed inequalities hold for given variables
 +checkMe(_, []).
 +checkMe(FVars,​ [[V1n,​V2n]|T]) :-
 +    nth1(V1n, FVars, V1),
 +    nth1(V2n, FVars, V2),
 +    V1=\=V2,
 +    checkMe(FVars,​ T), !.
 +
 +% generates fresh variables in second argument -- the same number as
 +% in the first
 +freshVars([],​ []).
 +freshVars([_|To],​ [_|Tn]) :- freshVars(To,​ Tn), !.
 +
 +% unifies VH with FVH-th tlement of PDom
 +unif([], [], _).
 +unif([VH|VT],​ [FVH|FVT], PDom) :-
 +    nth1(FVH, PDom, VH),
 +    unif(VT, FVT, PDom).
 +
 +% Vars -- variable to solve, Domain -- common domain for all vars
 +solve(Vars, Domain, Diff) :-
 +    length(Domain,​ DomLen),
 +    gen1n(DomLen,​ Nums), % Nums=[1..DomLen]
 +    freshVars(Vars,​ FVars),!, %len(Vars)=len(FVars),​ FVars -- new,
 +                              %fresh variables
 +    memberize(FVars,​ Nums),
 +    checkMe(FVars,​ Diff),
 +    permutation(Domain,​ PDom), % permutes elements in Domain -- we
 +                               % rely only on equality, so specific
 +                               % values are irrelevant, therefore we
 +                               % can assign them in any order to
 +                               % obtain valid assignment
 +    unif(Vars, FVars, PDom).
 +    ​
 +% use this to test
 +solution :-
 +    solve([A,​B,​C,​D,​E],​ [red, green, blue], [[1,2], [1,3], [1,4], [1,5], [2,3], [3, 4], [4, 5]]),
 +    format('​A = ~w, B = ~w, C = ~w, D = ~w, E = ~w', [A,​B,​C,​D,​E]).
 +
 +</​code>​
 + 
 +  * Stwórz program do rozwiązywania Sudoku 9x9 z wykorzystaniem wartości wymuszonych. Pamiętaj, że nowe wymuszone wartości mogą pojawić się po każdym przypisaniu zmiennej wartości. Sprawdź, jak sobie radzi z łamigłówkami znajdującymi się w Internecie.
 +
 +==== Więcej o kryptoarytmetyce ====
 +  * [[http://​bach.istc.kobe-u.ac.jp/​llp/​crypt.html|Cryptarithmetic Puzzle Solver]]
 +  * [[http://​cryptarithms.awardspace.us/​primer.html|Primer]]
 +
  
pl/dydaktyka/psi/labs/lab_csp.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
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