Rozwiązywanie Sudoku.pdf

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.

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

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