Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:constraint_satisfaction_problems [2015/03/23 12:49] kkr [9 Zadania fakultatywne] |
pl:prolog:prolog_lab:constraint_satisfaction_problems [2019/06/27 15:50] |
||
|---|---|---|---|
| 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]] [[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=12818|Thinking as Computation]]. | ||
| - | |||
| - | //Based on [[http://www.cs.toronto.edu/~hector/|Hector's Levesque]] [[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=12818|Thinking as Computation]]//. | ||
| - | |||
| - | Celem ćwiczenia jest wprowadzenie do tematyki CSP i zapoznanie się z możliwościami wykorzystania Prologu do rozwiązywania zadań z ograniczeniami. | ||
| - | |||
| - | ==== - Do przygotowania ==== | ||
| - | Wprowadzeniem teoretycznym jest [[http://www.cs.toronto.edu/~hector/PublicTCSlides.pdf|rozdział 5. w.w. książki: ss. 98-151]]. | ||
| - | |||
| - | |||
| - | ==== - 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 ==== | ||
| - | |||
| - | {{.: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ć ([[http://en.wikipedia.org/wiki/4-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. | ||
| - | |||
| - | {{.: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: {{.: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]] | ||
| - | |||
