Login lub e-mail Hasło   

Rozwiązywanie Sudoku

Odnośnik do oryginalnej publikacji: http://mmorfe.blogspot.com/2008/09/rozwi(...)ku.html
Uwaga może odebrać przyjemność z gry!
Wyświetlenia: 17.348 Zamieszczono 10/09/2008

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.

Podobne artykuły


55
komentarze: 19 | wyświetlenia: 75353
20
komentarze: 24 | wyświetlenia: 23818
13
komentarze: 1 | wyświetlenia: 5090
13
komentarze: 7 | wyświetlenia: 5868
20
komentarze: 14 | wyświetlenia: 53453
13
komentarze: 8 | wyświetlenia: 48705
32
komentarze: 17 | wyświetlenia: 2927
18
komentarze: 8 | wyświetlenia: 1287
19
komentarze: 4 | wyświetlenia: 10190
15
komentarze: 3 | wyświetlenia: 14603
43
komentarze: 28 | wyświetlenia: 6651
25
komentarze: 5 | wyświetlenia: 16725
20
komentarze: 5 | wyświetlenia: 21574
5
komentarze: 4 | wyświetlenia: 9031
 
Autor
Artykuł

Powiązane tematy





Dla leniwych a ciekawych strona z opisem wszystkich technik:
http://www.sudokuoftheday.com/(...)iew.php
Pozostawiona w artykule technika i dalsze pozwalają tylko i aż na usuwanie potencjalnych kandydatów, wyznaczenie pola zawsze odbywa się przy pomocy 1 lub 2. Do diagramu w artykule wystarczy tylko cierpliwie stosować 1.



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2014 grupa EIOBA. Wrocław, Polska