5.3. [można] Wyjaśnić dlaczego jako heurystyki przyspieszające wybieramy zmienną najbardziej ograniczającą spośród najbardziej ograniczonych i wybieramy dla tej zmiennej wartość najmniej ograniczającą.

Odp.: Aby zmniejszyć rozmiar drzewa przeszukiwania, wierzchołki o mniejszym rozgałęzieniu przesuwamy do kierunku korzenia. Wybieramy wartość najmniej ograniczającą dla zmiennej bo chcemy trafić na rozwiązanie (a nie sprzeczność).

5.4. [trzeba] Rozważmy problem konstruowania (a nie rozwiązywania) krzyżówek: rozstawienie słów na planszy. Załóżmy, że pola na planszy są pokolorowane na czarny lub szary i mamy listę słów do wybierania i wypełniania do czarnych pól. Sformułuj dokładnie ten problem w dwa sposoby:
a)	Jako generalny problem przeszukiwania. Wybierz odpowiedni algorytm i podaj funkcję użyteczności jeżeli jest potrzebna. Czy lepiej wypełnić na raz jedną literę lub jedno słowo? 
b)	Jako problem przeszukiwania z więzami. Czy zmienne powinno oznaczyć słowa lub litery?
Które sformułowanie jest lepsze? Dlaczego?

Odp.: 
a)	Według mnie wypełnienie całego słowa na raz jest lepsze (niż wypełnienie jednej litery na raz). Jeden z możliwych scenariuszy: 
Stany: Co zostało wypełnione i gdzie.
Cel: Krzyżówka określona jak w zadaniu.
Akcje: Wypełnienie słowa niewykorzystanego.
Algorytm: Przeszukiwanie zachłanne
Funkcja użyteczności: ilość wypełnionych słów, lub nieskończoność w przypadku błędu 

b)	Używamy zarówno zmiennych oznaczających słowa i zmiennych oznaczających litery. 
Używamy jednej zmiennej dla każdego obszaru na rzędzie lub na kolumnie zawierającego pola czarne. Zbiór możliwych wartości dla takiej zmiennej zawiera numery słów mających odpowiednią długość. Używamy jednej zmiennej dla każdego czarnego pola występującego na planszy jako przecięcie obszarów. Zbiorem dopuszczalnych wartości dla takiej zmiennej jest alfabet. Więzy są takiej postaci:
Obszar = ?  Pole = ?

Sformułowanie wykorzystujące więzy jest lepsze, bo w ogólności przeszukiwanie z więzami jest bardziej wyrafinowane i za pomocą więzi możemy wykryć sprzeczności wcześniej. 

5.5. [trzeba] Podaj dokładne sformułowania dla następujących problemów z więzami:
a)	Znalezienie nie pokrywających się miejsc dla mniejszych prostokątów w większym prostokącie.
b)	Planowanie zajęć: Dane są profesorowie, sale, przedmioty i dopuszczalne terminy dla przedmiotów. Każdy profesor ma zbiór przedmiotów, które może prowadzić.

Odp.: 
a)	Dla każdego prostokąta do postawienia używamy dwóch zmiennych oznaczających współrzędne górno-lewego kąta, które są typu liczb rzeczywistych. Dla każdej prostokąta mamy więzy specyfikujące, że ten mały prostokąt leży całkowicie w prostokącie do wypełnienia. Dla każdej pary prostokątów mamy więzy specyfikujące, że one nie pokrywają się.
b)	Dla każdego przedmiotu i używamy trzech zmiennych: Pi (profesor dla i), Si (sala dla i), Ti (termin dla i). Zbiory dopuszczalnych wartości dla tych zmiennych są odpowiednio określone. Mamy następujące więzy:
-	dopuszczalne terminy dla przedmiotów;
-	preferencje profesorów;
-	w każdej sali w każdym terminie może odbywać się tylko jeden przedmiot;
-	w każdym terminie każdy profesor może prowadzić tylko jeden przedmiot.

5.6. [trzeba] Rozwiąż ręcznie następujący przykład krypto-arytmetyki używając przeszukiwania przyrostowego z powracaniem i heurystyk przyspieszających (w tym, wybór zmiennej, wybór wartości zmiennej i sprawdzanie wprzód):
	 TWO
	+TWO
	----
	FOUR

Odp.: 
Przyjmijmy, że mamy następujące więzy, gdzie zmienne P1 i P2 mogą otrzymać wartość 0 lub 1: 
a)	R = (O+O) mod 10
b)	P1 = (O+O) div 10
c)	U = (W+W+P1) mod 10
d)	P2 = (W+W+P1) div 10
e)	O = (T+T+P2) mod 10
f)	F = (T+T+P2) div 10
Kroki:
1)	Zmienne P1 i P2 są najbardziej ograniczone pośród wszystkich zmiennych. Są one równo ograniczające (każda występuje w trzech więzach i jest bezpośrednio związana z 4 innymi zmiennymi). Wybierzmy, np., P1 do rozgałęzienia.
2)	Wartości 0 i 1 dla P1 są równo ograniczające (dla O). Wybierzmy 0. Jako efekty, O może otrzymać wartość w zakresie 0..4 i więzy c) i d) mają prostsze postaci.
3)	 Teraz P2 jest bardziej ograniczona. Wybierzmy P2 do rozgałęzienia.
4)	Wybierzmy wartość 0 dla P2. Wtedy W może otrzymać wartość w zakresie 0..4 i mamy następujące więzy:
a.	R = (O+O) mod 10
b.	(O <= 4)
c.	U = (W+W) mod 10
d.	(W <= 4)
e.	O = (T+T) mod 10
f.	F = (T+T) div 10
5)	Teraz zmienne O i W są najbardziej ograniczone pośród wszystkich zmiennych. O jest bardziej ograniczająca niż W: O występuje w dwóch więzach a W w jednej więzi oraz O jest bezpośrednio związana z dwoma innymi zmiennymi a W z jedną zmienną. Wybierzmy O do rozgałęzienia.
6)	Wśród wartości 0..4 dla O, wartości 0, 2, 4 są mniej ograniczające (1 i 3 powodują sprzeczność dla T). Wybierzmy 0. Jako efekty mamy R = 0 i ((T = 0 i F = 0) lub (T = 5 i F = 1)). (Tu używamy sprawdzenia wprzód.)
7)	Wybierzmy teraz W do rozgałęzienia.
8)	Dla każdej wartości od 0 do 4 dla W otrzymamy jedną wartość dla U i jedno rozwiązanie, np. O = 0, R = 0, T= 0, F= 0, W = 1, U = 2.
9)	Wykonujemy powracanie ...
10)	Rozważmy przypadek kiedy P1 = P2 = 1. Wtedy O i W otrzymują wartości 5..9 i mamy następujące więzy:
a.	R = (O+O) mod 10
b.	(5 <= O <= 9)
c.	U = (W+W+1) mod 10
d.	(5 <= W <= 9)
e.	O = (T+T+1) mod 10
f.	F = (T+T+1) div 10
11)	Teraz zmienne O i W są najbardziej ograniczone pośród wszystkich zmiennych. O jest bardziej ograniczająca niż W: O występuje w dwóch więzach a W w jednej więzi oraz O jest bezpośrednio związana z dwoma innymi zmiennymi a W z jedną zmienną. Wybierzmy O do rozgałęzienia.
12)	Wśród wartości 5..9 dla O, wartości 5, 7, 9 są mniej ograniczające (6 i 8 powodują sprzeczność dla T). Wybierzmy 5. Jako efekty mamy R = 0 i ((T = 2 i F = 0) lub (T = 7 i F = 1)). (Tu używamy sprawdzenia wprzód.)
13)	Wybierzmy teraz W do rozgałęzienia.
14)	Dla każdej wartości od 0 do 4 dla W otrzymamy jedną wartość dla U i jedno rozwiązanie, np. O = 5, R = 0, T= 7, F= 1, W = 1, U = 3.
	 715
	+715
	----
	1530
15)	...

5.8. [warto] Zastosuj procedurę AC-3 dla rysunku na stronie 3 wykładu i pokaż, że za pomocą tej procedury można wykryć sprzeczność dla wartościowania {WA = czerwony, V = niebieski}.

Odp.: 
Ponieważ WA = czerwony, wartość czerwony jest wyeliminowana dla SA i NT.
Ponieważ V = niebieski, wartość niebieski jest wyeliminowana dla SA i NSW.
Wynika stąd, że SA = zielony i wartość zielony jest wyeliminowana dla NT i NSW.
Wynika stąd, że NT = niebieski i NSW = czerwony. 
Ponieważ Q jest sąsiedni z SA, NT, NSW, wszystkie wartości zielony, niebieskie i czerwony są wyeliminowane i mamy sprzeczność.

5.9. i 5.10. [można] Oszacuj złożoność procedury AC-3 i pokaż, że można ulepszyć algorytm aby dostać złożoność O(n^2 d^2).

Odp.: Procedura remove-inconsistent-values ma złożoność O(d^2), czyli usuwanie jednej pary zmiennych (Xi, Xj) z kolejki ma koszt O(d^2). Każda para (Xk, Xi) może być wstawiona do kolejki d razy i jest O(n^2) takich par. Więc, w sumie złożoność jest O(n^2 d^3).
Ulepszenie: Para (Xk, Xi) będzie wstawiona do kolejki tylko kiedy zmniejszony zbiór dopuszczalnych wartości dla Xi powoduje, że niektóre wartości dla Xk będą wyeliminowane. 
Czy w ten sposób dostaniemy złożoność O(n^2 d^2)? Nie mam jeszcze odpowiedzi!

5.11. [warto] Pokaż, że więź postaci A+ B = C można zastąpić poprzez 3 binarne więzy. Uogólnić to i pokazać, że każdy problem z więzami można sprowadzić do problemu z binarnymi więzami.

Wskazówka: Dla A + B = C, użyjmy dodatkowej zmiennej X takiej, że Dom(X) = Dom(A) x Dom(B) i więzów: suma współrzędnych X równa C, A jest pierwszym współrzędnym X, ...
Postępujemy podobnie dla więzów zawierających >= 3 zmienne. Eliminujemy unarne więzy poprzez modyfikowanie dziedzin zmiennych.

5.13. [można] Rozważ następujące puzzle: Jest 5 mężczyzn i każdy mieszka w oddzielnym domu o odmiennym kolorze. Każdy mężczyzna pali odmienny rodzaj papierosów, pije odmienny napój i ma odmiennego zwierzęta. Dane są następujące fakty, a pytaniem jest „w którym domu jest zebra a w którym domu właściciel pije wodę?”.
•	Anglik mieszka w czerwonym domu.
•	Hiszpan ma psa.
•	Norweg mieszka w pierwszym domu po lewej stronie.    
•	Kools są palone w żółtym domu.
•	Mężczyzna palący Chesterfields mieszka obok mężczyzny posiadającego lisa.
•	Norweg mieszka obok niebieskiego domu.
•	Mężczyzna palący Winston ma ślimaki.
•	Mężczyzna palący Lucky Strike pije sok pomarańczowy.
•	Ukrainiec pije herbatę.
•	Japończyk pali Parliaments.
•	Kools są palone w domu obok domu mającego konia.
•	Kawa jest używana w zielonym domu.
•	Zielony dom jest bezpośrednio na prawej stronie szarego (ivory?) domu.
•	Mleko jest używane w środkowym domu.
Dyskutować różne reprezentacje dla tego problemu jako dla problemu z więzami. 
Która reprezentacja jest bardziej odpowiednia? Dlaczego?