Metody Sztucznej Inteligencji

TEMAT: Rozwiązywanie Sudoku - poroblem przeszukiwania z ograniczeniami (Constrained Satisfaction Problem, CSP), - porównanie algorytmów BT,FC oraz LA.

Problemy CSP:

• skończony zbiór zmiennych X = {x1, x2, ..., xn}
• dla każdej zmiennej xi skończony zbiór możliwych jej wartości, zwany dziedziną danej zmiennej
• skończony zbiór ograniczeń (constraints), zwanych również więzami, na kombinacje wartości zmiennych, np., jeśli x1 = 5, to x2 musi być parzyste, a kombinacja (x1 = 5, x2 = 8, x3 = 11) jest niedozwolona

Rozwiązaniem problemu CSP jest każda kombinacja wartości zmiennych, która spełnia wszystkie więzy.

Zauważmy, że problemy CSP są w istocie szczególnym przypadkiem ogólnego przeszukiwania w przestrzeni stanów, jeśli potraktujemy zbiór ograniczeń jako specyfikację celu, a przypisywanie wartości zmiennym jako operatory.

Przykłady problemów CSP: kolorowanie grafu lub mapy, problem 8-hetmanów (klasyka), problem SAT (przypisanie wartości 0/1 elementom formuły logicznej spełniające tę formuę), kryptoarytmetyka, projektowanie układów VLSI, tzw. problem etykietowania węzłów pozwalający rozpoznawać obiekty na obrazach po ich konturowaniu, kolejkowanie zadań, planowanie, i wiele innych.

Wiele spośród tych zagadnień stanowią problemy NP-trudne.

Rozwiązanie problemu CSP może istnieć lub nie, bądź może istnieć wiele rozwiązań. Celem przeszukiwania może być znalezienie jednego dowolnego rozwiązania, wszystkich rozwiązań, bądź rozwiązania optymalnego w sensie jakiejś danej funkcji kosztu.

Opis zagadnienia:

W 1979r. w majowym wydaniu "Dell Pencil Puzzles & Word Games" (nr 16), na stronie 6, ukazało się coś niezwykłego -"Number Place". Oto oryginalna instrukcja: "Twoim zadaniem jest wstawić cyfrę w każdą pustą komórkę, tak aby każdy rząd, każda kolumna oraz każdy mniejszy 9-komórkowy kwadrat w obrębie większego kwadratu( jest w nim 9 takich) zawierał każdą cyfrę od 1 do 9. Pamiętaj że żadna z cyfr nie może wystąpić więcej niż raz w każdej kolumnie, rzędzie oraz mniejszym 9-komórkowym kwadracie: to powinno Ci pomóc w rozwiązaniu tych puzzli."

Kto wymyślił tą grę?
Za osobę która wymyśliła SuDoku uważany jest Howard Garns byl on architektem, który ułożyl tą zagadkę umysłową mając 74 lata, szybko upraszczając reguly do tych, które znamy dzisiaj: "Wypelnij kwadrat w taki sposób aby każdy rząd, każda kolumna oraz każdy mniejszy kwadrat 3x3, zawierał wszystkie cyfry od 1 do 9". W kwietniu 1984r. wydawnictwo Nikoli zamieściło "Number Place" w swoim miesięczniku "Monthly Nikolist". Gra została nazwana Suuji Wa Dokushin Ni Kairu ("cyfry musza pozostac samotne") i szybko stała się bardzo popularna w Japonii. Kaji Maki, szef wydawnictwa Nikol, skrócił nazwe do Sudoku - (Su = Cyfra, Doku =Pojedycza) i opatentowal tę nazwę. Jako że popularność rosła, konkurencyjne wydawnictwa, które nie mogły używać nazwy Sudoku, drukowały diagramy pod nazwą "Number Place" lub "nanpure". Nawet dzisiaj wiele japońskich magazynów nazywa "Number Place" po angielsku. W USA i innych miejscach na świecie nazywane jest Sudoku ("pojedyncza cyfra") po japońsku. Dlatego też japończycy używają angielskiego natomiast mówiący po angielsku, japońskiego.

Minimum podanych cyfr prowadzących do unikalnego rozwiazania to 17.

Oto dwa przykłady Sudoku w/g normalnych zasad:

Omówienie algorytmów BT, FC oraz LA:

Algorytm przeszukiwania przyrostowego z nawracaniem - BT (backtracking)

przeszukiwanie wgłab, kazdy krok to ustalenie wartosci jednej zmiennej kolejność przypisywania zmiennych jest ustalona jesli ustalenie kolejnej zmiennej jest niewykonalne bez łamania wiezów nastepuje powrót, tzn. cofnięcie niektórych przypisań

Algorytm sprawdzania wprzód - FC (forward checking) - połączenie przeszukiwania z nawracaniem ze sprawdzaniem spójności więzów.

Przeszukiwanie sprawdza, czy dotychczas przypisane zmienne nie eliminują wszystkich wartości dla którejś z nieprzypisanych zmiennych.
Cofa się, jeśli któraś zmienna nie ma już zadnej dopuszczalnej wartości.

procedure AC3-FC(cv) Q <- {(Vi,Vcv) in arcs(G),i>cv}; consistent <- true; while not Q empty & consistent select and delete any arc (Vk,Vm) from Q; if REVISE(Vk,Vm) then consistent <- not Dk empty endif endwhile return consistent end AC3-FC

Pełen algorytm sprawdzania spójności - LA (look-ahead)

procedure AC3-LA(cv) Q <- {(Vi,Vcv) in arcs(G),i>cv}; consistent <- true; while not Q empty & consistent select and delete any arc (Vk,Vm) from Q; if REVISE(Vk,Vm) then Q <- Q union {(Vi,Vk) such that (Vi,Vk) in arcs(G),i#k,i#m,i>cv} consistent <- not Dk empty endif endwhile return consistent end AC3-LA

Opis implementacji:

Program rozwiązujacy SuDoku napisałem całkowicie samodzielnie w jezyku C++ (kompilator Borland Builder 6.0). Algorytm jakie udało mi się zimplementowć, to przeszukiwanie z nawracaniem (BT) oraz forward checking (FC).

Program ma wprowadzaną macierz sudoku do rozwiązania jako dwuwymiarową tablicę liczb całkowitych o wymiarach 9x9 z wpisanymi wszystkimi wartościami, zera (0) oznaczają miejsca które muszą zostać wypełnione, natomiast wszystkie inne wartości reprezentują liczby już wpisane do sudoku.

np. macierz nr 1 z przykładu powyżej należałoby wpisać następująco:
int m[9][9]={0,0,0,0,0,0,8,0,6,0,0,9,0,0,0,0,0,0,0,0,6,0,4,2,0,0,0, 0,8,0,1,0,0,0,0,0,0,1,0,0,0,0,0,2,0,0,0,0,0,0,9,0,4,0,0,0,0,8,3,0,1,0,0, 0,0,0,0,0,0,9,0,0,2,0,5,0,0,0,0,0,0};

Implementacja algorytmu przeszukiwania z nawracaniem (BT):

Program, jako że dokonuje przeglądu zupełnego, zaczyna wypełniać macierz od pierwszego wolnego miejsca idąc od lewej (1 kolumna) do prawej (9 kolumna), kolejno w pierwszym a pózniej w następnych wierszach. Zawsze pierwszą wstawianą liczbą jest 1, następnie program sprawdza czy jej wstawienie powoduje pojawienie się konfliktu, czyli czy w danym wierszu, kolumnie lub bloku (mniejsza macierz 3x3) już nie wystąpila ta liczba. Jesli nie było konfliktu, algorytm przechodzi do kolejnego wolnego pola, znów zaczynając wypełnianie od 1, jeśli natomiast po wstawieniu cyfry w danym miejscu wystąpił konflikt, wartość zwiększana jest o 1 (czyli po 1 wstawi 2) i tak aż do dopasowania jakiejś liczby. Operacja wstawiania kolejnej liczby powtarzana jest aą do momentu pojawienia się w macierzy wszystkich 81 cyfr (każdej 9 razy). W przypadku gdy program juz spradzi wszystkie 9 cyfr na danej pozycji i żadna nie pasuje (ciagle występował konflikt), oznacza to, że doszedł do punktu z którego nie można osiągnąć rozwiązania przy takim wypełnieniu pierwszych wolnych miejsc w macierzy. Wtedy algorytm cofa się do poprzednio wstawianej liczby (powracanie) i w tym miejscu spróbuje wstawić większą wartość od obecnie tam umieszczonej. Gdy znowu żadna wyższa cyfra nie będzie pasowała cofnie się do jeszcze wczesniejszego pola; jesli natomiast wstawiona nowa cyfra będzie pasowała, program przejdzie dalej do uzupelniania sudoku.

Nawracanie zrealizowałem na dynamicznym wektorze (zawsze wiemy ile liczb w danej macierzy trzeba dostawić: 81-ilość_zapisanych_cyfr_na_początku, ale liczba ta będzie różna dla różnych macierzy) o polach struktury zawierajacej 3 wartości całkowite, wartość wstawionej liczby i jej "współrzedne": wiersz i kolumna w której ją wstawiliśmy

// definicja struktury
struct puste {
int wart,wier,kol;
};

// definicja wektora z informacją o wstawonych liczbach
puste *dodane;    // tablica dynamiczna wszystkich wstawionych przez program liczb
int x=0;    // przetrzymuje info która to już nowa liczba wprowadzana do macierzy
int z=81-wpisane;
dodane=new puste[z];

dodane[x].wart=tab[w][k];    // dodanie do wektora dodanych liczb info o nowej
dodane[x].wier=w;              // liczbie, tylko gdy nie ma konfliktu
dodane[x].kol=k;

Do wektora dodane, program za każdym razem wpisuje nowo wstawioną do sudoku liczbę, jeśli już nie ma jak wpisać kolejnej liczby, wraca się na poprzednią, poprzez odczytanie z tego właśnie wektora nr'u wiersza i kolumny oraz wartości na jakiej skończył podstawianie w danym polu.
Dodawane elementy idą po kolei, ale niektóre pola są już wypełnione.

Implementacja algorytmu sprawdzania wprzód (FC):

Implementacja algorytmu FC jest bardzo podobna do implementacji algorytmu BT. Podobnie jest dokonywane wpisywanie liczb, kolumnami od lewej do prawej, oraz wierszami z góry na dół. zaczynając wstawianie ] od pierwszej "dostępnej liczby t[w][k].d[0]". W ten sam sposób zostało rozwiązane powracanie gdy algorytm stwierdzi, że już nie uda mu się znaleść rozwiązania.

Poniżej przedstawiam cechy własne jakie ma algorytm FC.

Program przed odpaleniem właściwej części algortmu, przygotuje sobie na podstawie wprowadzonej macierzy typu int, maierz 9x9 typu fc (fc - struktura) w której oprócz informacji o zajętych polach, będzie zapisana informacja jakie liczby w danym miejscu mogą być wpisane, oraz jakie liczby mogły być wpisane, ale po ich wstawieniu nie da się rozwiązać macierzy Sudoku. Gdy ma przepisać liczbę która jest w macierzy jako "podana od początku", jako wartosc wpisze 10, natomiast jej prawdziwą wartość wpisze pod pierwszą dostępną do wpisania.

Informacja o liczbach które nie dadzą rozwiązania jest potrzebna do tego, aby w przypadku powrotu, algorytm nie przeliczał od nowa które liczby mogą być wstawione a które nie, tylko przepisywał te mogące się w danej komórce pojawić.

Algorytm po wstawieniu w pozycji [i][j] nowej wartości, dokonuje ograniczenia we wszystkich kolejnych polach w danym wierszu, kolumnie i bloku. Oznacza to, że gdy w miejscu [2][3] algorytm wstawi cyfrę 5, to tym samym dla pól w kolejnych kolumnach w wierszu 2, w kolejnych wierszach w kolumnie 3 i w pozostalych elementach bloku pierwszego, jeśli wśród dostępnych liczb jest cyfra 5, przeniesie ją do liczb "ograniczonych" aktualizując odpowiednio stan liczników.

Analogicznie będzie przebiegało cofnięcie ograniczeń, z tym że przy powrocie, cyfra z liczb ograniczonych dla danego pola, zostanie przeniesiona do liczb "dostępnych - wolnych"

Dzięki tym zabiegom, algorym doskonale wie, jakie cyfry może wstawić, znając także ich ilość (tab[w][k].ile). Po wstawieniu każdej nowej cyfry, algorytm sprawdza pozostałą do wypełnienia część macierzy, aby sprawdzić czy sudoku ma jeszcze szanse zostać rozwiązane. Gdy w którymś z pól licznik tab[w][k].ile jest mniejszy od 1, tzn. że w tamtym miejscu już nie można podstawić żadnej cyfry; tym samym należy cofnąć ostatnie podstawienie i wpisać tam inną liczbę, która nie zablokuje rozwiązania sudoku. Podstawianie wykonujemy, aż do rozwiązania całego sudoku, czyli gdy licznik wpisanych do macierzy cyfr osiągnie wartość 81.

Opis obsługi programu:

Program niestety nie jest wyposażony w bogaty interfejs graficzny, wszystko co robi i wylicza wypisywane jest w okienku tekstowym. W programie mamy 3 kolejne menu wyboru:

I - Menu glowne - czyli jakie mamy opcje do wyboru zaraz po odpaleniu programu:

1. - krok po kroku - pokazane każde podstawienie
2. - szybkie wyliczenie, program wypisze od razu wynik
3. - koniec pracy programu

W tym miejscu wybieramy czy chcemy wykonac algorytm z wypisywaniem na ekran każdego ruchu (podstawienia) jaki zrobi (1), czy żeby wykonał wszystkie obliczenia i na koniec wypisał już uzupełnioną macierz sudoku(2), lub zakończył już swoje działanie(3).

II - Wybór algorytmu jakim chcemy rozwiązać sudoku

1. - BT - przeszukiwanie pełne z powrotami
2. - FC - sprawdzanie w przód

Tak jak wcześniej już wspominałem, opracowałem jedynie 2 algorytmy, algorytm pełnego przeszukiwania z powrotami(1) oraz algorytm sprawdzania w przód (2), więc tylko 2 pozycje w tym menu.

III - Wybór macierzy jaką chcemy uzupełnić.

W zadaniu podane są 2 przykładowe macierze jakie program może wypełnic, pierwsza łatwa, którą oba algorytmy wyliczają bardzo szybko, oraz druga - trudniejsza - której szybkie wyliczanie (bez wypisywania kolejnych kroków) trwa kilkanaście sekund; macierz nr 2 to macierz podana w opisie implementacji

Przykłady działania:

Ponieważ wyniki pracy programu (dla tej samej macierzy) dla trybu "krok po kroku" oraz "szybkiego wyliczenia" są identyczne, wstawiam tu jedynie kolejno wierszami podane macierze do rozwiązania, macierz rozwiązanązaną algorytmem BT oraz macierz rozwiązaną algorytmem FC, a pod rysunkami jeszcze liczbę wykonanych podstawień dla danej macierzy i wybranego algorytmu.

Oprócz tych dwóch przykładowych macierzy, dokonałem również przeglądu czasu wykonywania się zaimplementowanych algorytmów, w zależności od podstawionej macierzy - stopnia jej wypełnienia - czyli ilości liczb jakie mamy podane przed przystąpieniem do rozwiązywania sudoku.

Poniżej przedstawiam tabelkę zawierającą zebrane przeze mnie dane:
czas - czas wykonania danego algorytmu dla macierzy i, iteracji - liczba iteracji danego algorytmu

Jak wynika z powyższej tabelki, w większości przypadków szybciej wykonywał się algorytm BT, jednak w 2 przypadkach (pozycja 8 i 9), szybciej wykonał się algorytm FC. Poniżej załączam macierz z pozycji 8:

Jak widać z załączonego rysunku, macierz szybciej rozwiązana za pomocą algorytmu FC, ma więcej wolnych pół w lewej i górnej części, co oznacza, ze mniej konfliktów występuje w początkowym czasie jej wyliczania. Problemy z rozwiązaniam pojawiają się dopiero gdy przejdziemy do dalszych miejsc, gdzie przez liczniejsze ograniczenia zaczyna brakować nam cyfr do wstawiania i musimy się częsciej i wcześniej wracać. Tu właśnie widać przewagę algorytmu FC, który duzo wcześniej wie (zanim zacznie bezmyślnie podstawiać), które podstawienia nie dadzą pozytywnego rozwiązania, i wstawia dalsze cyfry lub wcześniej dokonuje korekty w dotychczasowym rozwiązaniu. Wystarczy porównać liczbę wykonanych iteracji, żeby sprawdzić jak wile przypadków algorytm FC wykluczył w stosunku do BT, przed znalezieniem rozwiązania.

Wnioski:

Jak widać napisany przeze mnie program (Arek22) działa prawidłowo. Bez problemów potrafi rozwiązać każde podane mu zadanie. Jedynym mankamentem jest to, że niestety nie da się tego zrobić (wprowadzić macierzy do rozwiązania) po odpaleniu programu, a trzeba to zmienić w kodzie źródłowym. Krótko mówiąc program wciąż pozostawia wiele do życzenia jeśli chodzi o szatę graficzną (której w zasadzie nie ma) i opcje.

Jak można wywnioskować z samego opisu, program niestety nie realizuje wszystkich początkowych założeń, ponieważ udało mi się zimplementować jedynie dwa z trzech proponowanych algorytmów (BT i FC).

Jeśli chodzi o implementację pierwszego z nich (BT) nie miałem najmniejszego problemu, program kolejno w kolejnych polach podstawia cyfry zaczynając od 1 kończąc na 9, na bieżąco sprawdzając czy nie powoduje to żadnych konfliktów.

Implementacja kodu dla algorytmu FC była o wiele bardziej pracochłonna i skomplikowana. Najwięcej problemów sprawiło mi zrealizowanie sprawdzania czy wstawiona w danym miejscu cyfra nie blokuje już rozwiązania całego sudoku. Problem ten rozwiązałem wprowadzając dodatkowe tablice, co niby poprawiło sprawność podstawień (było ich dla pierwszej macierzy ok 4 razy mniej, a dla drugiej macierzy ok 15 razy mniej), ale niestety nie poprawiło czasu rozwiązania. Wprowadziłem również dodatkową funkcję na obliczenie czasu, w jakim dokonywane jest rozwiązanie problemu przy użyciu konkretnego algorytmu. Oczywiście sens liczenia czasu działania jest tylko wtedy, gdy algorytmy działają w "trybie ciągłym" (szybkie wyliczenie) i tylko tam wprowadziłem pomiar czasu. Przy liczeniu pierwszej przykładowej macierzy czas wykonania ze względu na małą liczbę iteracji w obu przypadkach jest równy 0, i nie można na tej podstawie porównać czasu obliczeń. Natomiast dla przykładu drugiego, po wykonaniu się algorytmu (BT lub FC) program wypisze na ekranie oprócz ilości iteracji i rozwiązania także czas jakiego potrzebował na całkowite wyliczenie sudoku.

Analizując teraz swój program, dochodze do wniosku, że dużo lepszym rozwiązaniem (szybszym czasowo), byłoby wprowadzenie innej reprezentacji cyfr dostępnych i nie, jakie można w danym polu podstawić.
Zamiast stosować dwa dodatkowe wektory dziewięcio elementowe typu int dla każedego pola, możnaby było wprowadzić jeden wektor tej samej długości, ale o polach typu bool. Umożliwiłoby to nam szybszy przegląd cyfr jakie w danym polu można wstawić a jakie nie (wek[i]==true -> wtedy liczba i jest dostepna), oraz zminiejszyłoby poblemy z cofnięciem ograniczenia na daną cyfrę, gdy należałoby wrócić w poprzednio edytowane pole w celu zmienienia wstawionej tam wartości.

Niestety pomysł ten przyszedł zbyt późno, gdy już miałem napisane oba algorytmy, oraz gdy sprawdziłem jak mało ekonomiczny czasowo jest pomysł zrealizowany na początku.

Mimo wszystko dzięki tym dwóm algorytmom, można zdecydowanie stwierdzić, że algorytm FC jest dużo wydajniejszy od algorytmu BT (potrzebuje dokonać mniejszej liczby iterazcji aby rozwiązać problem), natomiast jest ze względu na swoją złożoność obliczeniową wolniejszy - czasem nawet ok. 4.5 sekundy.
Tylko dla 2 przypadków udało mi się uzyskać lepsze czasy dla algorytmu FC, dla specyficznego typu macierzy, co opisałem w przykładach działania.

Z tego wynia, że o ile przy rozwiązaniu prostszego zadania jakim jest problem n-hetmanów (prostszego bo dokonujemy wyboru czy w danym polu można postawic henmana czy nie, w sudoku dodatkowo zastanawiamy się jaką liczbę należy podstawić) opłaca się zaimplementować algorytmy dokonujące mniej iteracji (FC, LA), o tyle do rozwiązywania sudoku ( gdzie mamy o wiele większą złożoność obliczeniową, ale mniej pól do uzupełnienia - max 81) wystarczy zaimplementować algorytm pełnego przeglądu z powrotami BT, co mało że jest szybsze w wykonaniu to i dodatkowo w moim przypadku również w obliczeniach.

Oczywiście jeśli postaralibyśmy się poprawić część obliczeniową w moim programie, o czym wyżej wspominałem, zapewne dostalibyśmy czasowo lepsze wyniki dla algorytmu FC, mniejsze również od czasu trwania obliczeń dla BT - jednak zanim zabierzemy się za jego implementowanie, należy się zastanowić czy będzie to opłacalne, bo np. dla sudoku uzyskanie lepszego czasu rozwiązania rzedu 3-4 sekund, nie będzie wymierną korzyścią do straconego czasu na napisanie innago algorytmu.

Wykorzystane materiały pomocnicze:

Materiały pomocnicze z jakich korzystałem przy pisaniu obu algorytmów oraz niniejszego sprawozdania (raportu) znalazłem na stronach:

• Strona z informacjami o sudoku - www.sudoku1.pl
• Materiały doktora Witolda Paluszyńskiego na temat metod przeszukiwań
• Strona doktora Romana Bartaka z Czech na temat rozwiązywania problemów CSP
• Materiały doktora Arkadiusza Wojny z UW na temat metod przeszukiwań