Metody i Algorytmy Sztucznej Inteligencji
Projekt wykonany w ramach przedmiotu w semestrze letnim 2006 / 2007
Wykonał: Władysław Magiera
Opiekun: dr inż. Witold Paluszyński
Wykonanie: 26.06.07 1. Temat projektu
Rozwiązywanie sudoku za pomocą przeszukiwania przyrostowego z nawracaniem.

2. Cel projektu
Celem projektu jest porównanie algorytmów rozwiązujących problemy CSP (Constraint Satisfaction Problem). W znalezionych źródłach ([1], [2]) sugeruje się użycie algorytmów przeszukiwania przyrostowego z nawracaniem (z ang. backtracking), z zastosowaniem następujących heurystyk:
Sprawdzanie wprzód (z ang. forward checking)
Wybór zmiennej najbardziej ograniczonej
Wybór zmiennej najbardziej ograniczającej
Wybór zmiennej najmniej ograniczającej


3. Problem CSP
Z problemem CSP (Constraint Satisfaction Problem) ma się doczynienia w sytuacji, gdy stan składa się z ustalonej ilości zmiennych mogących przyjmować wartości z określonej dziedziny. Ponadto muszą zostać uwzględnione ograniczenia nałożone na poszczególne zmienne. Ograniczenia mogą powstawać podczas przeszukiwania i być efektem zależności pomiędzy wartościami zmiennych. Jest to przykład przeszukiwania z ograniczeniami.
Przykład problemu CSP:
Zadanie pokolorowania wydzielonych obszarów na mapie tak, aby żadne dwa obszary o tym samym kolorze nie miały wspólnej granicy.
Poniżej przedstawiono przykładową mapę przed i po wypełnieniu kolorami. Dana jest ustalona ilość zmiennych (7 obszarów), określona dziedzina (3 kolory) i ograniczenia (sąsiadujące obszary nie mogą mieć tego samego koloru).

4. Zasady rozwiązywania sudoku
Klasyczne sudoku składa się z kwadratowej planszy mającej 9 na 9 pól. Ponadto wyróżnionych jest 9 kwadratów 3 na 3 nie zachodzących na siebie (czyli pokrywających całą przestrzeń). Poniżej przedstawiono pustą planszę do sudoku:

Następnie w niektóre pola zostają wpisane cyfry od 1 do 9 (zwykle od 24 do 30 liczb). Wypełnione pola powinny być symetryczne względem środka planszy, lub jednej z osi symetrii kwadratu.

Zadanie polega na wypełnieniu wszystkich pozostałych pól liczbami od 1 do 9 tak, aby w każdej kolumnie, wierszu i wyróżnionym kwadracie 3 na 3 każda z tych liczb znalazła się dokładnie jeden raz.

Sudoku rozwiązuje się poprzez przeszukiwanie rozwiązań w celu znalezienia właściwego. Dokonuje się tego poprzez analizę możliwości wpisywania poszczególnych wartości do różnych pól (zgodnie z [3], [4]). W celu napisania programu rozwiązującego sudoku używa się przeszukiwania przyrostowego z nawracaniem (przykłady: [5], [6]). Sudoku posiada określoną ilość zmiennych (co najwyżej 81), dziedzinę każdej z nich (liczby od 1 do 9) i określone ograniczenia (wynikające z reguł). Z tego powodu sudoku jest dobrym przykładem do porównania algorytmów rozwiązujących problem CSP.


5. Opis użytych algorytmów
Przeszukiwanie przyrostowe z nawracaniem
Zasada działania algorytmu:
znajdź_pierwszą_wolną_komórkę
if nie_ma_wolnych_komórek
return jest_rozwiazanie (bo cała tablica jest wypełniona)
else
while jest_liczba_do_wstawienia_nie_powodujaca_powtorzen
wstaw_pierwszą_liczbę_nie_powodującą_powtórzeń
uruchom_kolejną_iterację_z_tą_liczbą
if jest_rozwiząnie
return jest_rozwiązanie
else
oznacz_liczbę_jako_powodującą_powtórzenia
end
end
return nie_ma_rozwiązania (bo każda z możliwości prowadzi do sprzeczności
end

Sprawdzanie wprzód
Zasada działania algorytmu:
Różnica: zanim uruchomi kolejną itrację to sprawdza, czy po wstawieniu danej liczby dla każdego pola istnieje chociaż jedna dozwolona wartość do wstawienia.
znajdź_pierwszą_wolną_komórkę
if nie_ma_wolnych_komórek
return jest_rozwiazanie (bo cała tablica jest wypełniona)
else
while jest_liczba_do_wstawienia_nie_powodujaca_powtorzen
wstaw_pierwszą_liczbę_nie_powodującą_powtórzeń
sprawdź_czy_wszędzie_można_coś_wstawić
uruchom_kolejną_iterację_z_tą_liczbą
if jest_rozwiząnie
return jest_rozwiązanie
else
oznacz_liczbę_jako_powodującą_powtórzenia
end
end
return nie_ma_rozwiązania (bo każda z możliwości prowadzi do sprzeczności
end

Wybór zmiennej najbardziej ograniczonej
Zasada działania algorytmu:
Różnica: wstawia wartość w komórce, która ma najmniej dozwolonych liczb.
znajdź_komórkę_o_najmniejsze_liczbie_możliwości
if nie_ma_wolnych_komórek
return jest_rozwiazanie (bo cała tablica jest wypełniona)
else
while jest_liczba_do_wstawienia_nie_powodujaca_powtorzen
wstaw_pierwszą_liczbę_nie_powodującą_powtórzeń
uruchom_kolejną_iterację_z_tą_liczbą
if jest_rozwiząnie
return jest_rozwiązanie
else
oznacz_liczbę_jako_powodującą_powtórzenia
end
end
return nie_ma_rozwiązania (bo każda z możliwości prowadzi do sprzeczności
end

Wybór zmiennej najbardziej ograniczającej
Zasada działania algorytmu:
Różnica: wstawia wartości w komórce, która ma wpływ na jak największą liczbę niewypełnionych pól
znajdź_komórkę_o_największej_liczbie_wolnych_pól
if nie_ma_wolnych_komórek
return jest_rozwiazanie (bo cała tablica jest wypełniona)
else
while jest_liczba_do_wstawienia_nie_powodujaca_powtorzen
wstaw_pierwszą_liczbę_nie_powodującą_powtórzeń
uruchom_kolejną_iterację_z_tą_liczbą
if jest_rozwiząnie
return jest_rozwiązanie
else
oznacz_liczbę_jako_powodującą_powtórzenia
end
end
return nie_ma_rozwiązania (bo każda z możliwości prowadzi do sprzeczności
end

Wybór zmiennej najmniej ograniczającej
Zasada działania algorytmu:
Różnica: wstawia wartości w komórce, która ma wpływ na jak najmniejszą liczbę niewypełnionych pól
znajdź_komórkę_o_najmniejszej_liczbie_wolnych_pól
if nie_ma_wolnych_komórek
return jest_rozwiazanie (bo cała tablica jest wypełniona)
else
while jest_liczba_do_wstawienia_nie_powodujaca_powtorzen
wstaw_pierwszą_liczbę_nie_powodującą_powtórzeń
uruchom_kolejną_iterację_z_tą_liczbą
if jest_rozwiząnie
return jest_rozwiązanie
else
oznacz_liczbę_jako_powodującą_powtórzenia
end
end
return nie_ma_rozwiązania (bo każda z możliwości prowadzi do sprzeczności
end

6. Implementacja i przeprowadzone doświadczenia
W celu przeprowadzenia doświadczeń został napisany program w środowisku Matlab. Obliczano czas rozwiązania sudoku przez poszczególne algorytmy, a także ilość iteracji. Przebadano 40 różnych plansz sudoku (przykłady z [3] i [4]). Wśród nich znajdowało się po 10 plansz zawierających początkowo 26, 28, 29 i 30 wpisanych wartości. Wyniki w każdej z grup zostały uśrednione.


7. Wyniki
Czas rozwiązywania (w sekundach):

Ilość początkowo zapełnionych pól	26	28	29	30
Przyrostowy z nawracaniem	124,5	3,0	5,1	2,8
Sprawdzający wprzód	90,3	1,9	3,6	1,7
Wybór zmiennej najbardziej ograniczonej	6,1	0,1	0,1	0,1
Wybór zmiennej najbardziej ograniczającej	12,6	0,3	0,4	0,3
Wybór zmiennej najmniej ograniczającej	4,9	0,2	0,3	0,1

Ilość iteracji (w tys.)

Ilość początkowo zapełnionych pól	26	28	29	30
Przyrostowy z nawracaniem	249,5	7,5	11,0	6,2
Sprawdzający wprzód	69,6	1,5	2,9	1,4
Wybór zmiennej najbardziej ograniczonej	7,3	0,1	0,1	0,1
Wybór zmiennej najbardziej ograniczającej	61,9	1,5	2,1	1,5
Wybór zmiennej najmniej ograniczającej	24,7	1,2	1,7	0,7

8. Wnioski
Ogólnie czas rozwiązywania i ilości potrzebnych iteracji maleją wraz ze wzrostem ilości początkowo wypełnionych pól. Jest to efekt zmniejszenia wielkości problemu (mniej liczb do wpisania). Wartości średnie uzyskane dla 29 początkowo wpisanych liczb odbiegają od tego trendu. Wynika to z faktu, że zastosowane algorytmy silnie zależą od tego, czy wybrana przez nie wartości jest prawidłowa, czy będą musiały wracać po znalezieniu błędu. W badanej grupie plansz algorytmy zaczynały badać pola, w które należało wpisać duże liczby. Z tego powodu musiały przejrzeć wszystkie poprzednie. Efektem tego jest wydłużony czas pracy.
Najlepiej poradził sobie algorytm wybierający najbardziej ograniczoną wartość. Jest tak, ponieważ wybierał on wartość do wpisania z najmniejszego zbioru, przez co statystycznie rzadziej się mylił. Interesująca jest różnica pomiędzy wyborem zmiennej najbardziej i najmniej ograniczającej. Intuicja może podpowiadać, że opłacalniejsze będzie jak najszybsze ograniczanie (im więcej wolnych pól w zasięgu liczby, tym więcej rozstrzyga na przyszłość). Wyniki przeczą takiemu rozumowaniu. Okazuje się, że najważniejsze jest poprawne wpisywnie wartości na początku. W przypadku zmiennej najmniej ograniczającej największa jest ilość wypełnionych już pól, które ograniczają możliwości wpisywania, przez co zmniejszają prawdopodobieństwo popełnienia błędu.
Zdecydowanie najgorzej wypadł algorytm podstawowy, czyli przyrostwy z nawracaniem w czystej postaci. Jego modyfikacja, polegająca na szukaniu, czy nie pojawiają się pola, na które nie można nic wpisać (sprawdzający wprzód) zwiększa złożość obliczeniową, ale pozwala wcześniej wykryć złe rozwiązania, przez co przyspiesza działanie programu.


9. Użyte źródła i programy
Opis problemu CSP z zasugerowanymi heurystykami:
[1] http://www.mimuw.edu.pl/~awojna/SID/wyklady/przesz_z_wiezami.pdf
[2] http://www.man.poznan.pl/~ameis/PimW8.pdf
Zasady sudoku, wzory plansz:
[3] "Sudoku 2", autor Michael Mepham, wyd. Amber, ISBN-83-241-2291-5
[4] "1001 Sudoku", autor Akira Noe, wyd. Constanti, ISBN:83-923317-0-2
Programy do rozwiązywania sudoku:
[5] "Su Doku Solver" dostępny na stronie http://www.di-mgt.com.au/sudoku.html
[6] "Sudoku Solver" dostępny na stronie http://www.sudoku-solver.com/free.htm
Użyte programy:
1) Matlab ver. 7.1 dostępny dla studentów na serwerze diablo.ict.pwr.wroc.pl
2) MS Paint - fragment środowiska Microsoft Windows XP dostępnego dla studentów