Sudoku - Sudoku

Typická sudoku ...

… A jeho řešení

Sudoku (数独, sudoku , číslice-single) ( / y Ü d oʊ k Ü , - d ɒ k -, s ə - / , původně nazvaný Number Place ) je logika -založená, kombinatorické číslo, umístění puzzle . V klasickém sudoku je cílem vyplnit mřížku 9 × 9 číslicemi tak, aby každý sloupec, každý řádek a každá z devíti dílčích mřížek 3 × 3, které tvoří mřížku (nazývané také „krabice“, „bloky“ nebo „ regiony “) obsahují všechny číslice od 1 do 9. Nastavovač hádanek poskytuje částečně vyplněnou mřížku, která pro dobře položenou hádanku má jediné řešení.

Francouzské noviny uváděly variace sudoku v 19. století a puzzle se od roku 1979 objevuje v logických knihách pod názvem Number Place. Moderní sudoku si však začalo získávat velkou popularitu až v roce 1986, kdy jej japonská logická společnost Nikoli vydala pod názvem Sudoku, což znamená „jediné číslo“. Poprvé se objevil v amerických novinách a poté v The Times (Londýn) v roce 2004 díky úsilí Wayna Goulda , který vymyslel počítačový program pro rychlou produkci unikátních hádanek.

Dějiny

Z novin La France , 6. července 1895: Pokyny k hádance zněly: „Použijte čísla 1 až 9 devětkrát, abyste dokončili mřížku tak, aby se vodorovné, svislé a dvě hlavní diagonální čáry shodovaly celkový."

Předchůdci

Hádanky s čísly se objevily v novinách na konci 19. století, kdy francouzští zakladatelé hádanek začali experimentovat s odstraňováním čísel z magických čtverců . Pařížský deník Le Siècle zveřejnil 19. listopadu 189 částečně vyplněný kouzelný čtverec 9 × 9 s 3 × 3 subsquares. Nebylo to sudoku, protože obsahovalo dvojciferná čísla a k vyřešení vyžadovalo spíše aritmetiku než logiku, ale charakteristiky sdíleného klíče: každý řádek, sloupec a dílčí kvartum sečtou se stejným číslem.

Dne 6. července 1895, Le Siècle 's rival, La France , rafinovaný puzzle tak, aby to bylo téměř o moderní Sudoku a pojmenoval jej Carré MAGIQUE Diabolique (' ďábelské magický čtverec "). Zjednodušilo to magické čtvercové puzzle 9 × 9 tak, že každý řádek, sloupec a lomené úhlopříčky obsahovaly pouze čísla 1–9, ale neoznačovaly podřízené čtverečky. Ačkoli nebyly označeny, každá dílčí čtveřice 3 × 3 skutečně obsahovala čísla 1–9 a dodatečné omezení zlomených úhlopříček vedlo pouze k jednomu řešení.

Tyto týdenní hádanky byly znakem francouzských novin, jako byl L'Écho de Paris, zhruba deset let, ale zmizely v době první světové války .

Moderní sudoku

Moderní sudoku navrhl anonymně Howard Garns , 74letý architekt v důchodu a konstruktér na volné noze z Connersville v Indianě , a poprvé jej v roce 1979 publikoval časopis Dell Dell jako Number Place (nejstarší známé příklady moderního sudoku). Garnsovo jméno bylo vždy přítomné na seznamu přispěvatelů v číslech Dell Pencil Puzzles a Word Games, které obsahovaly Number Place, a vždy chybělo v problémech, které nebyly. Zemřel v roce 1989, než dostal šanci vidět jeho tvorbu jako celosvětový fenomén. Není jasné, zda byl Garns obeznámen s některým z výše uvedených francouzských novin.

Hádanku v Japonsku představil Maki Kaji (鍜 治 真 起, Kaji Maki ) , prezident společnosti Nikoli puzzle company, v novinách Monthly Nikolist v dubnu 1984 jako Sūji wa dokushin ni kagiru (数字 は 独身 に 限 限 る) , což může být přeloženo jako „číslice musí být jediné“ nebo jako „číslice jsou omezeny na jeden výskyt“ (v japonštině dokushin znamená „neprovdaná osoba“). Jméno bylo později zkráceno na Sudoku (数 独), přičemž pro vytvoření kratší verze bylo použito pouze první kanji složených slov. „Sudoku“ je registrovaná ochranná známka v Japonsku a skládačka se obecně označuje jako Number Place (ナ ン バ ー プ レ ー ス, Nanbāpurēsu ) nebo, neformálněji, zkrácení obou slov, Num (ber) Pla (ce) (ナ ン プ レ, Nanpure ) . V roce 1986 představil Nikoli dvě inovace: počet darů byl omezen na maximálně 32 a hádanky se staly „symetrickými“ (což znamená, že danosti byly distribuovány v rotačně symetrických buňkách ). Nyní je publikován v hlavních japonských periodikách, jako je Asahi Shimbun .

Kognitivní vědec Jeremy Grabbe zjistil, že sudoku zahrnuje oblast poznání nazývanou pracovní paměť . Následný Grabbeho experiment ukázal, že rutinní hraní sudoku by mohlo zlepšit pracovní paměť u starších lidí.

Rozšířeno mimo Japonsko

V roce 1997 viděl hongkongský soudce Wayne Gould částečně dokončenou hádanku v japonském knihkupectví. Více než šest let vyvinul počítačový program pro rychlou výrobu unikátních hádanek. S vědomím, že britské noviny mají dlouhou historii publikování křížovek a dalších hádanek, povýšil sudoku na The Times v Británii, který jej spustil 12. listopadu 2004 (nazýval jej Su Doku). První dopis The Times týkající se Su Doku byl zveřejněn následujícího dne 13. listopadu od Iana Payna z Brentfordu a stěžoval si, že hádanka způsobila, že zmeškal zastávku na tubusu . Hádanky sudoku se rychle rozšířily do jiných novin jako běžná funkce.

Rychlý vzestup sudoku v Británii z relativní nejasnosti na titulní stránku v celostátních novinách přilákal komentáře v médiích a parodii (například když The Guardian 's G2 sekci inzeroval sebe jako první novinový doplněk s mřížkou sudoku na každé stránce ). The Times, uznávajíce různé psychologické přitažlivosti snadných a obtížných hádanek, představily 20. června 2005 oba vedle sebe. Od července 2005 Channel 4 zahrnul do své teletextové služby denní hru Sudoku . Dne 2. srpna představil programový průvodce BBC Radio Times týdenní Super Sudoku s mřížkou 16 × 16.

Ve Spojených státech, první noviny, které vydaly sudoku od Wayna Goulda, byly v roce 2004 The Conway Daily Sun (New Hampshire).

První živá televizní show Sudoku na světě, 1. července 2005, Sky One

První živá televizní show Sudoku na světě, Sudoku Live , byla soutěž puzzle, která byla poprvé vysílána 1. července 2005 na Sky One . Představila ji Carol Vorderman . Devět týmů po devíti hráčích (s jednou celebritou v každém týmu) reprezentujících geografické oblasti soutěžilo o vyřešení hádanky. Každý hráč měl ruční zařízení pro zadávání čísel odpovídajících odpovědím pro čtyři buňky. Phil Kollin z Winchelsea v Anglii se stal vítězem hlavní ceny série a v sérii her si odnesl přes 23 000 liber. Obecenstvo doma bylo v samostatné interaktivní soutěži, kterou vyhrála Hannah Withey z Cheshire .

Později v roce 2005 zahájila BBC SUDO-Q , herní show, která kombinovala sudoku s obecnými znalostmi. Používal však pouze hlavolamy 4 × 4 a 6 × 6. Čtyři sezóny byly vyrobeny před show skončila v roce 2007.

V roce 2006 web Sudoku publikoval skladbu Petera Levyho o sudoku, ale kvůli vysokému provozu musel rychle stáhnout soubor MP3 . Britské a australské rádio zachytilo píseň, která má zaznít v britském dokumentu Sudoku. Japonské velvyslanectví také píseň nominovalo na cenu, přičemž Levy jednal se společností Sony v Japonsku a vydal píseň jako singl.

Software sudoku je velmi populární na počítačích, webových stránkách a mobilních telefonech. Dodává se s mnoha distribucemi Linuxu . Software byl také vydán na herních konzolích, jako jsou Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , čtečka elektronických knih Nook , tablet Kindle Fire, několik modelů iPodů a iPhone . Mnoho telefonů Nokia mělo také sudoku. Ve skutečnosti, pouhé dva týdny poté, co Apple Inc. debutoval online App Store v iTunes Storu 11. července 2008, už v něm bylo téměř 30 různých sudoku vytvořených různými vývojáři softwaru , konkrétně pro iPhone a iPod Touch. Jednou z nejpopulárnějších videoher se sudoku je Brain Age: Trénujte svůj mozek za několik minut denně! . Kriticky a komerčně dobře přijatý, přinesl zvláštní chválu za implementaci sudoku a celosvětově se prodalo více než 8 milionů kopií. Díky své popularitě Nintendo vytvořilo druhou hru Brain Age s názvem Brain Age ² , která má více než 100 nových sudoku a dalších aktivit.

V červnu 2008, australský léky související s porotou rozpočet přes A $ 1 milionu přerušena, když bylo zjištěno, že pět z dvanácti porotců bylo hraní Sudoku místo poslechu důkazů.

Varianty

Nonomino nebo skládačka Sudoku, jak je vidět v The Sunday Telegraph

A jeho řešení (červená čísla)

Variace velikostí mřížky nebo tvarů oblastí

Ačkoli mřížka 9 × 9 s oblastmi 3 × 3 je zdaleka nejběžnější, existuje mnoho dalších variací. Ukázkovými hlavolamy mohou být mřížky 4 × 4 s regiony 2 × 2; 5 × 5 mřížek s oblastmi pentomino bylo publikováno pod názvem Logi-5; World Puzzle Championship představoval 6 × 6 mřížky s 2 × 3 krajů a 7 × 7 mřížky s šesti heptomino regionech a nesouvislý region. Možné jsou také větší mřížky nebo různé nepravidelné tvary (pod různými názvy jako Suguru , Tectonic , Jigsaw Sudoku atd.). The Times nabízí 12 × 12 mřížku „Dodeka Sudoku“ s 12 oblastmi čtverců 4 × 3. Časopisy Dell pravidelně vydávají hlavolamy 16 × 16 „Number Place Challenger“ (pomocí čísel 1–16 nebo písmen AP). Nikoli nabízí monstra 25 × 25 „Sudoku the Giant“. V roce 2010 byla vydána logická hra 100 × 100 s názvem Sudoku-zilla.

Mini sudoku

Pod názvem „Mini Sudoku“ se v amerických novinách USA Today i jinde objevuje varianta 6 × 6 s regiony 3 × 2 . Předmět je stejný jako u standardního sudoku, ale logická hra používá pouze čísla 1 až 6. Podobná forma pro mladší řešitele hádanek s názvem „The Junior Sudoku“ se objevila v některých novinách, například v některých vydáních The Daily Mail .

Uložení dalších omezení

Další běžnou variantou je přidání omezení na umístění čísel nad rámec obvyklých požadavků na řádky, sloupce a rámečky. Limit má často formu „dimenze“ navíc; nejběžnější je požadovat, aby čísla v hlavních úhlopříčkách mřížky byla také jedinečná. Zmíněné hádanky „Number Place Challenger“ jsou všechny této varianty, stejně jako hádanky Sudoku X v The Daily Mail , které používají mřížky 6 × 6.

Zabijácké sudoku

Killer sudoku

A jeho řešení

Killer Sudoku varianta kombinuje prvky Sudoku a Kakuro .

Abecední sudoku

Puzzle Wordoku

A jeho řešení (červené znaky)

Objevily se abecední variace, někdy nazývané Wordoku ; ve hře neexistuje žádný funkční rozdíl, pokud písmena něco neříkají. Některé varianty, například v TV průvodci , obsahují čtení slov podél hlavní úhlopříčky, řádku nebo sloupce, jakmile jsou vyřešeny; stanovení slova předem lze považovat za pomoc při řešení. Wordoku může obsahovat jiná slova než hlavní slovo.

„ Quadratum latinum “ je variace sudoku s římskými číslicemi (I, II, III, IV, ..., IX) navržená Hebdomada aenigmatum , měsíčníkem latinských hádanek a křížovek. Stejně jako Wordoku nepředstavuje žádný funkční rozdíl od běžného sudoku, ale přidává vizuální obtížnost používání římských číslic.

Hyper sudoku / windoku

Hypersudoku puzzle

A jeho řešení

Hyper Sudoku nebo Windoku používá klasickou mřížku 9 × 9 s oblastmi 3 × 3, ale definuje čtyři další vnitřní oblasti 3 × 3, ve kterých se čísla 1–9 musí objevit přesně jednou. Byl vynalezen Peterem Ritmeesterem a poprvé jej zveřejnil v Dutch Newspaper NRC Handelsblad v říjnu 2005 a od dubna 2007 denně v The International New York Times (International Herald Tribune). Poprvé se tomu říkalo Hyper Sudoku ve Oblíbených variacích sudoku Willa Shortze (únor 2006). Je také známý jako Windoku, protože se čtyřmi stínovanými vnitřními oblastmi mřížky připomíná okno se zasklívacími lištami.

Twin Sudoku

V Twin Sudoku sdílejí dvě pravidelné mřížky pole 3 × 3. Toto je jeden z mnoha možných typů překrývajících se mřížek . Pravidla pro každou jednotlivou mřížku jsou stejná jako v normálním sudoku, ale číslice v překrývající se části jsou sdíleny každou polovinou. V některých kompozicích nelze ani jednotlivou mřížku vyřešit samostatně - úplné řešení je možné až poté, co byla každá jednotlivá mřížka alespoň částečně vyřešena.

Jiné varianty

Běžné jsou také hádanky postavené z více než dvou mřížek. Pět mřížek 9 × 9, které se překrývají v rohových oblastech ve tvaru quincunxu, je v Japonsku známé jako sudoku Gattai 5 (pět sloučených). V novinách The Times , The Age a The Sydney Morning Herald je tato forma hádanky známá jako samurajské sudoku. Baltimore Sun a Toronto Star vydávají ve své nedělní edici hlavolam této varianty (s názvem High Five). Často se do překrývajících se oblastí nevkládají žádné danosti. Sekvenční mřížky, na rozdíl od překrývání, jsou také publikovány, přičemž hodnoty na konkrétních místech v mřížkách je třeba přenést na jiné.

Příklad většího sudoku

Stolní verzi sudoku lze hrát se standardním balíčkem setů s 81 kartami (viz Set hra ). Trojrozměrná logická hra Sudoku byla publikována v The Daily Telegraph v květnu 2005. The Times také vydává trojrozměrnou verzi pod názvem Tredoku. Sudoku verze Rubikovy kostky se také jmenuje Sudoku Cube .

Bylo vyvinuto mnoho dalších variant. Některé mají různé tvary v uspořádání překrývajících se mřížek 9 × 9, například motýl, větrný mlýn nebo květina. Jiní mění logiku řešení mřížky. Jedním z nich je „Greater Than Sudoku“. V tomto je mřížka sudoku 3 × 3 dána 12 symboly větší než (>) nebo menší než (<) na společném řádku dvou sousedních čísel. Další variantou logiky řešení je „Clueless Sudoku“, ve které je devět mřížek sudoku 9 × 9 umístěno v poli 3 × 3. Středová buňka v každé mřížce 3 × 3 všech devíti hádanek je prázdná a tvoří desátou hádanku sudoku bez vyplnění jakékoli buňky; tedy „bezradný“. Nová varianta kombinuje sudoku s logem posuvných dlaždic v sudoku Slide Extreme. V této variantě jsou vyplněny všechny pozice. Dlaždice jsou přesunuty do správné polohy pro vyřešení hádanky. Tato varianta obsahuje power-upy a režim kampaně. Příklady a další varianty najdete v Glosáři sudoku .

Matematika sudoku

Automorphic Sudoku s 18 stopy a obousměrné úhlopříčkou symetrie

Tato část se týká klasického sudoku, bez ohledu na skládačky, hyper a další varianty.

Dokončená mřížka sudoku je speciální typ latinského čtverce s dodatečnou vlastností, že se v žádném z devíti bloků (nebo polí 3 × 3 buněk) nebudou opakovat žádné hodnoty . Vztah mezi těmito dvěma teoriemi je znám poté, co bylo prokázáno, že vzorec prvního řádu , který nezmiňuje bloky, platí pro sudoku právě tehdy, pokud platí pro latinské čtverce.

Obecný problém řešení sudoku na n ² × n ² mřížkách n × n bloků je znám jako NP-úplný . Mnoho počítačových algoritmů , jako je zpětné sledování a tančící odkazy, dokáže účinně vyřešit většinu hádanek 9 × 9, ale kombinatorická exploze nastává s nárůstem n , což vytváří limity vlastností Sudokus, které lze konstruovat, analyzovat a řešit, jak se zvyšuje n . Sudoku lze vyjádřit jako problém s vybarvením grafu . Cílem je sestrojit 9barvení konkrétního grafu s částečným 9barvením.

Nejméně možných stop pro správné sudoku je 17 (prokázáno v lednu 2012 a potvrzeno v září 2013). Bylo nalezeno přes 49 000 sudoků se 17 indicie, mnoho japonských nadšenců. Byly nalezeny sudokusy s 18 indicie a rotační symetrií a existuje alespoň jedno sudoku, které má 18 indicií, vykazuje obousměrnou diagonální symetrii a je automorfní . Maximální počet indicií, které lze poskytnout, aniž by se vykreslovalo jedinečné řešení, jsou čtyři plné mřížky (77); pokud v buňkách, které zabírají rohy ortogonálního obdélníku, chybí dvě instance po dvou číslech a přesně dvě z těchto buněk jsou v jedné oblasti, lze číslům přiřadit dva způsoby. Protože to platí pro latinské čtverce obecně, většina variant sudoku má stejné maximum.

Počet klasických mřížek řešení sudoku 9 × 9 je 6 670 903 752 021 072 936 960 (sekvence A107739 v OEIS ) nebo přibližně6,67 × 10 ²¹ . To je zhruba1,2 × 10 ^−6násobek počtu 9 × 9 latinských čtverců. Byly také vyjmenovány různé jiné velikosti mřížky - podrobnosti najdete v hlavním článku . Ukázalo se, že počet v podstatě odlišných řešení, když jsou brány v úvahu symetrie, jako je rotace, odraz, permutace a rebeling, je pouze 5 472 730 538 (sekvence A109741 v OEIS ).

Na rozdíl od počtu kompletních sudoku sítí není počet minimálních sudoku 9 × 9 přesně znám. (Minimální hádanka je taková, ve které nelze odstranit žádnou stopu, aniž by došlo ke ztrátě jedinečnosti řešení.) Statistické techniky v kombinaci s generátorem hádanek však ukazují, že přibližně (s 0,065% relativní chybou) 3,10 × 10 ³⁷ minimálních hádanek a 2,55 × 10 Existuje ²⁵ nepodstatně ekvivalentních minimálních hádanek.

Soutěže

Soutěž sudoku na SM City Baliuag

• První World Sudoku šampionát byl držen v Lucca , Itálie , od 10. března do 12. 2006. Vítězem se stal Jana Tylová z České republiky . Soutěž zahrnovala řadu variant.
• Druhé mistrovství světa v sudoku se konalo v Praze v České republice od 28. března do 1. dubna 2007. Individuálním šampionem se stal Thomas Snyder z USA. Šampionem týmu bylo Japonsko.
• Třetí mistrovství světa v sudoku se konalo v indické Goa od 14. do 16. dubna 2008. Thomas Snyder se opakoval jako individuální celkový vítěz a také vyhrál vůbec první Classic Trophy (podmnožinu soutěže čítající pouze klasické sudoku). Soutěž týmů vyhrála Česká republika.
• Čtvrtý světa v sudoku šampionát byl držen v Žilině , Slovensko , od 24. dubna do 27. 2009. Poté, co v minulosti šampiona Thomas Snyder USA vyhrál všeobecné kvalifikace, Jan Mrozowski Polska vynořil z 36-konkurent play off, aby se stal novým World Sudoku Mistr. Hostitelský národ Slovensko se ukázalo jako nejlepší tým v samostatné soutěži tříčlenných oddílů.
• Páté mistrovství světa v sudoku se konalo ve Philadelphii v Pensylvánii od 29. dubna do 2. května 2010. Jan Mrozowski z Polska úspěšně obhájil světový titul v soutěži jednotlivců, zatímco Německo vyhrálo samostatnou soutěž týmů. Hádanky napsali Thomas Snyder a Wei-Hwa Huang , oba v minulosti mistři USA v sudoku.
• 12. světové mistrovství v sudoku (WSC) se konalo v indickém Bangalore ve dnech 15. až 22. října 2017. Kota Morinishi z Japonska vyhrála WSC jednotlivců a týmovou událost získala Čína .
• V České republice se konalo 13. mistrovství světa v sudoku.
• Ve Spojených státech se národní mistrovství Philadelphia Inquirer Sudoku konalo třikrát, pokaždé nabídlo výhru 10 000 $ pokročilému vítězi divize a místo v americkém národním sudoku týmu cestujícím na mistrovství světa. Vítězi se stali Thomas Snyder (2007), Wei-Hwa Huang (2008) a Tammy McLeod (2009). V roce 2009 se finalista třetího místa v pokročilé divizi Eugene Varshavsky předvedl na jevišti velmi špatně poté, co stanovil velmi rychlý kvalifikační čas na papíře, což upoutalo pozornost organizátorů a konkurentů včetně bývalého šampiona Thomase Snydera, který požádal organizátory o přehodnocení jeho výsledky kvůli podezření z podvádění. Po vyšetřování a opakovaném testu Varšavského jej organizátoři diskvalifikovali a udělili Chrisovi Narrikkattuovi třetí místo.

Viz také

Reference

Další čtení

• Delahaye, Jean-Paul, „The Science Behind Sudoku“ , Scientific American , červen 2006.
• Provan, J. Scott, „Sudoku: Strategy Versus Structure“, American Mathematical Monthly , říjen 2009. Publikováno také jako technická zpráva University of North Carolina UNC/STOR/08/04 , 2008.

externí odkazy

• „Variace sudoku“ ze hry Fun With Puzzles
• Sudoku v Curlie - aktivní výpis odkazů na sudoku
• Další tahy hry „Father of Sudoku“ ( BBC )