Rozwiązywanie Sudoku
Uwaga może odebrać przyjemność z gry!
W 2005 roku świat zwariował na punkcie Sudoku. Zasady łamigłówki są bardzo proste,
wypełnij diagram 9x9 tak, aby w każdym wierszu, w każdej kolumnie i w każdym
wyznaczonym kwadracie 3x3 znalazło się po jednej cyfrze od 1 do 9. Plansze do gry
konstruowane są w taki sposób, by umożliwić znalezienie jedynego rozwiązania bez
konieczności zgadywania żadnej z cyfr. Podstawy rozwiązywania, opisy rozszerzeń gry,
rozgrywanych zawodów i inne ciekawostki dotyczące Sudoku znajdą Państwo na Wikipedii.
W artykule chciałbym zaprezentować matematyczne podejście do problemu.
Jaką cyfrę należy wpisać w zaznaczone pole? Patrząc na diagram od razu widzimy łatwiejsze
pola do uzupełnienia, ale można wypełnić i to na tym etapie gry.
Reguła 1. Do uzupełnienia tego pola skorzystamy z zasady, że cyfry nie mogą się powtarzać.
Dla wiersza, kolumny i kwadratu w którym znajduje się nasze pole wypisujemy pozostałe do
uzupełnienia cyfry, a następnie wyznaczamy cześć wspólną tych trzech zbiorów. Jeśli iloczyn
zbiorów ma jeden element, to jest to poszukiwana cyfra. Tym sposobem udało nam się
wyznaczyć dość groźnie wyglądające pole.
1
Reguła 2. Co jednak, gdy dla wszystkich jeszcze pustych pól mamy więcej niż jedną
potencjalną odpowiedź wyznaczoną regułą 1. Wtedy korzystamy z zasady, że każda z cyfr
musi się znaleźć w wierszu, kolumnie i kwadracie. Dlatego, pomimo że reguła 1 wskazuje na
więcej niż jedną możliwość, możemy wyszukać pola, które jako jedyne w wierszu, kolumnie
czy kwadracie mają w zbiorze możliwych rozwiązań daną cyfrę. Mówiąc bardziej
precyzyjnie, dla każdego wiersza, kolumny, kwadratu i dla każdej z pozostałych w nich do
uzupełnienia cyfr możemy wyznaczyć zbiór pól, które mogą zawierać daną cyfrę zgodnie z
regułą 1. Jeśli ten zbiór zawiera jedno pole, to w to pole wpisujemy daną cyfrę.
Okazuje się, że korzystając tylko z tych dwóch prostych reguł, które wyprowadziliśmy z
definicji gry, da się rozwiązać wszystkie łatwe i średnie diagramy, a nawet cześć trudnych.
Metoda jest trochę pracochłonna, ale nie wymaga myślenia i doskonale nadaje się dla
komputera. Żebyśmy nie popadli jednak za szybko w samozachwyt, pokażę przykład pola,
którego w ten sposób nie wyznaczymy.
Ujęcie matematyczne kolejnej reguły i znalezienie następnych pozostawiam zainteresowanym
jako pracę domową. W sieci nie brakuje gotowych aplikacji typu "sudoku solver", od
prostych - podstawiających w kolejne pole losową "poprawną" cyfrę i wyocfujących się z
błędnych strzałów, do bardzo zaawansowanych - pokazujących kolejne ruchy i reguły
wnioskowania do nich użyte, pozwalających generować plansze do których rozwiązania
trzeba użyć zadanych reguł, itp. Znajdywanie prostych i eleganckich reguł przenosi grę na
2
wyższy poziom abstrakcji, ale zwykła gra może wtedy zacząć nudzić. Człowiek podczas
rozwiązywania diagramu rozumuje inaczej, uproszczone reguły warto też stosować np. w
zawodach na czas, z kolei takie metodyczne podejście może okazać się pomocne, gdy akurat
utkniemy na łamigłówce.
Autor: Maciej Brochocki
3