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.

Sudoku 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.

W 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:

Polega 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)

Polega 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.

Jest 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ę.

Ta sekcja od 2015-05 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.

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.

Pierwsze 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].

W 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(inne języki))^[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 hasło sudoku w Wikisłowniku

• Kakuro

• 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.). brak numeru strony – 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ą