
Sudoku ledovec: 20 faktů, o kterých jste pravděpodobně neslyšeli
Sudoku ledovec: 6 670 903 752 021 072 936 960 mřížek, důkaz za 7 milionů výpočetních hodin a hádanka, která zbořila australský soudní proces.
Publikováno 9 min
Na této stránce
Sudoku patří k nejpopulárnějším hlavolamům v historii novin a logických her. Většina hráčů si je spojuje s ranním tiskem, aplikací v telefonu nebo povědomou mřížkou devět na devět. Pod minimalistickým povrchem se však skrývá fascinující svět pokročilé kombinatoriky, gigantických výpočetních kapacit a překvapivých společenských příběhů.
Namísto opakování známých pravidel sestupujeme mnohem hlouběji. Článek má strukturu ledovce: začínáme fakty, které znějí povědomě, pokračujeme matematickými důkazy a historickými perličkami až k tématům na samých hranicích současných znalostí. Společně s Poly, maskotem našeho studia, vás zveme na cestu pod hladinu hrací desky.

Vrstva 1. Povrch: fakty známé mnoha hráčům
1. Sudoku není aritmetická hra
Číslice 1 až 9 v sudoku nereprezentují číselné hodnoty. Při řešení hráč neprovádí žádná matematická sčítání, odčítání ani jiné operace. Tyto symboly fungují pouze jako rozlišovací znaky. Stejně dobře by je mohla nahradit písmena abecedy, barvy, geometrické tvary či pozice hráčů na baseballovém hřišti, jak v experimentu předvedla stanice ESPN.
Podstatou jsou čisté logické vztahy: příslušnost, vzájemné vylučování a jednoznačné přiřazení symbolu k poli v řádku, sloupci a bloku. Proto se v sudoku stejně dobře orientují humanitní vědci, právníci i programátoři. Rozhoduje strukturální postřeh, nikoli početní zběhlost.
2. Skutečný význam japonského názvu
Počátky moderního sudoku souvisí s americkou hádankou Howarda Garnse publikovanou v roce 1979 pod názvem Number Place. V dubnu 1984 japonské vydavatelství logických časopisů Nikoli uvedlo tento koncept na domácí trh. Redakce pojmenovala hru Sūji wa dokushin ni kagiru, což lze přeložit jako: číslice musí zůstat osamocené. Slovo dokušin znamená v japonštině svobodného člověka. Název výstižně shrnoval hlavní pravidlo: v řádku, sloupci a bloku se každá číslice smí objevit pouze jednou, bez protějšku.
Dlouhý název brzy zkrátili kombinační prvních znaků kandži: sū (číslice) a doku (samotný). Tak vzniklo slovo sudoku. Vydavatelství Nikoli si tento termín v Japonsku registrovalo jako ochrannou známku. Konkurenční japonští vydavatelé proto používají označení nanpure, fonetickou adaptaci původního názvu Number Place. Širší kontext představujeme v článku o historii sudoku.
3. Dvě železná pravidla vydavatelství Nikoli
Vydavatelství Nikoli proslulo rigorózním přístupem ke kvalitě. Zavedlo dva tvrdé standardy: žádná oficiální úloha nesmí obsahovat více než 32 výchozích nápověd, protože větší počet hodnot bere radost ze samostatného objevování. Druhé pravidlo z roku 1986 vyžaduje rotační symetrii rozmístění nápověd o 180 stupňů. Takové uspořádání je podpisem lidského autora, který úlohu skládá záměrně s důrazem na plynulou deduktivní cestu.
4. Počet nápověd neurčuje obtížnost
Mnozí začátečníci posuzují obtížnost podle toho, kolik polí je předem vyplněno. To je intuitivní, ale zavádějící předpoklad. Standardní novinové sudoku má obvykle 30 až 35 nápověd. Matematické minimum pro jednoznačné řešení činí 17 nápověd. Naproti tomu některé z nejtěžších úloh na světě obsahují 21, 23 nebo i více výchozích čísel.
O skutečné náročnosti rozhoduje geometrie vazeb mezi symboly, nikoli jejich celkový počet. Stačí posunout dvě nebo tři čísla jinam a zdánlivě banální úloha vyžaduje pokročilé řetězové postupy. Rozdíly jsou ještě výraznější u hybridních variant, o nichž píšeme v přehledu variant sudoku jako killer či thermo.
Vrstva 2. Voda: matematika pod deskou

5. Přesný počet platných mřížek: 6 670 903 752 021 072 936 960
Dlouhá léta po celosvětové popularitě nikdo neznal přesný počet všech správně vyplnitelných sudoku mřížek 9x9. Prostor 9^81 kombinací přesahuje kapacity všech počítačů. Průlom nastal v roce 2005 díky Bertramu Felgenhauerovi z drážďanské univerzity a Frazeru Jarvisovi z University of Sheffield.
Matematici rozdělili desku na pásma a využili jejich symetrie. Celý prostor zredukovali na 44 základních uspořádání prvního pásma. Výsledek byl ohromující: existuje přesně 6 670 903 752 021 072 936 960 platných mřížek.
6. Pouze 5 472 730 538 významově odlišných mřížek
Původní číslo zahrnuje i varianty, které jsou z matematického hlediska svými kopiemi. Pokud na hotové desce prohodíme všechny jedničky a dvojky, logická struktura zůstává stejná. Totéž platí pro otočení desky, zrcadlení či přeházení řádků a sloupců uvnitř bloků.
V roce 2006 Ed Russell a Frazer Jarvis dokázali, že plná grupa symetrií sudoku obsahuje 1 218 998 108 160 prvků. Pomocí Burnsideova lemmatu rozdělili celkový prostor a ukázali, že odlišných mřížek existuje přesně 5 472 730 538.
7. Celkový počet úloh nikdo nezná
Je důležité rozlišovat plné řešení (kompletně vyplněnou desku) od samotné úlohy. Úloha je výchozí síť s odstraněnými číslicemi zaručující jediné řešení. Z jedné báze lze vytvořit tisíce různých úloh a naopak různé báze mohou vést ke shodnému zadání. Celkový počet unikátních sudoku úloh dodnes zůstává neznámý.
8. Úloha se 40 nápovědami může být minimální
V terminologii hlavolamů označuje minimální úloha takový rébus, z něhož nelze odebrat jedinou nápovědu bez ztráty jednoznačnosti. Největší známá minimální úloha obsahuje 40 nápověd. Téměř polovina desky je vyplněná, a přesto je každé číslo absolutně nezbytné. Současně platí: každá platná úloha musí obsahovat nejméně 8 z 9 různých číslic.
Vrstva 3. Temnota: hranice poznání a superpočítače
9. Sedmnáctka je matematický zákon. Důkaz stál 7 milionů hodin
Více než dvě desetiletí se vědci ptali, zda je možná platná úloha s pouhými 16 výchozími číslicemi. Odpověď přinesl teprve v lednu 2012 tým Garyho McGuirea z University College Dublin: úloha s 16 nápovědami a jediným řešením neexistuje.
Klíčem se stala metoda nevyhnutelných množin (unavoidable sets). Výpočty na superpočítačích zabraly celkem asi 7 milionů jádro-hodin. Podrobnosti metody najdete v publikaci týmu McGuirea na arXiv.
10. Diagramy s 16 nápovědami existují, ale mají dvě řešení
Gordon Royle z University of Western Australia našel uspořádání s 16 nápovědami, které má přesně dvě řešení. Na desce schází jediné číslo k uzavření alternativní cesty. Ukazuje to přesnou hranici: 16 nápověd umí prostor zúžit ke dvěma stavům, nikdy však k jedinému výsledku.

11. Roylova sbírka: 49 151 úloh se 17 nápovědami
Gordon Royle dlouhá léta shromažďoval známé jednoznačné úlohy se 17 nápovědami. Jeho registr se uzavřel na čísle 49 151 diagramů a odhady naznačují, že zachycuje téměř všechny existující úlohy tohoto typu.
Z materiálů připojených k McGuireově publikaci vyplývá ještě jeden pozoruhodný kombinatorický fakt: rekordní plná mřížka umožňuje vyříznout až 29 různých jednoznačných 17nápovědových úloh.
12. Symetrické minimum čeká na formální důkaz
Ačkoli víme, že celkové minimum pro libovolnou desku činí 17 nápověd, u symetrických diagramů je situace komplikovanější. Nejmenší známá úloha se středovou symetrií (otočení o 180 stupňů) obsahuje 18 nápověd. Matematici se domnívají, že 17 nápověd v symetrickém uspořádání není možné, ale úplný důkaz dosud nikdo nepředložil.
13. Zobecněné sudoku patří k nejtěžší třídě problémů informatiky
Klasickou desku 9x9 moderní algoritmus vyřeší během zlomku vteřiny. Situace se dramaticky mění, když pravidla zobecníme na desky o velikosti n^2 na n^2. Roku 2002 Takayuki Yato a Takahiro Seta dokázali, že zobecněné sudoku je NP-úplným problémem.
To znamená, že řešení patří do stejné třídy výpočetní složitosti jako slavný problém obchodního cestujícího. Podrobnosti najdete v práci Yatoa a Sety a v původním článku Knutha.
14. V teorii grafů jde o barvení vrcholů
Z pohledu diskrétní matematiky je mřížka sudoku grafem: každých 81 polí odpovídá vrcholu, hrany spojují vrcholy, které nesmějí přijmout stejné číslo, tedy leží ve stejném řádku, sloupci nebo bloku. Řešení odpovídá nalezení správného 9obarvení tohoto grafu. Závislost podrobně popsali Agnes Herzbergová a M. Ram Murty v článku na stránkách Notices of the American Mathematical Society.
Vrstva 4. Historie, soudy a mistři
15. Sudoku vzešlo z problému, který porazil Eulera

V roce 1782 švýcarský matematik Leonhard Euler formuloval slavný problém 36 důstojníků: rozmístit do čtverce 6x6 důstojníky z šesti pluků o šesti hodnostech tak, aby se v žádném řádku ani sloupci neopakovala pluk ani hodnost. Takové uspořádání nazýváme řecko-latinským čtvercem řádu 6. Euler po mnoha pokusech dospěl k závěru, že uspořádání není možné.
Teprve v roce 1901 francouzský matematik Gaston Tarry Eulerovu domněnku dokázal ručním ověřením všech případů. A v roce 2022 fyzici představili kvantové řešení problému 36 důstojníků využívající provázané stavy a zlatý řez.
16. Hádanka, která přerušila soudní proces za miliony
Roku 2008 se v australském Sydney projednával složitý trestní případ týkající se nelegální výroby drog. Řízení trvalo téměř tři měsíce, bylo vyslechnuto 105 svědků a náklady překročily milion australských dolarů. Nečekaně si obhájci všimli podezřelého chování předsedkyně poroty.
Rychle vyšlo najevo, že si místo záznamů o svědeckých výpovědích do poznámkového bloku luštila sudoku. Navíc svou vášní od druhého týdne nakazila další čtyři porotce. Soudce Peter Zahra musel porotu rozpustit a celou kauzu začít znovu. Případ tehdy popisovali novináři Sydney Morning Herald.
17. Jana Týlová a zlatý úvod české sudoku historie
Oficiální mistrovství světa v sudoku (World Sudoku Championship) pořádá Světová federace hádanek od roku 2006. První turnaj se konal v italské Lucce a zvítězila v něm reprezentantka Česka Jana Týlová před Američanem Thomasem Snyderem. Snyder pak získal zlaté medaile v letech 2007, 2008 a 2011 a zapsal se do Guinnessovy knihy rekordů za vyřešení turnajové desky za neuvěřitelných 2 minuty a 8,53 sekundy.
Zejména Češi si výsledků českých luštitelů dlouhodobě váží: Jana Týlová i následní reprezentanti potvrdili, že česká sudoku škola patří k absolutní světové špičce, přičemž oba první světové tituly získali shodně ženy i muži napříč kategoriemi.
Vrstva 5. Dno ledu: výzvy pro hrstku odvážných
18. AI Escargot: nejslavnější a nejtěžší hádanka světa
Finský matematik Arto Inkala proslul tvorbou desek, které potrápí i špičkové počítačové programy. Roku 2006 vydal diagram AI Escargot. Zkratka AI pochází z iniciál jeho jména a slovo escargot (francouzsky: šnek) odkazuje na charakteristické spirálovité uspořádání startovních čísel.
V roce 2012 Inkala navrhl další 21nápovědovou desku označenou tiskem za nejtěžší sudoku na světě. Její konstrukce si vyžádala tři měsíce práce a otestování více než miliardy variant. Ukazatel trivializability udávající pravděpodobnost, že jedno správné číslo uvolní další tahy, činí pouhých 4,5 %.
19. Největší sudoku světa čítá 280 spojených desek
Pro většinu lidí je jedna deska 9x9 naprosto dostačující mentální výzvou. Dne 7. října 2018 však bylo v japonském městě Čófu u Tokia představeno gigantické multi-sudoku složené z 280 propojených mřížek. Událost byla oficiálně zapsána do Guinnessovy knihy rekordů.
20. Proč sudoku nikdy nevyčerpáme
Při 5,5 miliardy významově odlišných řešení, nespočetném množství platných úloh, 49 151 známých uspořádáních se 17 čísly a otevřených otázkách kolem symetrií je sudoku prakticky nekonečným logickým vesmírem.
Navíc vědci dosud neznají přesný počet mřížek pro větší formáty 16x16 či 25x25 a vývoj hybridních variant neustále otevírá nové oblasti výzkumu. Sudoku není rébus, který lze odložit na polici. Je to bohatý oceán logických závislostí, v němž každý hráč může objevovat nové hloubky. Doporučujeme zejména prostudovat nabídku variant sudoku.
Často kladené otázky (FAQ)
Kolik čísel minimálně potřebuje správné sudoku? Matematické minimum pro desku 9x9 činí přesně 17 nápověd. Bylo prokázáno výpočtem roku 2012 týmem Garyho McGuirea.
Podle čeho poznáme obtížnost úlohy? O úrovni rozhoduje poloha čísel a složitost eliminací potřebných k dalšímu kroku, nikoli celkový počet nápověd.
Jak se v Japonsku říká tradičnímu sudoku? V Japonsku se běžně používá označení nanpure odvozené od anglického Number Place. Slovo sudoku je chráněnou známkou vydavatelství Nikoli.
Musí se u těžkého sudoku někdy hádat? Ne. Každá správně sestavená úloha s jediným řešením je řešitelná výhradně dedukcí. Nutnost hádání signalizuje vadné zadání.
Zdroje a další čtení
- Cornell Math: The Math Behind Sudoku
- arXiv: There is no 16-Clue Sudoku
- Wikipedia: Mathematics of sudoku
- Quanta Magazine: kvantové řešení Eulerova problému
- Sydney Morning Herald: jurors playing Sudoku abort trial
- Guinness World Records: nejrychlejší a největší sudoku
Dále doporučujeme průvodce jak hrát sudoku, článek o historii sudoku a naši hru Polydocu.
Polydocu - sudoku v podobě dobrodružství
Devět číslic, výprava džunglí, papoušek Poly a žádné umělé překážky. Zapište se na seznam čekatelů a pošleme vám zprávu v den vydání.
Jeden e-mail v den vydání, žádný spam.



