sudoku

Sudoku je populární logická hra, hlavolam. Název vznikl z japonského "Súdži wa dokušin ni kagiru," ale její původ není japonský. Hra byla známa v osmdesátých letech 20.století pod názvem "Number Place" ("Umísti číslice") v americkém magazínu o hlavolamech. V Japonsku se tato číselná křížovka rychle stala populární - možná také proto, že v Japonštině klasické slovní křížovky prakticky nelze tvořit. V roce 2004 přinesl SuDoku do Anglie Wayne Gould a od té doby začali doceňovat její krásu a zdánlivou jednoduchost lidé ze západní civilizace. V současná době ji dávají jako přílohu přední deníky po celém světě.
V Česku sudoku vyšlo poprvé v Lidových novinách, poté se přidala řada dalších, včetně Deníku a MF Dnes.

Je zadána tabulku o devíti sloupcích a devíti řádcích s několika doplněnými jednocifernými číslicemi.

Vaším cílem je pokud možno v co nejkratším čase

doplnit tabulku Sudoku o zbývající číslice 1 až 9 tak, aby se žádná číslice v žádnám sloupci, řádku, a ani jednom z devíti čtverců o hraně 3 čtverečky neopakovala.

To znamená, že v každém řádku, sloupci, a tučně ohraničeném čtverci musí být právě číslice 1-9 (1, 2, 3, 4, 5, 6, 7, 8, 9).

Na první pohled se zdá řešení lehké, ale opak je pravdou. Obtížnost hry Sudoku není dána pouze počtem skrytých políček, ale jejich vzájemnými vazbami, které mohou být velmi složité. Těžká sudoku mohou průměrně zkušenému luštiteli zabrat kolem 15 – 60 minut.

Aby měla hra sudoku jen jedno řešení, musí mít zadaných minimálně 17 čísel. Sudoku s 16 zadanými čísly nejsou známy. Ovšem to, že hlavolam má předem zadáno pouze 17 čísel neznamená, že musí být těžší než některé s více předem zadanými čísly. Jako příklad můžeme použít 2 hlavolamy s 64 neznámými čísly: první sudoku patří mezi jedny z nejlehčích, zatímco druhé Sudoku nelze vyluštit logicky (užitím dnes známých technik) a vyžaduje náhodné zkoušení možných hodnot.

Dovolené pomůcky jsou papír, tužka a připravené mozkové závity. Při hře Jste odkázáni pouze na vlastní logické myšlení. Je zakázáno v průběhou luštění konzultovat řešení s jinou osobou.

Z definice hry sudoku vyplývá, že existuje pouze omezené množství zadání sudoku hlavolamů: V ohraničeném poli 9*9 je pouze omezené množství variant zadání.
Pokud "validnost" sudoku nebudeme omezovat minimálním počtem nevyplněných políček, lze konstatovat, že existuje přesně 6 670 903 752 021 072 936 960 zadání Sudoku. Pro normálního člověka to znamená, že může luštit celý rok a nemusí se bát, že v jentak nebude mít co k hraní. Ovšem pro matematiky můžeme toto ohromné číslo trochu vysvětlit:
6,67*10²¹ tj. 6,67 triliard.

Zdroj

Uvedené číslo bylo poprvé vypočteno neznámým přispívajícím v diskusi s přezdívkou "QSCGZ". Druhým, kdo tento výsledek potvrdil, byl Frazer Jarvis z univerzity v Sheffieldu (anglicky).