Sudoku

Sudoku - Logická hra

Sudoku je logická hra japonského pôvodu pre jedného hráča.

Cieľom je doplniť chýbajúce číslice od 1 do 9 podľa nasledujúcich pravidiel:

Na začiatku riešenia sú niektoré políčka vyplnené číslicami. Vyplnené číslice sú rozmiestnené tak, aby pre dané rozmiestnenie existovalo iba jediné riešenie.

1. Hrací plán sa skladá z 9x9 políčok rozdelených na 9 podoblastí s 3x3 políčkami.
2. V každej podoblasti sa každá číslica má vyskytnúť práve raz (podoblasti su vyznačené hrubou čiarou).
3. V každom stĺpci a v každom riadku sa má každá číslica vyskytnúť práve raz.

Existuje aj písmenový variant Sudoku, hrací plán má rozmery 16x16 a je rozdelený na 16 podoblastí so 4x4 políčkami. Vypĺňajú sa písmená od A až O, pričom platia analogické pravidlá ako v číselnom Sudoku.

V princípe možno hrať sudoku aj na plánoch 25x25, 36x36 atď. Aký je rozmer hracieho plánu, toľko potrebujeme symbolov.

Sudoku a história

Koncom 19 storočia sa v novinách (hlavne Francúzskych) začalo objavovať veľké množstvo rôznych hlavolamov ktoré boli založené na experimentovaní s odstraňovaním čísel z magických štvorčekov. Parížsky denník Le Siècle publikoval ako prvý čiastočne vyplnený magický štvorec o veľkosti 9x9 s vnorenými štvorcami 3x3 už v Novembri 1892. To však ešte nemôžeme považovať za Sudoku, pretože na vyriešenie bola potrebná skôr aritmetika ako logika a v štvorčekoch sa mohli objavovať aj dvoj a viac ciferné čísla. Každopádne bol tento hlavolam veľmi podobný súčastnému Sudoku minimálne v tom, že súčet každého riadku, stĺpca a subštvorca musel dávať rovnaký výsledok.

V júly 1895 začali tieto, ale aj iné Francúzske noviny publikovať čiastočne pozmenené sudoku ktoré sa už podobá na súčastné moderné Sudoku. Určilo sa, že celý štvorec 9x9 môže obsahovať len čísla 1-9, avšak prestali sa vyznačovať subštvorce 3x3. Tieto týždenné hlavolamy sa objavovali vo Francúzskych novinách ako napríklad L'Echo de Paris približne dekádu, ale počas prvej svetovej vojny bohužiaľ úplne zanikli.

Podľa Willa Shortza, známeho amerického experta na oblasť hlavolamov, moderné Sudoku bolo s veľkou pravdepodobnosťou prvý krát vytvorené anonymne Howardom Garnsom. Tento 74 ročný bývalý architekt a nadšenec hlavolamov z Indiany svoj výtvor prvý krát publikoval v roku 1979 v magazíne Dell pod názvom "miesto pre čísla". So svojím Sudoku prispieval niekoľko rokov do viacerých časopisov ako Dell Pencil Puzzles alebo Word Games, ktoré publikovali jeho "miesto pre čísla". Garson umrel v roku 1989 pred tym ako sa stal z jeho výtvoru svetový fenomém. Nie je známe, či Garns poznal niektoré z tu opisovaných Francúzskych novinových Sudoku.

Do Japonska sa Sudoku dostalo v Aprili 1984 keď ho ako prvé publikovali noviny Monthly Nikolist pod názvom "Suuji" doslovne wa dokushin ni kagiru (数字は独身に限る?) ktoré sa dá voľne preložiť ako "čísla musia byť po jednom". Neskôr ho Maki Kaji (鍜治 真起) premenoval na Sudoku. V Japonsku následne hra získala nesmiernu popularitu a postupne sa stala populárnou na celom svete.

Sudoku a matematika

Riešenie Sudoku na hracom poli n² x n² rozdelenom na podoblasti n x n je z matematikého hľadiska NP-úplným problémom. Všetkých možných rôznych rozmiestnení vyhovujúcich pravidlám sudoku na hracom poli s rozmermi 9x9 je 6 670 903 752 021 072 936 960, ak sa odrátajú symetrické pozície, tak ich je len 5 472 730 538. Pre hrací plán rozmerov 16x16 zatiaľ počet kombinácií vyčíslený nebol.

Sudoku súťaže

Hoci je Sudoku hrou jedného hráča, možno organizovať aj súťaže v riešení Sudoku na čas. Slovenský zväz hádankárov a krížovkárov zorganizoval 10.2.2007 prvé Majstrovstvá Slovenska, pričom Slovensko v poriadaní národných šamiponátov bolo len ôsmou krajinou sveta. V apríli 2007 sa slovenský majster Peter Hudák stal v Prahe na 2.Majstrovstvách sveta bronzovým šampiónom. SZHaK 23. februára 2008 uskutočnil opäť v Žiline druhý ročník, ktorý sa stal medzníkom v celosvetovom meradle. Súčasťou majstrovstiev bol totiž pokus o ustanovujúci rekord v najrýchlejšom lúštení podľa vopred zadaných kritérií. Zadanie totiž muselo splniť tieto pravidlá. V každom riadku, stĺpci i vnútorných 9 štvorcoch sa nachádzali presne 3 čísla. Zároveň každé číslo od 1 po 9 bolo použité presne tri krát. Tieto pravidlá a pokus boli zaregistrované v Nadácii Guinessových rekordov a v súčasnosti sa čaká na jeho overenie. Rozhodcovia uznali najlepší čas 5 min a 25 sek. a riešenie sudoku určeného k pokusu o svetový rekord Pavlovi Jaselskému z Vojtoviec (Slovensko). Pre zaujímavosť obdobne náročnú úlohu zvládol aktuálny majster sveta Thomas Snyder na jesenných Majstrovstvách USA za 7,5 minúty. O pokus bol naozaj záujem. Pritiahol totiž riešiteľov z Poľska, Maďarska a Českej republiky, z ktorých väčšina navyše v tejto oblasti patrí k svetovej špičke. Úloha bola naozaj náročná, pretože ju v stanovenom limite 15 minút vyriešilo z celkového počtu 195 riešiteľov len 11 súťažiacich (z toho len dvaja zo zahraničia). III.Majstrovstvá Slovenska v sudoku zorganizoval Slovenský zväz hádankárov a krížovkárov opäť v Žiline. Dňom D sa stal 28.február 2009, pričom všetko prebehlo v hoteli Slovakia. Titul najlepšieho "sudokáča" si v dramatickej súťaži opäť vyplúštil Košičan Peter Hudák, ktorý bol po prvom kole len na 11.mieste.