Sudoku

Logická hra sudoku Sudoku (česky též magický čtverec) je logická hra (puzzle) s číslicemi.

Historie

Tuto hru vymyslel Howard Garns v roce 1979 a publikoval ji v pod názvem „Number Place“. Své velké obliby se dočkala v Japonsku, odkud se později vrátila zpět pod názvem „sudoku“. +more Ve světě je sudoku vydáváno v mnoha periodikách. V Česku jsou to např. Lidové noviny, MF Dnes, Právo, Deník či Metro.

Princip

Cílem hry v základní podobě je doplnit chybějící cifry 1 až 9 v zadané, zčásti vyplněné čtvercové tabulce s 9 × 9 poli. V tabulce jsou zvýrazněny příčky vymezující 9 čtverců (3 × 3). +more K předem vyplněným číslicím je třeba doplnit další číslice tak, aby platilo, že v každém řádku, v každém sloupci a v každém z devíti dílčích čtverců jsou použity vždy všechny číslice jedna až devět, každá právě jednou. Aritmetická hodnota číslic pro řešení nemá význam, jde pouze o výběr logické řady devíti znaků (v zásadě je možné hrát sudoku i např. s písmeny A-I nebo jakoukoli jinou skupinou devíti symbolů).

Všech různých možností, jak může být hrací pole 9 × 9 podle těchto kritérií sestaveno, je 6 670 903 752 021 072 936 960, tj. přibližně 6,67×1021 (6,67 triliard). +more Pro zvětšující se čtverce je to úloha NP-úplná.

Obtížnost sudoku není přímo daná počtem implicitně vyplněných políček, ale jejich vzájemnými vazbami, které na první pohled nejsou vidět. Těžká sudoku mohou průměrně zkušenému luštiteli zabrat kolem 15-60 minut.

Základní metody řešení

Metoda jednoho kandidáta

Základní metodou řešení je vyhledávání všech variant (čísel) pro jednotlivé pole. Je třeba najít takové pole, kde je možná jen jediná varianta. +more Hledání je dobré provádět systematicky, a to buď v řádcích, sloupcích, nebo čtvercích 3 × 3 políčka. Je rovněž dobré začít sekcí (sloupcem, řádkem nebo čtvercem 3 × 3 políčka), ve kterém je vyplněno nejvíce čísel. Postupně pro každé prázdné pole projdeme čísla od 1 do 9 a prohledáme vždy příslušný sloupec, řádek a čtverec, zda tam již číslo je nebo není zadáno. Pokud není, zapíšeme si ho jako možnou variantu do pole (malým písmem, aby se nepletlo s řešením). Pokud v některém z polí zbude jen jedno číslo, doplníme ho jako řešení do pole a proškrtáme toto číslo ve variantách v polích ve stejném sloupci, řádku a čtverci. Takto můžeme přijít na další jednoznačně vhodná čísla. Provádíme dokola, dokud nám vycházejí nějaké jednoznačné varianty. Touto metodou lze vyřešit jen lehké hlavolamy, obtížnější vyžadují kombinaci více metod řešení.

Skenování

Každý řádek či sloupec obsahuje číslice od 1 do 9, z toho je jasné že každý tzv. super-řádek (tři řádky u sebe) či super-sloupec (tři sloupce u sebe) obsahuje tyto číslice třikrát. +more Pokud tedy najdete super-řádek se dvěma číslicemi, dokážete se poté soustředit na buňky, kde by se číslice mohla vyskytovat po třetí.

175x175pixelů

V tomto příkladu se zaměříme na šestky v prvním tzv. super-sloupci. +more Ta první se nachází v prvním sloupci a druhém řádku, ta druhá se nachází ve druhém sloupci a sedmém řádku. Díky metodě skenování je nám tedy jasné, že třetí šestka bude ve třetím sloupci a to v řádcích 4, 5 nebo 6. Ale protože se již dvě jiné šestky nachází v řádcích 4 a 6, naše šestka musí být správně umístěna do řádku 5.

Eliminace

Pokud se při luštění dostaneme do situace, kdy nám nepomůže ani metoda jednoho kandidáta ani skenování, zbývá poslední ze základních metod a to tzv. metoda eliminace. +more Tato metoda se zakládá na určení možných kandidátů (Vylučovací metodou určíme možné číslice, které do daného pole mohou teoreticky sedět). Díky tomu se pak lépe orientujeme a opět vylučovací metodou najdeme správná řešení. Poté se (je-li to možné) můžeme vrátit k řešení pomocí metody jednoho kandidáta či skenování.

Další varianty Sudoku

Diagonální sudoku

Diagonální sudoku přidává k základním pravidlům ještě pravidlo dvou hlavních diagonál (úhlopříček), které spojují protilehlé vrcholy tabulky a protínají se v prostředním poli prostředního čtverce. Také devět buněk v každé z těchto úhlopříček musí splňovat kritérium výskytu právě jedné číslice z řady 1-9. +more Toto rozšíření na jednu stranu přidává další pravidlo, které je třeba hlídat, ale na druhé straně umožňuje širší aplikaci výše uvedených metod - sledování diagonál může hráči urychlit nález řešení pro určitá pole.

Killer sudoku

Příklad zadání killer sudoku Killer sudoku (neboli „zabijácké sudoku“) je varianta hry, která neobsahuje žádná předepsaná čísla, ale pouze rámečky se součtem číslic ohraničených rámečkem - tyto rámečky nemusejí respektovat hranice 9 velkých čtverců. +more Kromě klasických technik pro řešení sudoku je nutno zapojit i různá součtová pravidla (součet řádku, sloupce či čtverce musí činit 45) a jiný druh kombinatoriky. Na rozdíl od klasického sudoku je zde tedy aritmetická hodnota číslic klíčová.

Abecední sudoku

Tato varianta se funkčně neliší od klasického sudoku, ale místo číslic používá písmena. Může jít o abecední řadu devíti písmen, nebo o skupinu jakýchkoli devíti písmen - účelem může např. +more být, aby jako bonus k samotnému vyplnění mřížky vyšlo někde v tabulce sestavené nějaké slovo jako tajenka. Takové variantě se někdy říká wordoku (česky by se dalo přeložit jako „slovoku“).

Další

Vedle těchto existuje mnoho dalších variant sudoku, které různě přidávají kritéria, mění geometrii rozdělení tabulky na devítimístné sektory, kombinují dvě hrací pole najednou apod.

Popularita

Sudoku se stalo velmi populárním na konci roku 2004 ve Velké Británii a postupně se rozšiřuje do celé Evropy. Sudoku vychází v novinách a časopisech, ale rychlost, s jakou se šíří světem, je způsobena především internetem. +more Dnes existuje přibližně 30 milionů internetových stránek, které se zmiňují o sudoku.

Sudoku bývá často označováno „hrou roku 2005“, „nejpopulárnější hlavolam současnosti“ nebo „nejrychleji se rozšiřující hra“.

Jedním z důvodů popularity sudoku jsou i benefity, které jeho hraní přináší. Pravidelné luštění sudoku zlepšuje paměť, soustředění a rozvijí logické i analytické schopnosti. +more Je tak často doporučováno jako určitá prevence před zhoršením kognitivních funkcí mozku, které souvisejí se stárnutím.

Soutěže

V únoru 2006 se v Brně konalo první mistrovství České republiky v sudoku. První oficiální titul mistra republiky získala žena, jednatřicetiletá Jana Tylová z Ústí nad Labem. +more V březnu Tylová na prvním mistrovství světa v italském městě Lucca porazila všech 87 soupeřů z dvaadvaceti zemí a stala se tak historicky první mistryní světa. Druhé mistrovství světa se uskutečnilo od 28. března do 1. dubna 2007 v Praze, mistrem světa pro rok 2007 se stal Američan Thomas Snyder.

Popularita sudoku (a příbuzného kakuro) přiměla v roce 2006 organizátory XVII. mezinárodního festivalu šachu, bridže a her Czech Open 2006 zařadit turnaje v těchto dvou disciplínách do programu. +more Soutěže Kanzelsberger Sudoku Open a Kanzelsberger Kakuro Open proběhly 25. a 26. července v Pardubicích. Turnaj v sudoku vyhrál Čech Tomáš Zavoral s časem 2 minuty 55 sekund, turnaj v kakuro vyhrál Milan Kajan ze Slovenska s časem 133,26 minut a ziskem 67 bodů.

Jako vůbec první na světě vypravily České dráhy 10. listopadu 2007 na koleje „sudokuvlak“. +more Šlo o pendolino na trase Praha-Brno a zpět. V rámci společné akce železnice, Českého rozhlasu a knihkupectví Kanzelsberger tehdy proběhl dětský turnaj v sudoku.

Ve slovenské Žilině vytvořili 23. února 2008 ustavující rekord v nejrychlejším řešení sudoku. +more Mřížku, do které se vpisují čísla od jedné do devíti, se vysokoškolákovi Pavlu Jaselskému z východního Slovenska podařilo vyluštit za pět minut a 25 sekund. Zadání obsahovalo několik speciálních podmínek, které organizátoři upřesnili ve spolupráci s anglickou centrálou pro Guinnessovy rekordy. Celkem se o zápis do světové Guinnessovy knihy rekordů v řešení sudoku pokusilo 195 luštitelů ze Slovenska, Polska, Česka a Maďarska. Pokus o světový rekord byl součástí Slovenského mistrovství v sudoku, které zorganizoval Slovenský svaz hádankářů a křížovkářů. Šampionát byl druhým mistrovstvím Slovenska v sudoku a pro pořádající Žilinu šlo o generálku před mistrovstvím světa ve stejné disciplíně, které se zde konalo v roce 2009.

Odkazy

Reference

Související články

Mistrovství České republiky v sudoku * Mistrovství světa v sudoku * Melancholie I * Jezdcova procházka * Latinský čtverec

Externí odkazy

[url=http://www. sudokualogika. +morecz/]Hráčská asociace logických her a sudoku, o. s. (HALAS). [/url] - sdružení pořádající turnaje v sudoku a logických úlohách, Mistrovství České republiky a vysílá reprezentaci na MS. * [url=https://megahry. cz/sudoku]Sudoku online[/url] - web s lehkými až středně těžkými sudoku.

Kategorie:Hlavolamy Kategorie:NP-úplné problémy Kategorie:Rekreační matematika