Opis problemu

Sudoku jest łamigłówką polegającą na odpowiednim uzupełnieniu planszy cyframi w taki sposób, by rozwiązanie spełniało narzucone reguły. Najpopularniejszym wariantem jest plansza w rozmiarze 9x9, wypełniona cyframi z przedziału [1,9], podzielona na 9 „podkwadratów” w rozmiarze 3x3. Problem można także uogólnić do rozmiaru NxN i liczb z przedziału [1,N], gdzie należy także zdefiniować sposób podziału planszy na „podkwadraty” / „bloki”.

Aby rozwiązanie łamigłówki mogło być uznane za poprawne, uzupełniona plansza musi spełniać następujące kryteria:

1. W każdym wierszu każda liczba z przedziału [1,N] może wystąpić tylko raz

2. W każdej kolumnie każda liczba z przedziału [1,N] może wystąpić tylko raz

3. W każdym „podkwadracie” / „bloku” każda liczba z przedziału [1,N] może wystąpić tylko raz

W stanie początkowym część pól na planszy jest uzupełniona, a wpisanie pozostałych cyfr tak, aby spełniały powyższe założenia, stanowi istotę rozwiązywanego problemu. Ilość uzupełnionych na początku cyfr warunkuje to, czy sudoku posiada jedno dopuszczalne rozwiązanie, czy wiele różnych, spełniających kryteria. Dla planszy 9x9 minimalna ilość uzupełnionych cyfr w stanie początkowym to 17, dla mniejszej ilości nie istnieje jednoznaczne rozwiązanie. Dodatkowo należy pamiętać, że stan początkowy również musi spełniać kryteria poprawnego rozwiązania.

Przykładowe plansze 9x9 w stanie początkowym:

Wykazano, że problem znalezienia poprawnego rozwiązania sudoku jest problemem NP-zupełnym – można do niego sprowadzić inne problemy z klasy NP, takie jak problem SAT czy 3-kolorowanie grafu. W praktyce oznacza to, że nie istnieje algorytm działający w czasie wielomianowym, który sprawdzałby wszystkie możliwe kombinacje rozwiązań.

Przegląd stanu wiedzy

Rozwiązywanie oparte na regułach

Do rozwiązywania problemu sudoku stosowano już wiele różnych podejść. Jednym z nich jest rozwiązywanie takich plansz, jakie mogą zostać rozwiązane przez człowieka - można je rozwiązać opierając się na logicznych regułach. Zasada jest taka, że reguły te powinny opierać się na aktualnie dostępnym stanie, bez prób i błędów. Nie jest to precyzyjne kryterium, więc istnieją spory co do tego, które plansze można w taki sposób rozwiązać, a które nie. Wielu ludzi zajmuje się wymyślaniem takich reguł rozwiązywania i stosowaniem ich do pisania solverów SuDoku. Ta gałąź badań nad łamigłówką jest nam przydatna do jednego z pomysłów na rozwiązywanie prefixów w algorytmie hierarchicznym, jednak w ogólności dotyczy tylko wąskiego podzbioru planszy i nie jest wystarczająca do ogólnego zadania rozwiązywania SuDoku, jakie przed sobą postawiliśmy.

Backtracking

Backtracking to algorytm sprawdzający wszystkie możliwe rozwiązania. Jeżeli próbując jakiegoś rozwiązania natknie się na sprzeczność, powraca do orginalnego rozwiązania. Algorytm ten nie jest ciekawy algorytmiczni, ale jest stosowany w wielu solverach sudoku rozwiązywalnych przez człowieka i może przydać się w naszej pracy przy rozwiązywaniu prefiksów w algorytmie hierarchicznym.

Constraint programming

Problem sudoku można potraktować również jako problem "z ograniczeniami". Zastosowanie tej strategii do rozwiązywania plansz rozwiązywalnych przez człowieka jest omówione w następującej pracy: http://4c.ucc.ie/~hsimonis/sudoku.pdf

Rozwiązania stochastyczne

Do rozwiązywania problemu sudoku stosowano z różnym powodzeniem wiele metod stochastycznych. Pozwalają one na rozwiązywanie ogólnych plansz, nie tylko tych, które człowiek może rozwiązać. Częściowy przeglą metod stochastycznych zastosowaniych w rozwiązywaniu sudoku można znaleźć w:

• Rhyd Lewis, Metaheuristics can solve sudoku puzzles, Journal of Heuristics, v.13 n.4, p.387-401, August 2007 . doi>10.1007/s10732-007-9012-8 (http://www.inf.utfsm.cl/~mcriff/Tesistas/Games/sudoku.pdf)
• A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, E. Ugboh. A Comparative Evolutionary Models for Solving Sudoku. Automation, Control and Intelligent Systems. Vol. 1, No. 5, 2013, pp. 113-120. doi: 10.11648/j.acis.20130105.13 (http://article.sciencepublishinggroup.com/pdf/10.11648.j.acis.20130105.13.pdf)

Opis algorytmu

Algorytm podstawowy

Algorytmem wyjściowym, który będziemy adaptowali dla naszego rozwiązania jest algorytm genetyczny. W podstawowej wersji tego algorytmu mamy do czynienia z populacją możliwych rozwiązań, która jest poddawana procesowi ewolucji w celu znalezienia optymalnego rozwiązania.

Podstawowymi pojęciami w algorytmie genetycznym są:

• genotyp - posiada go każdy osobnik. Jest to kodyfikacja rozwiązania, który dany osobnik reprezentuje.
• funkcja oceny (fitness function) - dla danego genotypu określa ona jakość rozwiązania problemu zakodowanego za jego pomocą
• mutacja - proces tworzenia nowych osobników polegający na zmianie losowego genu w genotypie niektórych osobników
• krzyżowanie - proces tworzenia osobnika, który ma wejść w skład następnego pokolenia, z wykorzystaniem genów osobników z pokolenia aktualnego
• selekcja - proces wyboru osobników, którzy zostaną wykorzystani w procesie tworzenia kolejnego pokolenia, zazwyczaj oparty na funkcji oceny

Przebieg algorytmu genetycznego

1. Wygenerowanie początkowej populacji
2. Selekcja osobników, którzy wezmą udział w procesie reprodukcji
3. Reprodukcja - proces tworzenia nowego pokolenia osobników przy wykorzystaniu mutacji i krzyżowania
4. Odrzucenie osobników o najgorszej funkcji oceny w celu utrzymania stałej wielkości populacji
5. Jeżeli osiągnięty został warunek stopu, osobnik w populacji o największej funkcji oceny jest znalezionym rozwiązaniem, w przeciwnym razie powracamy do 2.

Adaptacja algorytmu genetycznego do problemu Sudoku

Zastosowanie algorytmu genetycznego do problemu Sudoku wymaga określenia pewnych zagadnień charakterystycznych dla problemu.

Sposób kodowania

Pierwszym ważnym zagadnieniem jest sposób zakodowania rozwiązania w postaci genomu. Rozważamy tutaj dwa podejścia:

• pierwsze podejście to bezpośrednie zakodowanie planszy jako tablicy cyfr 1-9. Jest ono proste i bardzo naturalne, może jednak nie być optymalne przy wyznaczaniu funkcji oceny, gdyż nie uwzględnia w bezpośredni sposób uwarunkowań problemu (warunki nałożone na kolumny, wiersze i kwadraty). Można rozszerzyć ten sposób kodyfikacji o cyfrę 0, symbolizującą brak wpisanej cyfry w wypadku, gdy konieczna będzie reprezentacja częściowych rozwiązań.
• Drugie podejście polega na utrzymaniu trzech struktur przestawiających rozwiązanie pod kątem kolumn, wierszy i kwadratów. Dla każdego z tych "wymiarów" problemu, można utrzymać odpowiednią mapę. Przykładowo dla kolumn otrzymujemy mapę o 9 wpisach, odpowiadających zawartości kolejnych 9 kolumn. Reprezentacja ta pozwala na wygodne obliczanie sensownych funkcji oceny, może jednak być kosztowna w utrzymaniu w przypadku mutacji czy krzyżowania, trzeba bowiem uaktualniać wszystkie trzy struktury w razie zmian.

Z wymienionych rozwiązań skłaniamy się do rozwiązania pierwszego ze względu na jego prostotę i naturalność. Pozwoli ono również na łatwiejsze wprowadzenie podejścia hierarchicznego, poprzez dowolne dzielenie planszy na fragmenty.

Funkcja oceny

Funkcja oceny to bardzo istotne zagadnienie, jej definicja wpływa na jakość otrzymywanych rozwiązań oraz zbieżność algorytmu. Dlatego chcemy przetestować kilka z różnych funkcji, szczególnie że nie jest to w tym wypadku zagadnienie oczywiste. Nie ma narzucającej się naturalnej funkcji oceny, jest jednak do sprawdzenia kilka ciekawych możliwości.

• Sprawdzenie sumy liczb w kolumnach i wierszach. Suma liczb w każdej kolumnie i każdym wierszu musi być równa 45. Jako funkcję oceny możemy ustalić odległość danego rozwiązania od tego optimum.
• Sprawdzenie ilości pomyłek w wierszach i kolumnach. Dla każdego wiersza i każdej kolumny można wyliczyć ile powtórzeń w niej występuje i karać za każde takie powtórzenie.

Niezależnie od wyboru funkcji oceny należy uwzględnić początkowe cyfry wpisane w sudoku. Rozwiązanie, które modyfikuje jedną z takich cyfr jest niewątpliwie nieprawidłowe. Zdecydowaliśmy, że uwzględnimy ten fakt nie dopuszczając do sytuacji w której wartości tych pól zostaną naruszone, tj. po krzyżowaniu i mutacji wartości tych pól są aktualizowane.

Mutacja

Najprostszą wersją mutacji jest w naszym przypadku zamiana losowej liczby na inną. Mutacja taka może jednak bardzo często zmieniać rozwiązanie na gorsze. Lepszym podejściem wydaje się być pewna permutacja istniejącego rozwiązania. Dobrymi podejściami do wypróbowania wydają się tu być:

• Zamiana losowych dwóch liczb na planszy
• Zamiana całych losowo wybranych elementów (kolumn, wierszy lub kwadratów) - przykładowo wybranie dwóch kolumn i zamiana ich miejscami.

Krzyżowanie

Krzyżowanie polegać powinno na wymianie fragmentów planszy. Rozsądnym wydaje się być, podobnie jak w przypadku mutacji, wymienianie całych elementów (kolumn, wierszy lub kwadratów) w celu mniejszego zaburzania struktury rozwiązania. Przy krzyżowaniu podział powinien więc przebiegać wzdłuż granic kolumn, wierszy lub kwadratów.

Selekcja

Najrozsądniejszym sposobem selekcji, jaki można wybrać wydaje się być selekcja turniejowa.

Podejście hierarchiczne

Dodatkową, niezwykle istotną modyfikacją, którą chcemy wprowadzić do naszego algorytmu jest optymalizacja hierarchiczna. Podejście to pozwala na zmniejszenie złożoności zagadnienia poprzez rozbicie problemu na mniejsze części. W naszym przypadku będzie ono polegać na tym, iż w każdej iteracji algorytmu będziemy mieć zbiór rozwiązań pewnego prefiksu - części planszy Sudoku a następnie dla każdego A z tych częściowych rozwiązań innym algorytmem będziemy rozwiązywać pozostałą część planszy, szukając sufiksu B, dla którego wartość funkcji oceniającej f(AB), gdzie AB to plansza skonstruowana z prefiksu i sufiksu, jest największa. Jako wartość funkcji oceniającej f* dla A, z której korzystamy w dalszych krokach algorytmu genetycznego przyjmujemy f*(A) = max(B) f(AB).

Wybór prefiksu

• Zbiór kwadratów o największym ilości początkowych cyfr - powinno to ułatwić znalezienie rozwiązań dla prefiksów - będą to miejsca, gdzie najwięcej rozwiązań łatwo wykluczyć. Wada to możliwy brak uwzględnienia wierszy i kolumn
• Wybór "krzyża" - prefiks to środkowy kwadrat oraz kwadraty w lewo, w górę, w prawo i w dół
• Wybór "pasma" - 3 kwadratów w kolumnie lub wierszu (przykładowo 3 pierwsze kolumny)
• Wybór "L" - 3 kwadraty w kolumnie i dodatkowe dwa w wierszu

Innym możliwym podejściem do wyboru prefiksu jest rozwiązanie fragmentu planszy za pomocą metod logicznych, tj.:

• wypełnianie pól na przecięciu wiersza i kolumny (brakujące wartości w wierszu i kolumnie)
• wypełnianie pól w każdym z 9 kwadratów 3x3 (brakujące wartości w kwadracie)

Dodatkowo, jeżeli wypełnienie pola metodą logiczną nie jest jednoznaczne, możemy wybrać losowo jedną z możliwości i kontynuować kolejne iteracje wypełniania. Losowy wybór może być błędny, ale ma on szansę zostać poprawiony przez algorytm genetyczny.

Warianty algorytmu hierarchicznego

Przy założeniu wypełniania prefiksu metodą logiczną rozważamy trzy podejścia:

• podejście proste - wypełnianie logiczne jest realizowane na kilka kroków od wejściowej planszy, tylko raz przed rozwiązywaniem sufiksu
• podejście iteracyjne - wypełnianie logiczne jest zastosowane raz, ale po przejściu algorytmu genetycznego wybieramy najlepsze rozwiązania, patrzymy na ich prefiksy, dokładamy do nich część prefiksów oryginalnych i na takiej populacji wykonujemy algorytm genetyczny
• podejście iteracyjne z dodatkowymi krokami - podejście analogiczne jak poprzednie ale za każdą iteracją algorytmu hierarchicznego dodatkowo wykonujemy na najlepszych prefiksach parę kroków algorytmu wypełniania logicznego.

Algorytm rozwiązywania sufiksu

Dla rozwiązania sufiksu został zastosowany algorytm genetyczny.

Testy

Wstęp

Podstawową wartością, którą będziemy chcieli mierzyć w przypadku różnych wersji algorytmu jest czas (rozumiany jako liczba kroków algorytmi) po jakim zostaje znalezione co najmniej jedno poprawne rozwiązanie problemu wyjściowego. W szczególności rozwiązanie takie może nie zostać znalezione w akceptowalnym czasie, np. ze względu na źle dobrane parametry algorytmu.

Tam gdzie to możliwe, mierzony będzie nie rzeczywisty czas, ale liczba iteracji algorytmu wymagana do znalezienia rozwiązania. Ze względu na stochastyczną naturę algorytmu, liczba iteracji wymaganych do znalezienia rozwiązania nie jest jednoznacznie zależna od parametrów algorytmu i wyjściowego problemu, więc w każdym przypadku algorytm musi zostać wykonany wielokrotnie, i porównywać będziemy średnią liczbę iteracji oraz odchylenie standardowe.

Parametry

Możemy porównać cztery wersje algorytmu: hierachiczną prostą, hierarchiczną iteracyjną, hierarchiczną iteracyjną z krokami i klasyczną (prosty algorytm genetyczny).

Ww wszystkich przypadkach istnieje kilka podstawowych parametrów, które możemy modyfikować:

• rozmiar populacji
• prawdopodobieństwo mutacji
• początkowe wypełnienie planszy

Ponadto, jakość algorytmu silnie zależy od:

• wybranej funkcji oceny - w tym przypadku do sprawdzenia jest wiele wariantów
• sposobu krzyżowania - wybór fragmentu planszy
• rodzaju mutacji

Dodatkowo, w przypadku algorytmu hierarchicznego, kluczowy jest podział na prefix i suffix.

W przypadku logicznego generowania prefiksu, możemy modyfikować głębokość wypełnienia planszy i sterować pewnością wyboru wartości na wypełnianym polu. Dzięki temu możemy porównać różne sposoby logicznego wypełniania planszy.

Dane testowe

Do wykonania testów wykorzystane zostaną plansze o różnym początkowym wypełnieniu. Generator pozwala nam stworzyć początkowe plansze o dowolnym wypełnieniu, więc testy będą przeprowadzane dla wypełnień od około 10% do 90% planszy.

Podstawowym zestawem testowym będzie zestaw:

• plansza o określonym wypełnieniu
• rozmiar populacji (parametr algorytmu)
• prawdopodobieństwo mutacji (parametr algorytmu)
• funkcja oceny algorytmu (suma liczb lub ilość pomyłek)

Algorytmy zostaną przetestowane kilkukrotnie przy użyciu każdego zestawu, dla ustalonych pozostałych parametrach (sposobie krzyżowania, rodzaju mutacji). Tam gdzie to możliwe, wyniki zostaną przedstawione w formie średniej liczby iteracji, odchylenia standardowego, wyniku funkcji oceny oraz najlepszego wyniku dla każdego z zestawów.

Dla zestawów dających najlepsze wyniki przeprowadzone zostaną testy przy zmiennym sposobie krzyżowania i rodzaju mutacji, oraz dla algorytmu hierarchicznego sposobie podziału na prefix i suffix. Będzie to miało na celu określenie najlepszej dostępnej kombinacji parametrów.

Otrzymane wyniki

Należy zaznaczyć, ze przetestowana została większa ilość parametrów niż zaprezentowana poniżej, jednakże spora część wyników okazała się nieinteresująca. Część rozwiązań okazało się niestety niezbieżnych: warianty mutacji polegające na podmianie całych fragmentów planszy czy crossover na granicy kwadratów. Crossover na granicy kolumn jest całkowicie analogiczny do crossoveru na granicy rzędów, więc został wykorzystany jedynie ten drugi. Ewaluacja za pomocą sumy była zbieżna, ale dawała znacznie gorsze wyniki niż ewaluacja za pomocą ilości błędów.

Wyniki dla algorytmu genetycznego

Poniższe zestawienie przestawia przebiegi algorytmu dla ustalonego wypełnienia planszy 33/81, przy populacji o rozmiarze 200, i maksymalnej liczbie kroków algorytmu genetycznego wynoszącej 400. Wykorzystywana funkcja oceny zliczała błędy na planszy.

Zmieniane było prawdopodobieństwo mutacji, od 0 do 1, co 0.1.

Poniższy wykres przedstawia zbieżność algorytmu w zależności od początkowego wypełnienia planszy. Prawdopodobieństwo mutacji zostało ustalone na 0.8. Reszta parametrów jest taka sama jak w poprzednim przypadku.

Wyniki dla algorytmu hierarchicznego prostego

Algorytm hierarchiczny prosty - prawdopodobieństwo mutacji, minimum błędu i średni błąd w populacji

Algorytm hierarchiczny prosty - wypełnienie planszy, minimum błędu i średni błąd w populacji

Wyniki dla algorytmu hierarchicznego iterowanego

Algorytm hierarchiczny iterowany - prawdopodobieństwo mutacji, minimum błędu i średni błąd w populacji

Algorytm hierarchiczny iterowany - wypełnienie planszy, minimum błędu i średni błąd w populacji

Wyniki dla algorytmu hierarchicznego iterowanego z krokami

Algorytm hierarchiczny iterowany z krokami - prawdopodobieństwo mutacji, minimum błędu i średni błąd w populacji

Algorytm hierarchiczny iterowany - wypełnienie planszy, minimum błędu i średni błąd w populacji

Referencje

• Reynolds, Robert G. "An introduction to cultural algorithms." Proceedings of the third annual conference on evolutionary programming. Singapore, 1994. (http://www.danielcondurachi.ro/podpress_trac/feed/10/0/cult94.pdf)
• A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, E. Ugboh. A Comparative Evolutionary Models for Solving Sudoku. Automation, Control and Intelligent Systems. Vol. 1, No. 5, 2013, pp. 113-120. doi: 10.11648/j.acis.20130105.13 (http://article.sciencepublishinggroup.com/pdf/10.11648.j.acis.20130105.13.pdf)
• Rhyd Lewis, Metaheuristics can solve sudoku puzzles, Journal of Heuristics, v.13 n.4, p.387-401, August 2007 . doi>10.1007/s10732-007-9012-8 (http://www.inf.utfsm.cl/~mcriff/Tesistas/Games/sudoku.pdf)
• de Jong, E. D., Thierens, D., & Watson, R. A. (2004). Hierarchical genetic algorithms. Parallel Problem Solving from Nature: Proceedings of the 8th International Conference, 232–241 (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.7168&rep=rep1&type=pdf)