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.
Brak komentarzy:
Prześlij komentarz