Algorytmy rozwiązywania sudoku

Typowa łamigłówka Sudoku

Standardowe Sudoku zawiera 81 komórek w siatce 9 × 9 i ma 9 pól, z których każde jest przecięciem pierwszych, środkowych lub ostatnich 3 wierszy oraz pierwszych, środkowych lub ostatnich 3 kolumn. Każda komórka może zawierać liczbę od jednego do dziewięciu, a każda liczba może wystąpić tylko raz w każdym wierszu, kolumnie i polu. Sudoku zaczyna się od kilku komórek zawierających liczby ( wskazówki ), a celem jest rozwiązanie pozostałych komórek. Właściwe Sudoku mają jedno rozwiązanie. ^{[ potrzebne źródło ]} Gracze i badacze używają szerokiej gamy algorytmów komputerowych do rozwiązywania Sudoku, badania jego właściwości i tworzenia nowych łamigłówek, w tym Sudoku z ciekawymi symetriami i innymi właściwościami.

Istnieje kilka algorytmów komputerowych, które rozwiążą łamigłówki 9 × 9 ( $n$ = 9) w ułamkach sekundy, ale eksplozja kombinatoryczna następuje wraz ze wzrostem $n$ , tworząc granice właściwości Sudoku, które można konstruować, analizować i rozwiązywać wraz ze wzrostem $n$ .

Techniki

Cofanie się

Sudoku (na górze) rozwiązywane przez cofanie się . Każda komórka jest sprawdzana pod kątem prawidłowej liczby, cofa się, gdy występuje naruszenie, i ponownie przesuwa się do przodu, aż zagadka zostanie rozwiązana.

Sudoku zaprojektowane do działania przeciwko algorytmowi brutalnej siły.

Niektórzy hobbyści opracowali programy komputerowe, które rozwiązują łamigłówki Sudoku za pomocą algorytmu śledzenia wstecznego , który jest rodzajem wyszukiwania siłowego . Backtracking to przeszukiwanie w głąb (w przeciwieństwie do przeszukiwania wszerz ), ponieważ całkowicie eksploruje jedną gałąź w celu znalezienia możliwego rozwiązania przed przejściem do innej. Chociaż ustalono, że istnieje około 5,96 x 11 ²⁶ końcowych siatek, algorytm brutalnej siły może być praktyczną metodą rozwiązywania łamigłówek Sudoku.

Algorytm brutalnej siły odwiedza puste komórki w określonej kolejności, sekwencyjnie wpisując cyfry lub wycofując się, gdy okaże się, że liczba jest nieprawidłowa. Krótko mówiąc, program rozwiązałby zagadkę, umieszczając cyfrę „1” w pierwszej komórce i sprawdzając, czy może się tam znaleźć. Jeśli nie ma żadnych naruszeń (sprawdzanie ograniczeń dotyczących wierszy, kolumn i pól), algorytm przechodzi do następnej komórki i umieszcza w niej „1”. Podczas sprawdzania naruszeń, jeśli okaże się, że „1” jest niedozwolone, wartość jest zwiększana do „2”. Jeśli zostanie wykryta komórka, w której żadna z 9 cyfr nie jest dozwolona, algorytm pozostawia tę komórkę pustą i wraca do poprzedniej komórki. Wartość w tej komórce jest następnie zwiększana o jeden. Jest to powtarzane, aż zostanie odkryta dozwolona wartość w ostatniej (81.) komórce.

Animacja pokazuje, jak rozwiązuje się Sudoku tą metodą. Wskazówki układanki (czerwone cyfry) pozostają niezmienione, podczas gdy algorytm testuje każdą nierozwiązaną komórkę z możliwym rozwiązaniem. Zauważ, że algorytm może odrzucić wszystkie wcześniej przetestowane wartości, jeśli stwierdzi, że istniejący zestaw nie spełnia ograniczeń Sudoku.

Zalety tej metody to:

Rozwiązanie jest gwarantowane (o ile łamigłówka jest ważna).
Czas rozwiązania jest w większości niezwiązany ze stopniem trudności .
Algorytm (a tym samym kod programu) jest prostszy niż inne algorytmy, zwłaszcza w porównaniu z silnymi algorytmami, które zapewniają rozwiązanie najtrudniejszych zagadek.

Wadą tej metody jest to, że czas rozwiązywania może być długi w porównaniu do algorytmów wzorowanych na metodach dedukcyjnych. Jeden z programistów poinformował, że taki algorytm może zwykle wymagać zaledwie 15 000 cykli lub nawet 900 000 cykli do rozwiązania Sudoku, przy czym każdy cykl jest zmianą pozycji „wskaźnika”, gdy porusza się on przez komórki Sudoku.

Inne podejście, które również wykorzystuje backtracking, wynika z faktu, że w rozwiązaniu standardowego sudoku rozkład dla każdego pojedynczego symbolu (wartości) musi być jednym z zaledwie 46656 wzorców. W ręcznym rozwiązywaniu sudoku technika ta nazywana jest nakładaniem wzorów lub używaniem szablonów i ogranicza się do wpisania tylko ostatnich wartości. Biblioteka ze wszystkimi możliwymi wzorami może zostać załadowana lub utworzona podczas uruchamiania programu. Następnie każdemu danemu symbolowi przypisywany jest przefiltrowany zestaw z tymi wzorami, które są zgodne z podanymi wskazówkami. W ostatnim kroku, właściwej części cofania się, wzorce z tych zestawów są łączone lub nakładane w sposób niekonfliktowy, aż do trafienia na jedną dopuszczalną kombinację. Implementacja jest wyjątkowo łatwa przy użyciu wektorów bitowych, ponieważ do wszystkich testów potrzebne są tylko bitowe operacje logiczne, zamiast zagnieżdżonych iteracji w wierszach i kolumnach. Znaczącą optymalizację można osiągnąć, jeszcze bardziej redukując zestawy wzorców podczas filtrowania. Testując każdy wątpliwy wzór ze wszystkimi zredukowanymi zestawami, które zostały już zaakceptowane dla innych symboli, całkowita liczba wzorów pozostawionych do cofnięcia jest znacznie zmniejszona.

Podobnie jak w przypadku wszystkich technik sudoku typu brute-force, czas działania można znacznie skrócić, stosując najpierw niektóre z najprostszych rozwiązań, które mogą wypełnić pewne „łatwe” wartości.

Sudoku można skonstruować tak, aby przeciwdziałało cofaniu się. Zakładając, że solver działa od góry do dołu (jak na animacji), łamigłówka z kilkoma wskazówkami (17), bez wskazówek w górnym rzędzie i ma rozwiązanie „987654321” dla pierwszego rzędu, działałaby w opozycji do algorytmu . W ten sposób program spędzałby dużo czasu na „liczeniu” w górę, zanim dotrze do siatki, która spełnia zagadkę. W jednym przypadku programista stwierdził, że program brutalnej siły potrzebował sześciu godzin, aby znaleźć rozwiązanie dla takiego Sudoku (aczkolwiek przy użyciu komputera z 2008 roku). Takie Sudoku można obecnie rozwiązać w mniej niż 1 sekundę przy użyciu wyczerpującej procedury wyszukiwania i szybszych procesorów. ^{[ potrzebne źródło ]}

Stochastyczne metody wyszukiwania / optymalizacji

Sudoku można rozwiązać za pomocą algorytmów stochastycznych (losowych). Przykładem tej metody jest:

Losowo przypisz liczby do pustych komórek w siatce.
Oblicz liczbę błędów.
„Przetasuj” wstawione liczby, aż liczba błędów spadnie do zera.

Następnie zostaje znalezione rozwiązanie zagadki. Podejścia do tasowania liczb obejmują symulowane wyżarzanie , algorytm genetyczny i wyszukiwanie tabu . Wiadomo, że algorytmy stochastyczne są szybkie, choć być może nie tak szybkie jak techniki dedukcyjne. Jednak w przeciwieństwie do tych ostatnich, algorytmy optymalizacyjne niekoniecznie wymagają, aby problemy były logicznie rozwiązywalne, co daje im potencjał do rozwiązywania szerszego zakresu problemów. Algorytmy zaprojektowane do kolorowania wykresów są również znane z tego, że dobrze działają w Sudoku. Możliwe jest również wyrażenie Sudoku jako całkowitoliczbowego programowania liniowego problem. Takie podejście szybko zbliża się do rozwiązania, a następnie może użyć rozgałęzienia pod koniec. Algorytm simplex jest w stanie rozwiązać odpowiednie Sudoku, wskazując, czy Sudoku jest nieprawidłowe (brak rozwiązania). Jeśli istnieje więcej niż jedno rozwiązanie (niewłaściwe Sudoku), algorytm simplex generalnie da rozwiązanie z ułamkowymi ilościami więcej niż jednej cyfry w niektórych kwadratach. Jednak w przypadku prawidłowego Sudoku, same techniki programowania liniowego przed rozwiązaniem pozwolą wydedukować rozwiązanie bez potrzeby wykonywania iteracji simpleksowych. Reguły logiczne używane przez techniki presolve do redukcji problemów LP obejmują zestaw reguł logicznych używanych przez ludzi do rozwiązywania Sudoku.

Programowanie z ograniczeniami

Sudoku można również modelować jako problem spełnienia ograniczeń . W swoim artykule Sudoku jako problem z ograniczeniami Helmut Simonis opisuje wiele algorytmów wnioskowania w oparciu o ograniczenia, które można zastosować do modelowania i rozwiązywania problemów. Niektóre narzędzia do rozwiązywania ograniczeń obejmują metodę modelowania i rozwiązywania Sudoku, a program może wymagać mniej niż 100 linii kodu do rozwiązania prostego Sudoku. Jeśli kod wykorzystuje silny algorytm wnioskowania, włączenie śledzenia wstecznego jest potrzebne tylko w najtrudniejszych Sudoku. Algorytm łączący algorytm oparty na modelu ograniczeń ze śledzeniem wstecznym miałby tę zaletę, że zapewniałby szybki czas rozwiązywania — rzędu kilku milisekund — i możliwość rozwiązania wszystkich sudoku.

Dokładna okładka

Łamigłówki Sudoku można opisać jako dokładny problem z okładką , a dokładniej problem z dokładnym trafieniem . Pozwala to na eleganckie opisanie problemu i sprawne rozwiązanie. Modelowanie Sudoku jako dokładnego problemu z okładki i użycie algorytmu, takiego jak algorytm X Knutha i jego technika Dancing Links „jest metodą z wyboru do szybkiego znajdowania [mierzonego w mikrosekundach] wszystkich możliwych rozwiązań łamigłówek Sudoku”. ^{[ nieudana weryfikacja ]} Alternatywnym podejściem jest zastosowanie eliminacji Gaussa w połączeniu z uderzaniem w kolumny i wiersze.

Relacje i reszty

Niech Q będzie macierzą Sudoku 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, a X reprezentuje ogólny wiersz, kolumnę lub blok. N dostarcza symboli do wypełnienia Q , jak również zestawu indeksów dla 9 elementów dowolnego X. Podane elementy q w Q reprezentują funkcję częściową od Q do N . Rozwiązanie R jest relacją całkowitą , a zatem funkcją . Reguły Sudoku wymagają, aby ograniczenie R do X było bijekcją , więc każde częściowe rozwiązanie C , ograniczone do X , jest częściową permutacją N.

Niech T = { X : X jest wierszem, kolumną lub blokiem Q }, więc T ma 27 elementów. Układ jest albo częściową permutacją, albo permutacją na N . Niech Z będzie zbiorem wszystkich układów na N . Częściowe rozwiązanie C można przeformułować tak, aby zawierało reguły jako złożenie relacji A (jeden do trzech) i B wymagających zgodnych ustaleń:

{\ Displaystyle Q \ xrightarrow {A} T \ xrightarrow {B} Z \ quad {\ tekst {z}} \ quad A; B \ subseteq C.}

Rozwiązanie zagadki, sugestie dotyczące wprowadzenia nowego q $Q$ , pochodzą z zabronionych układów dopełnienie C w Q x przydatne w rachunku relacji to pozostałości :