Ćwiczenia 20: Przeszukiwanie z nawrotami (ang. back-tracking)

Napisz procedurę, która dla danej liczby $n$ znajdzie jak można obejść szachownicę $n \times n$ skoczkiem.
Skoczek zaczyna obejście w rogu szachownicy, ale może skończyć gdziekolwiek.
Wynikiem powinna być lista par liczb -- kolejnych pozycji skoczka.
Jeżeli rozwiązanie nie istnieje, procedura powinna zgłaszać wyjątek Failure.

Rozwiązania
Napisz procedurę , która dla danej liczby całkowitej $n$ ( $n>1$ ) wyznacza
rozbicie $n$ na sumę minimalnej liczby składników będących liczbami pierwszymi.
(Możesz założyć prawdziwość hipotezy Goldbacha.)
Dany jest (multi-)zbiór kostek domina.
Należy wyznaczyć maksymalny łańcuch, jaki można ułożyć z danych kostek, oczywiście zgodnie z zasadami domina.
Rozwiązanie powinno mieć postać procedury domino : (α * α) list → (α * α) list.
Klocki można obracać.
[XIV OI] Atrakcje turystyczne (uproszczone).
Mamy $n$ miejscowości, ponumerowanych od 1 do $n$ .
Odległości między miejscowościami są dane w postaci (symetrycznej) tablicy liczb całkowitych, o wymiarach $n \times n$ .

Chcemy zwiedzić wszystkie te miejscowości, jednak nie w dowolnej kolejności.
Mamy daną listę ograniczeń postaci $[(i_1, j_1); \dots; (i_k,j_k)]$ .
Ograniczenie $(i,j)$ oznacza, że miasto $i$ musi być zwiedzone przed miastem $j$ .
Możesz założyć, że ograniczenia da się spełnić.

Na początku wyruszamy z miasta 1, a kończymy podróż w mieście $n$ .
Wyznacz minimalną drogę jaką trzeba przejechać, żeby zwiedzić wszystkie miasta.

Informatyka MIMUW

Ćwiczenia 20: Przeszukiwanie z nawrotami (ang. back-tracking)