Sudoku
Sudoku (jap. 数独 sūdoku; od sūji wa dokushin ni kagiru, czyli cyfry muszą być pojedyncze) – łamigłówka, której celem jest wypełnienie diagramu 9 × 9 w taki sposób, aby w każdym wierszu, w każdej kolumnie i w każdym z dziewięciu pogrubionych kwadratów 3 × 3 (zwanych „blokami” lub „podkwadratami”) znalazło się po jednej cyfrze od 1 do 9.
Zasady przypominają trochę kwadrat łaciński, wymyślony i badany przez średniowiecznych matematyków z terenów Arabii (XIII wiek). W sudoku, w przeciwieństwie do kwadratu łacińskiego, cyfry nie mogą się powtarzać nie tylko w żadnym wierszu i kolumnie, ale także w małym kwadracie 3 × 3.
Historia
edytujSudoku zostało wynalezione przez Amerykanina Howarda Garnsa w 1979 r. i opublikowane pod nazwą „Number Place”. Łamigłówka przeszła wiele zmian. Dzisiejsze sudoku pojawiło się po raz pierwszy w Japonii w 1986 r., w czasopiśmie Nikoli, jednak międzynarodową sławę zyskało dopiero w 2005 r.
W latach 2004 i 2005 sudoku stało się niezwykle popularne w Wielkiej Brytanii dzięki publikacjom łamigłówki w tamtejszych gazetach. Modę na sudoku zapoczątkował „The Times” 12 grudnia 2004 roku. W Polsce sudoku (pod obecną nazwą) jako pierwszy opublikował tygodnik „Polityka” (15 czerwca 2005 r.), kolejne były „Angora”, „Przyjaciółka”, „Gazeta Wyborcza”, „Przegląd”, „Focus”. Gra ta jednak ukazywała się już wcześniej w polskiej prasie m.in. w „Wiedzy i Życiu” pod nazwą „Dziewięć na dziewięć”[1]. Pierwsza polska strona o sudoku powstała w sierpniu 2005 r.[2] Obecnie zawiera ponad 200 tys. plansz.
Metody rozwiązywania
edytujW przeciwieństwie do innych łamigłówek sudoku nie wymaga od gracza wykonywania żadnych rachunków matematycznych, przez co wydaje się prosta. W rzeczywistości bez cierpliwości oraz umiejętności logicznego myślenia rozwiązanie diagramu nie jest możliwe.
Do diagramu cyfry wpisywać należy jedynie w miejsca, gdzie cyfra na pewno powinna się znajdować. Niepewne miejsca można tylko zanotować lub zaznaczyć, by uniknąć kreślenia i poprawek.
Poniżej przedstawione są podstawowe metody rozwiązywania sudoku:
Metoda 1
edytujPolega na znajdowaniu miejsca, gdzie w obrębie małego kwadratu 3 × 3 pasuje dana cyfra na zasadzie eliminacji rzędów i kolumn, w których ta cyfra znajduje się w innych kwadratach.
Diagram 1 – cyfrę 4 wpisać można tylko w jedno pole środkowego dolnego kwadratu (oba pozostałe rzędy są już zajęte).
Diagram 2 – bardziej skomplikowany przypadek, znalezienie miejsca dla cyfry 3. Cyfra 3 pasuje w dwa miejsca w środkowym dolnym kwadracie. Pozwala to na wyeliminowanie tego rzędu (cyfra 3 musi znaleźć się w tym rzędzie, niezależnie, czy na polu po lewej czy po prawej), więc w prawym dolnym kwadracie dwa rzędy są zajęte. Jedną kolumnę zajmuje wpisana już cyfra 3, więc pozostaje jedyne pole, gdzie można wpisać cyfrę 3.(to obok 8)
 |
 |
Metoda 2
edytujPolega na dopełnianiu rzędu, kolumny lub kwadratu 3 × 3 cyframi od 1 do 9.
Diagram 3 – w dolnym rzędzie brakuje już tylko dwóch cyfr. Łatwo sprawdzić, że są to 1 i 7. Do drugiego pustego pola od lewej pasuje tylko cyfra 1, ponieważ w tej kolumnie już znajduje się cyfra 7. Cyfra 7 natomiast powinna się znaleźć w pierwszym pustym polu po lewej.
Diagram 4 – w pewnym momencie można dopełnić cały kwadrat, dla przykładu lewy dolny. Cyfra 2 pasuje tylko do środkowej kolumny, cyfra 6 tylko do środkowego rzędu. Do tego, gdzie umiejscowić cyfrę 9, można w tym przypadku dojść na dwa sposoby:
- bo jest to ostatnia cyfra, jaka pozostała do wpisania w tym kwadracie,
- bo nie można tam wpisać ani cyfry 2, ani cyfry 6.
 |
 |
Metoda 3
edytujJest to metoda wymagająca „bazgrania” po diagramie. Polega ona na stawianiu w odpowiednim miejscu kratki kropek-podpowiedzi. Kropki stawia się tak, by jasno określić cyfrę – patrz Diagram 5.
Metoda druga polega na wpisywaniu małych cyfr w kratkę tak, jak pokazuje Diagram 5 z prawej strony.
 |
Diagram 6 – rozwiązując sudoku, często spotykamy się z sytuacją, kiedy w kwadracie 3 × 3 dana cyfra może znaleźć się dokładnie w dwóch miejscach. Zaznaczamy wtedy oba te miejsca kropką, postawioną w odpowiednim punkcie kratki.
Diagram 7 i 8 – kiedy później, w trakcie rozwiązywania, jedno z tych miejsc zostanie zapełnione jakąś cyfrą inną niż wskazuje kropka, to w drugie miejsce można automatycznie wpisać cyfrę wskazaną przez kropkę.
 |
 |
 |
Odmiany
edytuj
Istnieją również inne odmiany sudoku:
- sudoku kinoku – jedyna odmiana sudoku, w której zachodzi interakcja między graczami. Gra przeznaczona jest dla 2, 3 lub 4 osób. Polem gry jest kwadratowa plansza składająca się z dziewięciu diagramów 9 × 9 (łącznie 729 pól);
- sudoku samurai składa się z pięciu kwadratów połączonych ze sobą w kształcie litery X;
- w sudoku diagonalnym cyfry nie mogą się powtarzać również po przekątnych kwadratu;
- sudoku trójwymiarowe, w kształcie kostki sześciennej o wymiarach 9 × 9 × 9;
- killer sudoku – początkowa plansza nie ma żadnych wpisanych cyfr, ale zamiast tego ma zaznaczone obszary obejmujące od 2 do 7 pól, dla których podana jest suma zawartych w nich cyfr;
- w sudoku magnetycznym niedozwolone jest stykanie się takich samych cyfr w rogach kwadratów;
- sudoku na większej planszy, z większą liczbą symboli (np. plansza 12 × 12 podzielona na prostokąty 3 × 4 i 12 różnych symboli do rozmieszczenia, plansza 16 × 16 podzielona na 16 kwadratów po 16 liczb do rozmieszczenia);
- sudoku nieregularne, zamiast 9-polowych kwadratów występują tu 9-polowe figury o nieregularnych kształtach.
Mistrzostwa Polski i świata w sudoku
edytujPierwsze mistrzostwa Polski w sudoku, zorganizowane przez tygodnik „Polityka”, zakończyły się 5 listopada 2005 roku. Zwycięzcą został Michał Karwański, tytuł I wicemistrza zdobył Łukasz Bożykowski, a II wicemistrza Katarzyna Ślósarczyk.
Tytuł pierwszego mistrza świata w sudoku zdobyła we włoskim miasteczku Lucca w 2006 r. Jana Tylová z Czech. W rozgrywkach indywidualnych w 2023 roku tyłuł mistrza świata w sudoku zdobył, pochodzący z Chin Tantan Dai[3], natomiast polskim mistrzem świata, w ubiegłym roku[kiedy?] został Tomasz Skrzypczak[4].
Liczba możliwych plansz
edytujW 2005 r. matematycy Bertram Felgenhauer z Drezdeńskiego Uniwersytetu Technicznego oraz Frazer Jarvis z Uniwersytetu w Sheffield udowodnili, że istnieje 6 670 903 752 021 072 936 960 różnych poprawnych plansz sudoku. Po utożsamieniu wersji różniących się permutacją cyfr, wierszy lub kolumn oraz powstałych przez odbicia i obroty, pozostaje 5 472 730 538 plansz (Mathematics of Sudoku)[5].
Jeśli liczba podanych cyfr w diagramie jest mniejsza od 17, to łamigłówka nie ma jednoznacznego rozwiązania[6]. Jednak nie wszystkie układy 17 cyfr zapewniają jednoznaczność rozwiązania – znanych jest tylko 49 151 takich układów[7].
Zobacz też
edytuj
Przypisy
edytuj- ↑ Marek Penszko. Puzeland: Dziewięć po Dziewięć. „Wiedza i Życie”, czerwiec 1997.
- ↑ Dziennik Metro, 22 sierpnia 2005 r.
- ↑ WSPC News Updates [online], www.wspc2023.com [dostęp 2024-02-15].
- ↑ Zawody: XVII Mistrzostwa Polski w Sudoku (2023) - Eliminacje - SFINKS Fundacja Rozwoju Matematyki Rekreacyjnej [online], sfinks.org.pl [dostęp 2024-02-15].
- ↑ Źródło: Muy interesante, kwiecień 2007, Madryt, str. 106
- ↑ Gary McGuire, Bastian Tugemann, Gilles Civario, There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem [online], 2012.
- ↑ Minimum Sudoku [online], school.maths.uwa.edu.au [dostęp 2017-11-26] [zarchiwizowane z adresu 2012-11-30].
Linki zewnętrzne
edytuj- James F. Crook. A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles. „Notices of the AMS”. Volume 56, Number 4, 4 2009. [dostęp 2009-03-24]. (ang.). – algorytm rozwiązania dowolnego Sudoku (w języku angielskim)
- Biuletyn Informacyjny Ambasady Japonii w Polsce z czerwca 2010: "Gry i zabawy japońskie". pl.emb-japan.go.jp. [zarchiwizowane z tego adresu (2013-02-04)]. (pol.)
- Samouczki i rozwiązywanie taktyk - krok po kroku z wizualizacją