KenKen a kalkudoku
Klece, počty a logika
od první tužky po algoritmy
Na pozadí řeší počítač kalkudoku 6 × 6 tak jako člověk. V každém kroku hledá nejjednodušší techniku, která ještě něco přinese – od jednopolové klece po souhru klecí – a pojmenuje ji. Každá zapsaná číslice vyroste do věže podle své hodnoty a z vyřešené mřížky je panorama města. Techniky vysvětlují kapitoly 2 až 8, stejný řešitel hodnotí úlohy v kapitole 12.
Jak průvodce používat
KenKen a kalkudoku jsou dvě jména pro tutéž hádanku: mřížku N × N doplníte čísly 1 až N tak, aby se v řádku ani ve sloupci nic neopakovalo, a zároveň aby každá ohraničená klec dala svým sčítáním, odčítáním, násobením nebo dělením číslo v rohu. Je to sudoku, ve kterém se počítá. Průvodce vede od pravidel a prvních jistých tahů přes kandidáty klecí, povinné číslice a pravidlo součtu řádku až k latinským čtvercům, kombinatorice klecí a tomu, jak hádanku řeší a vyrábí počítač. Je pro děti, které právě zvládly malou násobilku, pro rodiče a učitele, pro hráče, kteří chtějí hrát lépe, i pro studenty matematiky a informatiky.
Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra na vlastní mřížce, kde si věc vyzkoušíte klepáním na pole. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, proč technika funguje, výpočty, řešené příklady a procvičení s řešením. Teorie bývá o úroveň náročnější než úvod kapitoly. Barevná tečka v obsahu ukazuje úroveň. Postup se ukládá jen ve vašem prohlížeči.
Hned za úvodem najdete sekci Hrajte kalkudoku ve 3D: barevné klece, kostky, které rostou do věží podle čísla, pět obtížností podle technik z tohoto průvodce a trenér, který ukáže další logický krok a odkáže na kapitolu, kde se technika vykládá.
Mapa průvodce
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Pravidla, pojmy a historie | základy | mřížka, klec, cíl, operace, opakování v kleci, příklad 4 × 4 krok za krokem; Miyamoto, výuka bez výkladu, noviny 2008–2009, jméno a značka |
| 2 První tahy | základy | jednopolové klece, klece s jedinou možností (tabulka pro 4 × 4 a 6 × 6), poslední pole v řádku a sloupci |
| 3 Kandidáti klece | základy | rozklady cíle, rozdíl a podíl pro N = 4 a 6, klece do L s opakováním, n-tice, poslední pole klece |
| 4 Řádky a sloupce | základy | latinský čtverec, jediný kandidát, skrytý singl, poznámky tužkou, kontrola chyb |
| 5 Povinné číslice | pokročilí | povinná číslice klece, klec v jednom řádku, prvočísla 5 a 7, parita |
| 6 Pravidlo součtu řádku a sloupce | pokročilí | součet a součin řádku, oblasti více řad, vnitřní zbytek a vyčnívající pole |
| 7 Dvojice, trojice a X-wing | pokročilí | nahé a skryté dvojice, nahé trojice, X-wing, jak je hledat |
| 8 Souhra klecí a varianty | pokročilí | zkusmé dosazení n-tice, varianta bez znamének, jen sčítání, velké mřížky, řešení na čas |
| 9 Latinské čtverce | mistr a věda | počty 1, 2, 12, 576, 161 280, redukované čtverce, Euler a 36 důstojníků, ortogonální čtverce, plánování pokusů |
| 10 Kombinatorika klecí | mistr a věda | počty rozkladů, nejjednoznačnější a nejvíc nejednoznačné cíle, prvočísla, simulace jednoznačnosti |
| 11 Algoritmy a složitost | mistr a věda | n-tice jako omezení, propagace, backtracking, exact cover a SAT, NP-úplnost doplňování latinských čtverců |
| 12 Tvorba úloh a výuka | mistr a věda | generátor krok za krokem, test jednoznačnosti, hodnocení podle technik, kalkudoku ve škole, zdravé hraní |
Co budete potřebovat
Tužku a papír, nebo jen prst na displeji. Všechny úlohy z průvodce jsou v laboratořích, takže tisknout nic nemusíte. Pro první část stačí sčítat, odčítat a znát malou násobilku. Od kapitoly 5 se hodí rozklad na prvočinitele, v kapitolách 9 až 11 trocha kombinatoriky a algoritmického myšlení – co je potřeba, průvodce vysvětlí na místě.
Navazující látku najdete v sousedních průvodcích: příbuznou hádanku bez počítání a ryby, křídla a řetězy v průvodci Sudoku, součty v řádcích a sloupcích v průvodci Kakuro, dělitelnost, prvočísla, permutace a faktoriály v průvodci Matematika, důkaz sporem a výrokovou logiku v průvodci Logika a kritické myšlení, algoritmy a složitost v průvodci Informatika, stromy variant v průvodci Šachy a odhad podílu ze simulace v průvodci Statistika a modely.
Značení a předpoklady
Pole se v celém průvodci značí ř3s2 = 3. řádek shora, 2. sloupec zleva. Klec se píše cílem a znaménkem, například 12×, 2÷, 7+ nebo 3−; jednopolová klec jen číslem. Mřížka N × N obsahuje čísla 1 až N. Laboratoře, hero i 3D hra používají řešitel, který v každém kroku zkouší techniky od nejjednodušší a úlohu zařadí podle nejtěžší, kterou potřeboval.
| Úroveň | Nejtěžší potřebná technika | Kapitola |
|---|---|---|
| 1 | Jednopolová klec, Klec s jedinou možností, Jediný kandidát, Skrytý singl | 2, 4 |
| 2 | Kandidáti klece, Poslední pole klece | 3 |
| 3 | Povinná číslice klece, Nahá dvojice (a trojice, skrytá dvojice) | 5, 7 |
| 4 | Pravidlo součtu řádku, X-wing | 6, 7 |
| 5 | Souhra klecí | 8 |
| mimo škálu | úloha potřebuje techniku nad rámec průvodce | 8, 11 |
Čtyři druhy rámečků
Konkrétní situace z mřížky nebo výpočet, který si můžete ověřit v laboratoři.
Jak hra vznikla, odkud má jméno, co dokázali matematici a jak se hádanka dostala do novin.
Rychlé pravidlo, zkratka nebo návyk, který používají zkušení řešitelé.
Častá chyba, mýtus nebo past, do které se snadno spadne.
Studijní materiál o hře. Hrajte pro radost a s mírou – bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje knihy, aplikace či programy; historické údaje a matematické výsledky mají v příloze C zdroj a datum ověření (8. 11. 2026). Úlohy, statistiky a počty v laboratořích jsou spočítané přímo v prohlížeči nebo skriptem nad stejným kódem.
Rozsahem odpovídá: matematika – kombinatorika a teorie latinských čtverců (počítání čtverců, redukované a ortogonální čtverce, faktoriály, rozklady čísel) na úrovni úvodních vysokoškolských kurzů; informatika – úvod do algoritmů prohledávání (backtracking, heuristiky), propagace omezení, převod na exact cover a SAT a úvod do teorie složitosti (NP-úplnost); pravidla – kalkudoku a jeho varianty podle pramenů uvedených v příloze C.
Kalkudoku ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
Řešte kalkudoku na desce s barevnými klecemi, kde každá zapsaná číslice vyroste v kostku – věž tím vyšší, čím větší je číslo. Pohled jde přepnout na 3D nebo 2D shora. Na výběr je Klasické (4 × 4 až 8 × 8), Denní výzva (v daný den stejné zadání pro všechny), Pro děti (jen + a −, mřížky 3 × 3 až 5 × 5), Bez znamének (operaci odvodíte sami, kapitola 8) a Velké 9 × 9. Obtížnost 1 až 5 odpovídá technikám z průvodce: 1 jsou jednopolové klece, klece s jedinou možností a singly z kapitoly 2 a kapitoly 4, 2 navíc kandidáti klecí a poslední pole klece z kapitoly 3, 3 povinná číslice klece z kapitoly 5 a nahé dvojice z kapitoly 7, 4 pravidlo součtu řádku z kapitoly 6 a X-wing, 5 souhra klecí z kapitoly 8. Ovládání v kostce: klepněte na pole a pak na číslo; na klávesnici 1–9, šipky, N přepne poznámky, T zavolá trenéra a Z (nebo Y) vrátí tah.
Pravidla, pojmy a historiezáklady
Mřížku N × N doplňte čísly 1 až N tak, aby se žádné neopakovalo v řádku ani ve sloupci. Mřížka je navíc rozdělená silnými čarami na klece; v rohu každé klece je cíl a operace. Čísla v kleci musí operací dát cíl: 7+ znamená součet 7, 12× součin 12, 3− rozdíl 3 a 2÷ podíl 2. To je celé pravidlo. Kapitola zavádí slovník, se kterým pracuje celý průvodce, ukazuje celé řešení malé úlohy krok za krokem a vypráví, jak hra vznikla.
Kalkudoku je jako rozpočet rodinného výletu: v každém řádku má každý člen rodiny jiný úkol a v každé klíčové skupince musí sedět součet nebo součin. Kdo vidí obojí naráz – řádky i počty –, najde řešení bez hádání.
+Teorie: pravidla, pojmy, řešený příklad, historie a jméno
1.1Pravidla
Kalkudoku (pod obchodním jménem KenKen) se hraje na čtvercové mřížce N × N, nejčastěji 4 × 4 až 9 × 9; pro děti se používá i 3 × 3. Do každého pole patří jedno z čísel 1 až N. Platí dvě pravidla:
- Latinský čtverec: v žádném řádku ani sloupci se číslo neopakuje. Každý řádek i sloupec tedy obsahuje všechna čísla 1 až N právě jednou.
- Klece: mřížka je rozdělená na souvislé skupiny polí ohraničené silnou čarou. Čísla v kleci musí uvedenou operací dát cíl v jejím rohu.
Operace se zapisují jako + (součet), − (rozdíl), × (součin) a ÷ (podíl). U odčítání a dělení se počítá „větší minus menší“ a „větší děleno menším“, a proto mají tyto klece podle pravidel v novinách a v tomto průvodci vždy právě dvě pole. Jednopolová klec nemá operaci: její cíl je přímo číslo, které do pole patří. Dobře zadaná úloha má jediné řešení; to ověřuje počítač (kapitola 12).
Na rozdíl od sudoku a kakura se v kleci číslice opakovat smí, pokud stejné číslice neleží ve stejném řádku ani sloupci. Klec do tvaru L nebo čtverec 2 × 2 tak může obsahovat dvě stejné číslice „na úhlopříčce“. Klec, která leží celá v jednom řádku nebo sloupci, má číslice vždy různé.
1.2Pojmy a značení
Řada je společné slovo pro řádek a sloupec. Kandidát pole je číslo, které do něj ještě může přijít. Sada číslic klece je výčet čísel, která v ní budou, bez ohledu na pořadí; n-tice je konkrétní pořadí čísel v polích klece. Klec 7+ ze dvou polí v mřížce 4 × 4 má jedinou sadu {3, 4}, ale dvě n-tice: (3, 4) a (4, 3). Na rozdílu mezi sadou a n-ticí stojí techniky z kapitol 2, 3 a 5.
Pro N = 4 je součet řádku 10 a součin 24, pro N = 6 je to 21 a 720. Z těchto dvou čísel vychází pravidlo součtu řádku v kapitole 6.
1.3Řešený příklad krok za krokem
Úlohu z obr. 1.1 řešitel průvodce vyřeší za 21 kroků bez jediného pokusu. První tahy jsou typické pro každou úlohu:
1. Jednopolová klec: ř2s2 = 3. 2. Klec 4÷ ve dvou polích splní jediná sada {1, 4} – z polí ř3s2 a ř3s3 škrtneme ostatní čísla. 3.–5. Kandidáti klecí: 2÷ připouští jen {1, 2} nebo {2, 4}, takže v ř1s1 nemůže být 3; podobně se zúží klece 2− a 7+. 6. Skrytý singl: trojka může v 1. řádku stát už jen v ř1s3. 7. Poslední pole klece: v kleci 2− je ř1s3 = 3, takže ř1s2 = 3 − 2 = 1. Zbytek dokončí jediní kandidáti a ještě jednou kandidáti klece 2÷.
V laboratoři projdete všech 21 kroků: 16 zápisů číslic (včetně zadané trojky) a 5 kroků, kdy se jen škrtají kandidáti. Za povšimnutí stojí, že klec 7+ do tvaru L má podle tvaru sady {1, 2, 4}, {2, 2, 3} i {1, 3, 3}; poslední dvě ale řešitel vyřadí, protože obě potřebují trojku ve 2. řádku, kde už je ř2s2 = 3.
1.4Historie
Hru vymyslel japonský učitel matematiky Tetsuya Miyamoto (nar. 1959). Oficiální stránky hry uvádějí rok 2004, životopisné heslo autora rok 2003. Miyamoto vedl vlastní soukromou školu matematiky a jeho přístup se popisuje jako „umění učit, aniž by se učilo“: žáci nedostanou výklad, ale úlohy, na které přijdou sami. Hádanky s klecemi a početními operacemi k tomu sloužily jako trénink vytrvalosti, logiky a počítání.
V Japonsku vycházely sbírky Miyamotových hádanek pod názvem, který se dá přeložit jako „hádanky, po kterých zmoudříte“ (kašikoku naru pazuru). V roce 2007 na ně narazil Američan Robert Fuhrer a firma Nextoy hádanku v roce 2008 přivedla do Spojených států. Britský deník The Times ji začal otiskovat v březnu 2008, The New York Times v únoru 2009. Od té doby vychází v desítkách novin a ve školách, kde slouží jako procvičování počítání s logikou.
1.5Jméno a ochranná známka
Japonské slovo ken (賢) znamená chytrost, moudrost; zdvojené KenKen se vykládá jako „chytrost na druhou“. Jméno KenKen (a také KenDoku) je ochranná známka: oficiální stránky hry uvádějí jako vlastníka registrované známky společnost KenKen Puzzle, LLC, encyklopedické zdroje jmenují Nextoy, LLC, firmu, která hru přivezla do USA. Hádanky téhož typu, které tuto značku nesou bez licence nést nemohou, se proto jmenují kalkudoku (z anglického calcudoku, „počítací sudoku“) nebo mathdoku. Průvodce používá v nadpisech obě jména a v textu volné slovo kalkudoku.
1.6Kalkudoku, sudoku a kakuro
Se sudoku má kalkudoku společný latinský čtverec, ale nemá bloky 3 × 3 a nemá předvyplněná vodítka – jejich roli hrají klece (zadaná číslice je jen jednopolová klec). S kakurem a Killer sudoku má společné cíle klecí, jenže kromě součtu používá i rozdíl, součin a podíl a dovoluje opakování v kleci. Proto se v kalkudoku od začátku počítá s rozklady cíle – výčtem sad, které cíl splní – a s jejich průnikem s řádky a sloupci.
1.7Procvičení
- Každý řádek a sloupec obsahuje 1 až N právě jednou; každá klec dá operací svůj cíl.
- Rozdíl a podíl jen ve dvou polích, větší číslo napřed; jednopolová klec je zadaná číslice.
- V kleci se číslice smí opakovat, pokud nesdílí řádek ani sloupec.
- Vymyslel ji Tetsuya Miyamoto kolem roku 2004 pro výuku; KenKen je ochranná známka, volný název je kalkudoku.
První tahyzáklady
Každá úloha má několik míst, kde je jasno hned na první pohled. Jednopolová klec je zadaná číslice. Klec s jedinou možností má cíl, který splní jediná sada číslic – 7+ ve dvou polích mřížky 4 × 4 může být jen 3 a 4. A když v řádku nebo sloupci zbývá poslední volné pole, chybějící číslo se dopíše bez počítání. Tyto tři tahy tvoří úroveň 1 a otevírají každou úlohu.
Cíl klece je jako cenovka, kterou jde zaplatit jen několika způsoby. Některé cenovky – třeba 30 jako součin dvou čísel do 6 – jdou zaplatit jediným způsobem: 5 · 6. Kdo si takové cenovky zapamatuje, začne každou úlohu o krok napřed.
Cíl klece je jako cenovka: za 30 korun koupíte z mincí 1 až 6 dvě různé jen jako 5 + … ne, za 30 „krát“ jen 5 a 6. Kdo si zapamatuje pár cenovek, které jdou zaplatit jediným způsobem, začne každou úlohu o krok napřed.
+Teorie: jednopolové klece, tabulka jediných možností a poslední pole
2.1Jednopolová klec
Klec z jediného pole nemá operaci a její cíl je přímo číslo, které do pole patří. Je to jediný druh „vodítka“, který kalkudoku má. Po zápisu se číslo škrtne jako kandidát ve zbytku řádku i sloupce. Ve vzorku 6 100 úloh mělo aspoň jednu jednopolovou klec 85 % úloh (průměrně 2,5 až 3,4 na úlohu). Vznikají při náhodném dělení na klece i při opravách, kdy generátor oddělí pole z klece, aby měla úloha jediné řešení (kapitola 12).
2.2Klec s jedinou možností
Cíl klece může vzniknout několika způsoby. Když ho splní jediná sada číslic, víme, co v kleci bude, i když ještě nevíme pořadí. Tahle informace se hned promítne do kandidátů: ostatní čísla z polí klece škrtneme. Nejčastěji jde o klece ze dvou polí; u tří polí v jedné řadě je jediná možnost jen u krajních cílů.
| Operace | Mřížka 4 × 4 | Mřížka 6 × 6 |
|---|---|---|
| + | 3 {1, 2}, 4 {1, 3}, 6 {2, 4}, 7 {3, 4} | 3 {1, 2}, 4 {1, 3}, 10 {4, 6}, 11 {5, 6} |
| − | 3 {1, 4} | 5 {1, 6} |
| × | všechny: 2, 3, 4, 6, 8, 12 | všechny kromě 6 a 12: 2, 3, 4, 5, 8, 10, 15, 18, 20, 24, 30 |
| ÷ | 3 {1, 3}, 4 {1, 4} | 4 {1, 4}, 5 {1, 5}, 6 {1, 6} |
U tří polí v jedné řadě mřížky 6 × 6 mají jedinou sadu součty 6 {1, 2, 3}, 7 {1, 2, 4}, 14 {3, 5, 6} a 15 {4, 5, 6} a součiny 6, 8, 10, 15, 18, 20, 36, 40, 48, 72, 90 a 120 – tedy 12 ze 16 možných součinů. Násobení je obecně „jednoznačnější“ než sčítání, protože rozklad na prvočinitele nese víc informace (kapitola 10).
Hledejte krajní cíle: nejmenší a největší součet, který klec může mít (3 a 2N − 1 pro dvě pole), a rozdíl N − 1, který dá jen 1 a N. U součinu stačí vidět velké prvočíslo: v mřížce 6 × 6 obsahuje každý součin dělitelný pěti číslici 5.
2.3Poslední volné pole v řádku nebo sloupci
Když jsou v řádku vyplněna všechna pole kromě jednoho, chybí v něm jediné číslo a to patří do volného pole. Je to nejjednodušší případ techniky Jediný kandidát z kapitoly 4 a hra ho tak také pojmenuje. Podobně funguje poslední volné pole klece – to se ale dopočítává z cíle (kapitola 3).
V mřížce 4 × 4 je v 1. řádku klec 7+ ze dvou polí a jednopolová klec 1. Klec 7+ je {3, 4}, jednička je zadaná, takže na zbylé pole řádku zbývá jen 2 – bez jakéhokoli zkoušení.
2.4Pořadí prvních tahů
- Zapište všechny jednopolové klece a škrtněte jejich čísla v řádcích a sloupcích.
- Projděte klece s jedinou možností a jejich sady zapište tužkou do polí.
- Hledejte řady, kde už z klecí víte skoro vše – poslední volné pole i dvojice, které se „zamknou“.
Klec s jedinou sadou ještě neříká pořadí. Kdo do klece 7+ napíše rovnou 3 a 4 zleva doprava, hádá. Pořadí rozhodne až řádek nebo sloupec, kde jedno z čísel už je.
2.5Procvičení
- Začněte jednopolovými klecemi a klecemi s jedinou možností.
- Krajní cíle (nejmenší a největší součet, rozdíl N − 1) mají jedinou sadu.
- Součiny jsou většinou jednoznačné; v 6 × 6 mají dvě sady jen 6 a 12.
- Sada není pořadí – to určí řádky a sloupce.
Kandidáti klecezáklady
Většina klecí má víc možností než jednu. Řešitel si proto napíše rozklad cíle – všechny sady číslic, které cíl dají – a nechá v polích klece jen ta čísla, která se v některé sadě objeví a zároveň se tam vejdou kvůli řádkům a sloupcům. Tomu se říká Kandidáti klece. Když v kleci zbývá jediné volné pole, dopočítá se z cíle: Poslední pole klece. Obě techniky tvoří úroveň 2.
Rozklad cíle je jako seznam způsobů, jak zaplatit účet přesně. Když víte, že jedna bankovka už je utracená jinde, z celého seznamu zbude třeba jen jedna možnost – a víte, co je v peněžence.
+Teorie: rozklady cíle, rozdíl a podíl, opakování v kleci a dvě techniky úrovně 2
3.1Sada a n-tice
Rozklad cíle je výčet všech sad číslic (multimnožin), které cíl dají. N-tice je navíc přiřazení čísel konkrétním polím klece. Klec ze dvou polí v řadě má z každé sady dvě n-tice (a, b) a (b, a); klec do L se sadou {2, 2, 3} má jen jednu, protože obě dvojky musí stát v rozích, které nesdílejí řádek ani sloupec. Řešitel i hra pracují s n-ticemi: je v nich zachycen tvar klece i pravidlo řad.
Kde T(K) je množina n-tic klece. Slovy: číslo zůstane kandidátem pole, jen když existuje n-tice, která ho na tom místě má a ve všech ostatních polích klece používá jen jejich současné kandidáty.
3.2Rozdíl a podíl
Klece s odčítáním a dělením mají vždy dvě pole a sady se dají vypsat zpaměti.
| Cíl | 4 × 4 | 6 × 6 |
|---|---|---|
| 1− | {1, 2}, {2, 3}, {3, 4} | {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6} |
| 2− | {1, 3}, {2, 4} | {1, 3}, {2, 4}, {3, 5}, {4, 6} |
| 3− | {1, 4} | {1, 4}, {2, 5}, {3, 6} |
| 4− | – | {1, 5}, {2, 6} |
| 5− | – | {1, 6} |
| 2÷ | {1, 2}, {2, 4} | {1, 2}, {2, 4}, {3, 6} |
| 3÷ | {1, 3} | {1, 3}, {2, 6} |
| 4÷ | {1, 4} | {1, 4} |
| 5÷, 6÷ | – | {1, 5}, {1, 6} |
Užitečné jsou hlavně čísla, která v rozkladu chybějí. Klec 4− v 6 × 6 nemůže obsahovat 3 ani 4, klec 3÷ nemůže obsahovat 4 ani 5 a klec 2÷ nemůže obsahovat 5. Klec 1− naopak připouští všechna čísla a sama o sobě nepomůže – zato v ní vždy sousedí dvě po sobě jdoucí čísla, tedy jedno sudé a jedno liché (kapitola 5).
3.3Součet a součin
U součtu pomáhají meze. Klec z k polí v jedné řadě má součet aspoň 1 + 2 + … + k a nejvýš N + (N − 1) + … + (N − k + 1); čím blíž je cíl krajům, tím méně sad. U součinu se vyplatí rozložit cíl na prvočinitele: 48 = 2⁴ · 3, takže v kleci 48× z příkladu v kapitole 1 musí být trojka a čtyři dvojky „rozdělené“ do čísel 2 a 4 – odtud sady {2, 2, 3, 4} a {1, 3, 4, 4}. Ve čtyřech polích jedné řady mřížky 4 × 4 by taková klec být nemohla: tam je součin vždy 1 · 2 · 3 · 4 = 24.
3.4Klece s opakováním
Klec, která zabírá aspoň dva řádky a dva sloupce (tvar L, T, čtverec 2 × 2), smí obsahovat stejné číslo dvakrát – v polích, která nesdílejí řadu. V kalkulačce jsou takové sady oranžově. Typická past: klec 4× do L v mřížce 4 × 4 nemá sadu {1, 4} (chybí třetí číslo), ale má {1, 1, 4} a {1, 2, 2}.
Opakování se týká jen tvaru klece. Klec ze tří polí v jedné řadě má číslice vždy různé, a proto má klec 6+ v řádku jedinou sadu {1, 2, 3}, kdežto stejná klec do L i sadu {1, 1, 4}.
3.5Technika Kandidáti klece
Řešitel vezme klec, projde všechny její n-tice a nechá jen ty, které souhlasí se současnými kandidáty polí. Čísla, která v žádné zbylé n-tici na daném místě nejsou, škrtne. V příkladu z kapitoly 1 klec 2÷ (ř1s1, ř2s1) připouští sady {1, 2} a {2, 4}, takže z ř1s1 zmizí 3. Po každém zápisu do řádku nebo sloupce se vyplatí klec projít znovu – n-tice ubývají.
Dvě pole v řádku: sady {2, 6} a {3, 5}. Když už je v řádku 6, zbývá jen {3, 5} – klec se změnila v klec s jedinou možností a v řádku navíc víme, kde nejsou 3 a 5.
3.6Technika Poslední pole klece
Když jsou v kleci vyplněná všechna pole kromě jednoho, chybějící číslo se dopočítá: u součtu odečtením, u součinu vydělením, u rozdílu a podílu jsou dvě možnosti (známé číslo plus nebo minus rozdíl, krát nebo děleno podílem), z nichž obvykle jen jedna leží mezi 1 a N nebo projde řadami.
3.7Procvičení
- Rozklad cíle je seznam sad; n-tice přidává pořadí a tvar klece.
- Kandidáti klece: nechte jen čísla, která jsou v nějaké n-tici slučitelné s ostatními poli.
- V klecích přes dva řádky a dva sloupce se smí opakovat číslo – v polích bez společné řady.
- Poslední pole klece se dopočítá z cíle.
Řádky a sloupcezáklady
Klece říkají, co v nich bude; řádky a sloupce říkají, kde. Řešení kalkudoku je latinský čtverec, a tak platí stejné dvě techniky jako v sudoku: Jediný kandidát (poli zbylo jediné možné číslo) a Skrytý singl (číslo má v řádku nebo sloupci jediné možné pole). S poznámkami tužkou se obě hledají snadno. Laboratoř je plnohodnotný hrací stůl s tužkou, gumou a nápovědou.
Poznámky tužkou jsou jako seznam úkolů na lednici: dokud je v hlavě, něco vypadne. Když je na papíře, škrtáte a nakonec v jednom řádku zbude jediná položka.
+Teorie: latinský čtverec, singly, poznámky tužkou a kontrola
4.1Latinský čtverec
Latinský čtverec řádu n je mřížka n × n se symboly 1 až n, ve které je každý symbol v každém řádku i sloupci právě jednou. Řešení kalkudoku je latinský čtverec a klece z nich vybírají jediný. Pro 4 × 4 existuje 576 latinských čtverců, pro 6 × 6 už 812 851 200 (kapitola 9). Každé pole má 2(N − 1) sousedů – pole ve stejném řádku nebo sloupci – a zápis čísla ho škrtne u všech.
4.2Technika Jediný kandidát
Pole má jediného kandidáta, když všechna ostatní čísla vylučují sousedé nebo klec. Nejjednodušší případ je poslední volné pole řádku nebo sloupce. Hra i laboratoř tuto techniku hledají jako první z „řadových“ technik, protože ji stačí vidět v jednom poli.
4.3Technika Skrytý singl
Číslo d musí být v každém řádku i sloupci. Když v řadě zbývá jediné pole, kde d ještě je kandidátem, patří tam – i kdyby to pole mělo jiné kandidáty. Skrytý singl se hledá „po číslech“: vezměte číslo a projděte řady, kde ještě chybí.
V kalkudoku je skrytý singl častější než v sudoku, protože klece kandidáty silně zužují: klec 4÷ v mřížce 6 × 6 nechá v obou polích jen 1 a 4, a pokud jinde v řádku jednička nemůže být, je jasné, kam patří.
4.4Poznámky tužkou
- Kandidáty pište do polí klecí s jedinou možností hned – jejich sada je jistá.
- U ostatních klecí pište kandidáty, až když se řady vyčerpají; jinak je mřížka plná čísel, která nic neříkají.
- Po každém zápisu škrtněte číslo v řádku a sloupci a podívejte se na klece, kterých se zápis dotkl – jejich n-tice ubyly.
Zkušení řešitelé si u klece píšou do rohu jen sady (například „16 / 25“ u 7+), ne kandidáty do každého pole. Teprve když sada zbude jediná, rozepíšou ji do polí. Tlačítko „Kandidáti z klecí“ v laboratoři ukazuje, kolik by se toho napsalo.
4.5Kontrola chyb
Chyba v kalkudoku se ukáže pozdě: dvě stejná čísla v řadě nebo plná klec, která nedává cíl. Rychlá kontrola hotového řádku je součet 1 + 2 + … + N (10 pro 4 × 4, 21 pro 6 × 6) a součin N! (24, 720). Kdo si kontroluje součty po každém dokončeném řádku, najde chybu, dokud je malá.
Součet řádku sám o sobě nestačí: řádek 1, 3, 3, 4, 4 v mřížce 5 × 5 má součet 15 a přesto je špatně. Kontrolujte i opakování, nejen součet.
4.6Procvičení
- Řešení je latinský čtverec: klece říkají co, řady kde.
- Jediný kandidát: poli zbylo jedno číslo. Skrytý singl: číslu zbylo v řadě jedno pole.
- Kandidáty pište cíleně – nejdřív u klecí s jedinou možností.
- Hotový řádek kontrolujte součtem, součinem i opakováním.
Povinné číslicepokročilí
Klec nemusí mít jedinou možnost, a přesto o ní víme něco jistého: číslo, které je ve všech jejích n-ticích. Klec 2÷ v mřížce 4 × 4 je {1, 2} nebo {2, 4} – dvojka v ní bude vždy. Když navíc povinné číslo leží ve všech n-ticích ve stejném řádku nebo sloupci, nemůže být nikde jinde v této řadě. To je technika Povinná číslice klece, první technika úrovně 3.
Je to jako s klíči od bytu: nevíte, ve které kapse kabátu jsou, ale víte, že jsou v kabátě. Takže je nemusíte hledat v tašce.
+Teorie: povinná číslice, klec v jedné řadě, prvočísla a parita
5.1Povinná číslice klece
Číslo d je povinné pro klec K, když je v každé n-tici, která ještě odpovídá kandidátům. Samo o sobě to nic neškrtá. Užitečné je, když d leží ve všech těch n-ticích v polích jedné řady R – pak ho klec v řadě R „zabere“ a ve zbytku řady ho škrtneme.
Je to obdoba „zamčených kandidátů“ ze sudoku. Rozdíl je v tom, že místo bloku tu „zamyká“ klec a o tom, zda d v kleci je, rozhoduje aritmetika cíle.
5.2Klec v jedné řadě
Nejčastější případ: klec leží celá v jednom řádku nebo sloupci. Pak jsou všechna povinná čísla klece zároveň zamčená v řadě. Klec 7+ ze tří polí v řádku mřížky 6 × 6 je jen {1, 2, 4}, takže 1, 2 a 4 ve zbytku řádku škrtneme a na zbylá tři pole zůstanou 3, 5 a 6. Stejně klec 2÷ ve dvou polích mřížky 4 × 4: dvojka je povinná a ve zbytku řady být nemůže.
Mřížka 6 × 6, klec 60× ze tří polí v 6. sloupci: sady {2, 5, 6} a {3, 4, 5}. Pětka je v obou, takže je povinná. Ve zbytku 6. sloupce pětku škrtneme – to je první příklad v laboratoři.
5.3Klec přes dvě řady
Klec do L nebo čtverec 2 × 2 zasahuje do dvou řádků i dvou sloupců. Povinné číslo pak nemusí ležet v jedné řadě – ale často leží, protože kandidáti už některé pozice vyloučili. Laboratoř to ukazuje na klecích 54× (čtverec 2 × 2) a 17+ (čtyři pole): povinné číslo vychází ve všech zbylých n-ticích v polích 1. řádku.
5.4Prvočísla 5 a 7
V mřížce 6 × 6 je 5 jediné číslo dělitelné pěti. Každý součin dělitelný pěti proto obsahuje pětku – a dělitelný 25 obsahuje pětky dvě (možné jen v kleci přes dva řádky i dva sloupce). V mřížkách 7 × 7 až 9 × 9 platí totéž pro 7 a v mřížkách 5 × 5 až 9 × 9 pro 5. Naopak součin, který pětkou dělitelný není, pětku neobsahuje – a to je stejně cenná informace: z polí klece ji škrtneme.
Pro prvočísla větší než N/2 je v mřížce jediný násobek, totiž p samo. Pro menší prvočísla to neplatí: v mřížce 6 × 6 jsou násobky tří 3 a 6, a součin dělitelný třemi tedy obsahuje trojku nebo šestku.
5.5Parita
Sudost a lichost dává rychlé škrty u součtových klecí. Lichý součet má lichý počet lichých čísel. Klec 1− obsahuje vždy jedno sudé a jedno liché číslo. Řádek mřížky 6 × 6 má tři lichá a tři sudá čísla; když klece v řádku „spotřebují“ všechna tři lichá, zbylá pole jsou sudá.
U každé klece si položte tři otázky: je v ní určitě nějaké číslo? (povinná číslice), je v ní určitě nějaké číslo vyloučené? (chybí v rozkladu), leží v jedné řadě? Klec, která odpoví „ano“ na první i třetí otázku, škrtá ve své řadě.
Povinné číslo klece přes dva řádky nemusí být zamčené v žádné řadě. Klec 2÷ do svislé dvojice je v jednom sloupci – dvojku škrtneme ve sloupci, ale ne v řádcích. Škrtejte jen v řadě, kterou mají společnou všechny n-tice.
5.6Procvičení
- Povinná číslice je ve všech n-ticích klece.
- Leží-li ve všech n-ticích v téže řadě, ve zbytku řady ji škrtneme.
- Velká prvočísla se v součinu neschovají: dělitelnost pěti nebo sedmi znamená pětku nebo sedmičku.
- Parita pomáhá u součtů a u klecí 1−.
Pravidlo součtu řádku a sloupcepokročilí
Každý řádek mřížky 6 × 6 má součet 21 a součin 720 – bez ohledu na to, jak je vyplněný. Když v řádku leží celé klece se známým součtem a zbude jediné další pole, dopočítá se odečtením. Stejně to jde pro sloupec a pro oblast několika sousedních řad. To je Pravidlo součtu řádku (technika úrovně 4), které zná každý řešitel kakura a Killer sudoku – v kalkudoku má navíc součinovou verzi.
Je to jako vážení zavazadel: víte, kolik váží celý kufr, a víte, kolik váží všechny tašky v něm kromě jedné. Poslední tašku nemusíte otevírat.
+Teorie: součet a součin oblasti, vnitřní zbytek, vyčnívající pole
6.1Součet a součin řady
Řádek i sloupec obsahují čísla 1 až N, takže jejich součet a součin jsou pevné. Oblast z w sousedních řádků (nebo sloupců) má w-násobný součet a w-tou mocninu součinu.
| N | součet řady | součin řady | součet mřížky |
|---|---|---|---|
| 4 | 10 | 24 | 40 |
| 5 | 15 | 120 | 75 |
| 6 | 21 | 720 | 126 |
| 7 | 28 | 5 040 | 196 |
| 8 | 36 | 40 320 | 288 |
| 9 | 45 | 362 880 | 405 |
6.2Vnitřní zbytek
Vezměte oblast řad a klece, které v ní leží celé a mají známý součet. Pokud oblast obsahuje kromě nich jediné další volné pole (a případně už vyplněná pole), je jeho hodnota součet oblasti minus součty klecí minus vyplněná čísla. Anglicky se mu říká innie.
6.3Vyčnívající pole
Obrácený případ: klece pokrývají celou oblast a z jedné z nich vyčnívá ven jediné volné pole. Součet klecí minus součet oblasti je pak hodnota vyčnívajícího pole (outie). Laboratoř počítá obě verze; řešitel průvodce je pojmenuje stejně – Pravidlo součtu řádku.
Mřížka 5 × 5, řádky 1 a 2 (součet 30). Pokrývají je klece se součty 8, 9, 7 a 10 (celkem 34), přičemž klec 10 má jedno pole ve 3. řádku. To pole je 34 − 30 = 4.
6.4Známý součet i u násobení a dělení
Klec nemusí být součtová, aby měla známý součet. Klec 30× ze dvou polí mřížky 6 × 6 je {5, 6} a má součet 11; klec 5− je {1, 6} se součtem 7. Klec 2÷ je {1, 2}, {2, 4} nebo {3, 6} a součet zatím známý nemá – dokud kandidáti nevyřadí dvě ze tří sad.
6.5Pravidlo součinu
Stejná úvaha funguje se součinem: oblast w řad má součin (N!)^w, klece uvnitř se známým součinem se vydělí a zbyde hodnota pole. Hodí se tam, kde v oblasti převažují součinové klece se sadou, ale neznámým součtem. Řešitel průvodce součinovou verzi zkouší až po součtové a jen pro oblasti, u kterých se součin vejde do přesné aritmetiky počítače (v mřížce 9 × 9 nejvýš dvě řady).
Pravidlo součtu se vyplatí hledat, když se úloha „zasekne“ a v některé řadě jsou samé dlouhé klece. Projděte okrajové řady (1. a N-tou) a dvojice řad – tam klece nejčastěji končí přesně na hranici.
Klec, která přesahuje z oblasti ven, do součtu oblasti nepatří celá. Kdo ji započítá, dostane nesmysl – například záporné číslo nebo číslo větší než N. To je zároveň dobrá kontrola: výsledek musí ležet mezi 1 a N.
6.6Procvičení
- Řada má součet N(N + 1)/2 a součin N!; oblast w řad w-násobek a w-tou mocninu.
- Vnitřní zbytek: oblast minus klece uvnitř. Vyčnívající pole: klece minus oblast.
- Známý součet mají i součinové klece s jedinou sadou.
- Výsledek musí ležet mezi 1 a N – jinak je v počtu chyba.
Dvojice, trojice a X-wingpokročilí
Když klece a singly dojdou, přicházejí na řadu vzory v kandidátech, které zná každý řešitel sudoku. Nahá dvojice: dvě pole řady mají jen tytéž dva kandidáty, takže si je rozdělí a jinde v řadě nejsou. Skrytá dvojice: dvě čísla mohou v řadě stát jen ve dvou polích, takže ta pole jiné kandidáty nepotřebují. Nahá trojice je totéž pro tři pole. A X-wing se dívá na jedno číslo ve dvou řádcích a dvou sloupcích naráz. Dvojice a trojice patří do úrovně 3, X-wing do úrovně 4.
Dva kamarádi, kteří jdou do kina jen spolu a jen na dvě sedadla, ta dvě sedadla obsadí – a nikdo jiný si na ně nesedne. Kdo vidí takovou dvojici, škrtá u všech ostatních.
+Teorie: nahé a skryté podmnožiny, X-wing a jak je hledat
7.1Nahá dvojice a trojice
Nahá podmnožina velikosti k je k polí jedné řady, jejichž kandidáti dohromady tvoří jen k čísel. Ta čísla se musí rozdělit mezi tato pole (žádné jiné tam nepasují a každé pole nějaké číslo dostane), takže ve zbytku řady být nemohou.
U trojice nemusí mít každé pole všechny tři kandidáty: pole {2, 4}, {4, 5} a {2, 5} tvoří nahou trojici {2, 4, 5}. Na obr. 7.1 je nahá dvojice z úlohy 6 × 6, kde po škrtech v 1. a 2. řádku spadne další kaskáda singlů.
7.2Skrytá dvojice
Skrytá podmnožina velikosti k jsou k čísel, která v řadě mohou stát jen v k polích. Ta pole tedy obsadí právě tato čísla a ostatní kandidáty z nich škrtneme. Nahé a skryté podmnožiny jsou dvě strany téže mince: v řadě s m volnými poli odpovídá nahé podmnožině velikosti k skrytá podmnožina velikosti m − k ve zbylých polích. Průvodce i hra hledají nahé dvojice a trojice a skryté dvojice.
7.3Dvojice z klecí
V kalkudoku vznikají dvojice často samy od sebe: klec ze dvou polí v jedné řadě s jedinou sadou {a, b} je nahá dvojice hned od začátku. Proto ji řešitel najde už jako klec s jedinou možností a povinnou číslici klece – technika Nahá dvojice přijde na řadu jen tam, kde se dvojice složí z kandidátů různých klecí.
7.4X-wing
Vezměte jedno číslo d. Když v řádcích a a b může d stát jen ve stejných dvou sloupcích c a e, pak jedna d leží v (a, c) a druhá v (b, e), nebo naopak. V obou případech jsou sloupce c a e „obsazené“ d z řádků a a b a ve zbytku sloupců c a e d škrtneme. Totéž platí s prohozenými řádky a sloupci.
X-wing hledejte po číslech, ne po polích: pro číslo d si spočítejte, v kolika polích může stát v každém řádku. Řádky, kde jsou jen dvě místa, porovnejte – shodují-li se sloupce, máte X-wing. V mřížkách do 6 × 6 je to rychlé, protože řádků je málo.
V kalkudoku nejsou bloky, takže „ryby“ a podmnožiny pracují jen s řádky a sloupci. Klec ale řadu nenahradí: dvě pole v jedné kleci, která neleží ve stejné řadě, smí mít stejné číslo, a nahá dvojice z nich proto nevznikne.
7.5Jak často se techniky objevují
Ve vzorku 6 100 úloh 4 × 4 až 7 × 7 použil řešitel povinnou číslici klece v 1 250 úlohách, X-wing ve 128, nahou dvojici ve 103, skrytou dvojici v 69 a nahou trojici ve 32. Kalkudoku je tedy „aritmetičtější“ než sudoku: většinu práce odvedou klece a vzory v kandidátech přicházejí na řadu až u těžkých úloh.
7.6Procvičení
- Nahá dvojice/trojice: k polí, k kandidátů – škrtáme ve zbytku řady.
- Skrytá dvojice: dvě čísla, dvě pole – škrtáme jiné kandidáty v těch polích.
- X-wing: číslo ve dvou řádcích jen ve dvou stejných sloupcích – škrtáme ve zbytku sloupců.
- V kalkudoku pracují tyto vzory jen s řádky a sloupci, ne s klecemi.
Souhra klecí a variantypokročilí
Nejtěžší úlohy průvodce potřebují souhru klecí: řešitel vezme klec s několika n-ticemi, každou zkusmo dosadí a podívá se, co to udělá s řádky, sloupci a sousedními klecemi. N-tice, po které by sousední klec nešla splnit nebo by v řadě nezbylo místo pro nějaké číslo, vypadne. Je to technika úrovně 5 – a zároveň hranice mezi logikou a hádáním. Kapitola pak představí varianty: kalkudoku bez znamének, jen se sčítáním a velké mřížky.
Souhra klecí je jako zkoušení klíčů: nezkoušíte je naslepo do konce, ale jen jeden zámek dopředu. Když klíč nepasuje hned do vedlejšího zámku, víte, že to není on.
+Teorie: souhra klecí, hranice logiky, varianty a řešení na čas
8.1Souhra klecí
Technika pracuje s jednou klecí K a její množinou n-tic F, které ještě odpovídají kandidátům. Pro každou n-tici t ∈ F se provede zkusmé dosazení: čísla se zapíšou, v jejich řadách se škrtnou a pak se zkontroluje
- že každé číslo má v každé dotčené řadě ještě aspoň jedno možné pole,
- že každé dotčené pole má ještě aspoň jednoho kandidáta,
- že každá klec, která sdílí řadu s klecí K, má ještě aspoň jednu n-tici.
N-tice, která některou kontrolu nesplní, je nemožná. Kandidáti, kteří zůstanou jen v nemožných n-ticích, se škrtnou. Řešitel průvodce tu přestane: nekombinuje víc klecí naráz a nedosazuje dál.
8.2Kde končí logika a začíná hádání
Každé zkusmé dosazení je formálně důkaz sporem: „kdyby tu bylo (5, 3, 3), klec 72× by nešla splnit, tedy tu (5, 3, 3) není“. Rozdíl mezi logikou a hádáním je v délce: souhra klecí kontroluje jen bezprostřední důsledky, které člověk udrží v hlavě. Kdo dosazuje a pokračuje několik kroků dopředu, dělá backtracking z kapitoly 11. Ve vzorku 6 100 úloh potřebovalo souhru klecí 340 úloh a 88 úloh (1,4 %) nevyřešil řešitel průvodce ani s ní – ty hra nepoužívá.
8.3Varianta bez znamének
V této variantě klec ukazuje jen cíl a řešitel musí operaci odvodit. Pomáhají meze: součet dvou čísel do N je nejvýš 2N − 1, rozdíl nejvýš N − 1, podíl nejvýš N. Cíl větší než 2N − 1 je tedy součin; cíl 1 ve dvou polích je jen rozdíl. U tří a více polí připadá v úvahu sčítání a násobení.
Skrytá operace výrazně zvyšuje počet možností: klec 2 ze dvou polí v mřížce 6 × 6 připouští šest sad (rozdíl, podíl i součin), se znaménkem − jen čtyři. Proto mají úlohy bez znamének víc klecí a víc jednopolových klecí. V simulaci z kapitoly 10 mělo jediné řešení 25,3 % náhodných úloh 6 × 6 bez znamének (27,5 % se znaménky).
8.4Jen sčítání a jiné varianty
Kalkudoku jen se sčítáním je blízký příbuzný Killer sudoku bez bloků: rozklady součtů jsou nejednoznačnější než součiny a pravidlo součtu řádku hraje větší roli. V simulaci mělo jediné řešení 24,0 % náhodných úloh 6 × 6 jen se sčítáním. Mezi další varianty patří úlohy s nulou, se zápornými čísly nebo s jinými operacemi (mocnina, zbytek po dělení). Hra průvodce nabízí variantu bez znamének, variantu pro děti jen se sčítáním a odčítáním a velkou mřížku 9 × 9.
8.5Velké mřížky
Mřížka 9 × 9 má 81 polí a typicky kolem 30 klecí. Součiny rostou (řada má součin 362 880), rozklady součtů se větví – klec ze čtyř polí v řadě se součtem 20 má 12 sad. Pomáhá prvočíslo 7: každý součin dělitelný sedmi obsahuje sedmičku, a pětka obdobně. Pravidlo součtu řádku je na velké mřížce nejsilnější zbraní, protože klece často kopírují hranice řad.
8.6Řešení na čas
Statistika řešitele dává užitečné pořadí i pro rychlé řešení: Jediný kandidát potřebovaly skoro všechny úlohy vzorku (6 056 ze 6 100), klec s jedinou možností 5 822, skrytý singl 5 430, jednopolovou klec 5 170, kandidáty klece 4 286 a poslední pole klece 3 926. Kdo chce řešit rychle, má tyto techniky dělat bez přemýšlení a teprve pak hledat povinné číslice (1 250 úloh) a pravidlo součtu (180). Poznámky pište jen u klecí s jednou nebo dvěma sadami.
Když se zaseknete, vraťte se k největším klecím. Jejich n-tice se po několika zápisech v okolí změnily a často z nich zbyla jediná sada – nebo je čas na pravidlo součtu řádku.
Souhra klecí je silná, ale snadno se v ní splete. Zkoušejte n-tici vždy jen proti řadám a klecím, kterých se přímo dotkne, a výsledek si zapište. Řetěz „kdyby… tak… tak…“ delší než dva kroky už je hádání.
8.7Procvičení
- Souhra klecí: dosaďte n-tici, zkontrolujte řady a sousední klece, nemožné n-tice vyřaďte.
- Jeden krok dopředu je logika, dlouhý řetěz pokusů už hádání.
- Bez znamének pomáhají meze: velký cíl je součin, cíl 1 je rozdíl.
- Na čas: singly a klece bez přemýšlení, pak povinné číslice a pravidlo součtu.
Latinské čtvercemistr a věda
Každé řešení kalkudoku je latinský čtverec: tabulka n × n, kde je v každém řádku a sloupci každý symbol právě jednou. Matematici je studují přes dvě stě let. Kolik jich je? Pro n = 1 až 5 je to 1, 2, 12, 576 a 161 280 – a pak počty explodují. Kapitola počítá čtverce v prohlížeči, vypráví Eulerovu úlohu o 36 důstojnících a ukazuje, proč latinské čtverce používají zemědělci a statistici při plánování pokusů.
Šest pluků, z každého šest důstojníků šesti hodností: lze je postavit do čtverce 6 × 6 tak, aby v každém řádku i sloupci byl každý pluk i každá hodnost jednou? Euler si myslel, že ne – a měl pravdu, ale důkaz přišel až o 118 let později.
+Teorie: počty čtverců, redukce, ortogonalita, Euler a plánování pokusů
9.1Kolik je latinských čtverců
Označme L(n) počet latinských čtverců řádu n se symboly 1 až n a R(n) počet redukovaných, jejichž první řádek i první sloupec je 1, 2, …, n. Z každého čtverce dostaneme redukovaný tak, že nejdřív permutujeme sloupce (první řádek seřadíme) a pak řádky 2 až n (seřadíme první sloupec). Obě permutace jsou jednoznačné, a proto
| n | R(n) redukovaných | L(n) všech |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 12 |
| 4 | 4 | 576 |
| 5 | 56 | 161 280 |
| 6 | 9 408 | 812 851 200 |
| 7 | 16 942 080 | 61 479 419 904 000 |
| 8 | 535 281 401 856 | 108 776 032 459 082 956 800 |
| 9 | 377 597 570 964 258 816 | 5 524 751 496 156 892 842 531 225 600 |
Žádný jednoduchý vzorec pro L(n) není známý. Ví se ale, jak rychle roste: logaritmus L(n) je přibližně n² ln(n/e²), takže L(n) ≈ (n/e²)^{n²}. Dolní odhad plyne z toho, že každý řádek lze přidat k předchozím mnoha způsoby (počet je dán permanentem matice), horní z obdobné úvahy pro libovolné 0/1 matice.
Mřížka 4 × 4 má 576 možných řešení. Každá klec úlohy z kapitoly 1 sama vyřadí většinu z nich: jednopolová klec 3 nechá 144 čtverců (čtvrtinu), klec 4÷ 96 a klec 48× jen 64. Všech sedm klecí dohromady nechá jediný čtverec. Zajímavost: úloha je „přeurčená“ – po vynechání kterékoli jedné klece má pořád jediné řešení. Ověřeno výčtem všech 576 čtverců.
9.2Ortogonální čtverce a Euler
Dva latinské čtverce A a B řádu n jsou ortogonální, když dvojice (Aij, Bij) probíhají všech n² kombinací právě jednou. Zapsané do jedné mřížky latinskými a řeckými písmeny tvoří řecko-latinský čtverec. Leonhard Euler se jimi zabýval v práci z roku 1782 a položil úlohu o 36 důstojnících, tedy otázku, zda existuje řecko-latinský čtverec řádu 6. Nenašel ho a vyslovil domněnku, že neexistuje pro žádné n = 4k + 2.
Pro n = 6 měl Euler pravdu: Gaston Tarry kolem roku 1900 probral všechny případy a ukázal, že dvojice ortogonálních čtverců řádu 6 neexistuje (prameny uvádějí rok 1900 i 1901). Pro ostatní řády tvaru 4k + 2 se ale Euler mýlil. V roce 1959 našel E. T. Parker řád 10 a R. C. Bose, S. S. Shrikhande a Parker pak dokázali (publikováno 1959–1960), že ortogonální dvojice existuje pro každé n kromě 2 a 6. Pro jejich protipříklady se vžila přezdívka „Eulerovi kazisvěti“.
Pro prvočíselné n stačí vzít čtverce (i + j) mod n a (2i + j) mod n; obecně pro mocninu prvočísla dává konečné těleso až n − 1 navzájem ortogonálních čtverců, a víc jich být nemůže. Takové úplné soustavy souvisejí s konečnými projektivními rovinami.
9.3Plánování pokusů
Latinské čtverce mají praktické využití ve statistice. Když se na pozemku zkouší pět odrůd a půda se mění v obou směrech (vlhkost, sklon), rozmístí se odrůdy podle latinského čtverce 5 × 5: každá je jednou v každém řádku i sloupci, a vliv řádků a sloupců se tak rozloží rovnoměrně. Takový plán rozpracoval a popularizoval statistik R. A. Fisher; v jeho knize o plánování pokusů z roku 1935 je latinský čtverec jedním ze základních plánů. Ortogonální čtverce pak dovolí do stejného pokusu přidat druhý faktor.
9.4Částečné latinské čtverce
Částečný latinský čtverec má některá pole vyplněná bez opakování v řadách. Otázka, zda ho jde doplnit na celý latinský čtverec, je obecně těžká – C. J. Colbourn v roce 1984 dokázal, že je NP-úplná (kapitola 11). Sudoku i kalkudoku jsou varianty této úlohy s dalšími omezeními.
9.5Procvičení
- Řešení kalkudoku je latinský čtverec; 4 × 4 jich má 576, 6 × 6 přes 812 milionů.
- L(n) = n! · (n − 1)! · R(n); redukované čtverce se počítají snáz.
- Ortogonální dvojice existuje pro každé n kromě 2 a 6 – Euler se u 6 trefil, jinde ne.
- Latinské čtverce slouží i v plánování pokusů.
Kombinatorika klecímistr a věda
Kolik sad číslic má cíl klece? Na tom stojí, jak silná je klec jako vodítko. Kapitola počítá rozklady pro všechny operace a velikosti mřížky, hledá nejjednoznačnější a nejvíc nejednoznačné cíle, vysvětluje, proč jsou součiny tak „výmluvné“, a simulací odhaduje, jak často má náhodně sestavená úloha jediné řešení.
Cíl klece je jako PSČ: některá čísla patří jedinému domu, jiná celé čtvrti. Kdo ví, která jsou která, pozná na první pohled, kde začít.
+Teorie: rozklady součtů a součinů, symetrie, prvočísla a simulace
10.1Rozklady součtů
Sady pro součet t z k různých čísel 1 až N jsou rozklady čísla t na k různých sčítanců nejvýš N. Rozložení je symetrické: záměna d → N + 1 − d převede sadu se součtem t na sadu se součtem k(N + 1) − t. Proto mají stejně sad krajní cíle (nejmenší a největší) a maximum je uprostřed.
Počet všech sad je \(\binom{N}{k}\): pro tři pole v mřížce 6 × 6 dvacet sad rozdělených mezi deset cílů 6 až 15 v poměru 1, 1, 2, 3, 3, 3, 3, 2, 1, 1 (obr. 10.1). Pro čtyři pole v mřížce 9 × 9 je to 126 sad mezi 21 cílů, nejvíc 12 u cíle 20 a jediná sada u cílů 10, 11, 29 a 30.
10.2Rozklady součinů
Součin nese víc informace, protože rozklad na prvočinitele je jednoznačný. Dvě různé sady se stejným součinem vzniknou jen tehdy, když se prvočinitele dají přeskupit do jiných čísel do N – v mřížce 6 × 6 jen 6 = 1 · 6 = 2 · 3 a 12 = 2 · 6 = 3 · 4.
| Mřížka, klec | + | − | × | ÷ |
|---|---|---|---|---|
| 4 × 4, 2 pole | 4 z 5 | 1 ze 3 | 6 z 6 | 2 ze 3 |
| 6 × 6, 2 pole | 4 z 9 | 1 z 5 | 11 z 13 | 3 z 5 |
| 6 × 6, 3 pole | 4 z 10 | – | 12 z 16 | – |
| 9 × 9, 2 pole | 4 z 15 | 1 z 8 | 26 z 31 | 5 z 8 |
| 9 × 9, 3 pole | 4 z 19 | – | 39 z 60 | – |
10.3Nejvíc nejednoznačné cíle
U rozdílu je nejhorší cíl 1: N − 1 dvojic sousedních čísel. U podílu cíl 2 (dvojice {k, 2k} pro k ≤ N/2). U součtu prostřední cíle, u součinu čísla s mnoha děliteli – v mřížce 9 × 9 mají tři pole v řadě nejvíc sad u cílů 24, 48 a 72 (po třech). Klece s takovými cíli jsou v úloze „výplň“: samy nic neřeknou, ale pomohou, až se okolí vyplní.
10.4Klece s opakováním
Klece přes dva řádky a dva sloupce přidávají sady s opakovanou číslicí, takže mají víc možností než stejně velké klece v řadě. Klec 6+ ze tří polí v řadě mřížky 6 × 6 má jedinou sadu, do tvaru L dvě.
10.5Simulace jednoznačnosti
Kolik náhodně sestavených úloh má jediné řešení? Odpověď se počítá těžko, a tak ji laboratoř odhaduje simulací Monte Carlo. S výchozími semínky a 1 000 úlohami vyšlo:
| Varianta | 4 × 4 | 5 × 5 | 6 × 6 |
|---|---|---|---|
| všechny operace | 28,2 % | 31,8 % | 27,5 % |
| jen sčítání | 23,1 % | 25,7 % | 24,0 % |
| bez znamének | 23,3 % | 27,9 % | 25,3 % |
| klece 2–4 pole | 18,8 % | 23,3 % | 21,3 % |
Simulace odhaduje podíl pro tento náhodný model, ne „pro všechny možné úlohy“. Rozdíly mezi sloupci tabulky jsou z velké části dané tím, že větší mřížky mají víc klecí; rozdíly menší než asi 4 procentní body mohou být jen náhoda. Spolehlivě z ní plyne jen kvalitativní závěr: náhodná úloha většinou jednoznačná není, jednopolové klece a součiny pomáhají, samé sčítání a velké klece škodí.
10.6Procvičení
- Součty mají symetrické rozložení sad; jedinou sadu jen na krajích.
- Součiny jsou většinou jednoznačné díky rozkladu na prvočinitele.
- Nejvíc nejednoznačné: rozdíl 1, podíl 2, prostřední součty, čísla s mnoha děliteli.
- Náhodná úloha má jediné řešení jen asi ve čtvrtině případů – generátor proto opravuje.
Algoritmy a složitostmistr a věda
Počítač vyřeší kalkudoku 9 × 9 za zlomek sekundy – ale jak? Kapitola ukazuje čtyři přístupy na stejných úlohách: logický řešitel, který napodobuje člověka, naivní backtracking, backtracking s kontrolou klecí a backtracking s propagací omezení, kterou používá generátor průvodce. Pak převede kalkudoku na úlohu přesného pokrytí (exact cover) a na splnitelnost formule (SAT) a vysvětlí, co se ví o jeho výpočetní složitosti.
Naivní počítač zkouší klíče od svazku jeden po druhém. Chytrý se nejdřív podívá na zámek a polovinu klíčů odloží, protože nemají správný tvar. Propagace omezení je právě to odkládání.
+Teorie: omezení, backtracking, propagace, exact cover, SAT a složitost
11.1Kalkudoku jako úloha s omezeními
V řeči umělé inteligence je kalkudoku úloha splňování omezení: proměnné jsou pole, doména každého je {1, …, N} a omezení jsou dvojí – „všechna různá“ pro každý řádek a sloupec a pro každou klec tabulka povolených n-tic. Tabulka n-tic je přesně to, co počítá kalkulačka klece v kapitole 3. Logické techniky z kapitol 2 až 8 jsou různě silné formy odvozování nad těmito omezeními.
11.2Backtracking
Naivní backtracking plní pole v pevném pořadí, hlídá jen opakování v řadách a klec zkontroluje, až když je celá vyplněná. Backtracking s kontrolou klecí po každém dosazení ověří, že klec ještě jde doplnit nějakou n-ticí slučitelnou s řadami. Druhá varianta odhalí spor dřív, a proto prohledá méně uzlů.
11.3Propagace omezení a MRV
Propagace opakuje odvozování, dokud se něco mění: z každé klece nechá jen kandidáty obsažené v n-ticích (to je obecná hranová konzistence pro tabulková omezení), zapíše jediné kandidáty a skryté singly. Když propagace sama nevyřeší vše, algoritmus vybere pole s nejméně kandidáty (MRV, minimum remaining values), zkusí jeho čísla a v každé větvi znovu propaguje. Úrovně 1 a 2 tím vyřeší bez větvení, protože propagace obsahuje všechny jejich techniky.
Úloha 2 z laboratoře (úroveň 2): naivní backtracking 154 uzlů, s kontrolou klecí 48, s propagací 1 – vyřeší ji už propagace v kořeni. Úloha 4 (úroveň 5, potřebuje souhru klecí): 61, 35 a 2 uzly. Propagace sice nezná souhru klecí, ale jeden pokus s následnou propagací ji nahradí.
11.4Přesné pokrytí
Úloha exact cover (přesné pokrytí): je dána 0/1 matice a hledáme výběr řádků, ve kterém má každý sloupec právě jednu jedničku. Kalkudoku se na ni převede takto: sloupce jsou „pole p je vyplněné“ (N² sloupců), „řádek r obsahuje d“ (N²) a „sloupec s obsahuje d“ (N²); řádky matice jsou dvojice (klec, n-tice) a každý pokrývá pole své klece a dvojice (řada, číslo) svých čísel. Přesné pokrytí pak vybere pro každou klec jednu n-tici tak, aby každé číslo bylo v každé řadě právě jednou.
Pro úlohu z kapitoly 1 je to 48 sloupců a 31 řádků. Na přesné pokrytí existuje Knuthův Algoritmus X s technikou Dancing Links, který je v podstatě backtracking s MRV nad sloupci matice – stejný princip, jaký používá řešitel průvodce.
11.5Převod na SAT
Pro výrokovou logiku zavedeme proměnnou xp,d = „v poli p je číslo d“, celkem N³ proměnných. Pravidla latinského čtverce se zapíšou jako klauzule „každé pole má aspoň jedno číslo“, „nejvýš jedno“ a totéž pro každou dvojici (řada, číslo). Klec je disjunkce svých n-tic; pro každou n-tici se zavede pomocná proměnná a klauzule, že aspoň jedna n-tice platí. Moderní řešiče SAT takové formule pro mřížky 9 × 9 řeší okamžitě.
11.6Co se ví o složitosti
Pro pevné N je každá úloha konečná a dá se vyřešit za konstantní čas, takže otázky složitosti dávají smysl až pro mřížky N × N s rostoucím N. Základní výsledek se týká latinských čtverců: C. J. Colbourn v roce 1984 dokázal, že rozhodnout, zda jde částečně vyplněný latinský čtverec doplnit, je NP-úplné. K. Haraguchi a H. Ono v roce 2013 dokázali NP-úplnost pro hádanku BlockSum (japonsky KeisanBlock) z téže rodiny „doplň latinský čtverec“ s bloky a cíli a v roce 2015 studovali, jak dobře jdou úlohy typu sudoku, futoshiki a KenKen řešit přibližně (kolik polí jde zaručeně vyplnit). Průvodce nenašel samostatný ověřený důkaz NP-úplnosti právě pro kalkudoku se všemi čtyřmi operacemi, a proto ho netvrdí; podrobnosti v příloze C.
NP-úplnost neznamená, že je hádanka „těžká“ pro člověka nebo pro počítač na malé mřížce. Znamená jen, že pro libovolně velké mřížky neznáme algoritmus, který by každou úlohu vyřešil v polynomiálním čase. Mřížky 4 × 4 až 9 × 9 jsou pro počítač hračka.
11.7Procvičení
- Kalkudoku je úloha s omezeními: řady „všechna různá“, klece tabulkou n-tic.
- Čím dřív algoritmus pozná spor, tím menší strom: naivní → kontrola klecí → propagace s MRV.
- Převod na exact cover (3N² sloupců) a na SAT (N³ proměnných) dovolí použít obecné řešiče.
- Doplňování latinských čtverců je NP-úplné (Colbourn 1984); pro malé mřížky to nic neznamená.
Tvorba úloh a výukamistr a věda
Jak vzniká úloha, která má jediné řešení a dá se vyřešit bez hádání? Generátor průvodce postupuje v pěti krocích: náhodný latinský čtverec, rozdělení na klece, volba operací, test jednoznačnosti s opravami a hodnocení obtížnosti podle technik. Laboratoř je ukazuje jeden po druhém. Kapitola končí tím, jak kalkudoku použít ve škole a jak hrát zdravě.
Výroba úlohy je jako pečení podle receptu pozpátku: nejdřív upečete dort (řešení), pak ho nakrájíte (klece) a na každý kousek napíšete, kolik váží (cíle). Úkol řešitele je složit dort zpátky – a recept musí zaručit, že to jde jen jedním způsobem.
+Teorie: generátor, jednoznačnost, hodnocení obtížnosti, výuka a zdravé hraní
12.1Pět kroků generátoru
- Latinský čtverec. Backtracking s náhodným pořadím čísel vyplní mřížku; pak se zamíchají řádky, sloupce a symboly. Tak vznikne náhodné řešení.
- Klece. Z náhodně vybraných volných polí rostou klece do náhodné velikosti (1 až 4 pole podle zvoleného stylu). Osamocené pole, které mělo být větší, se připojí k sousední kleci.
- Operace. Pro každou klec se podle čísel v řešení zvolí operace a spočítá cíl. U dvou polí se upřednostní dělení a odčítání, u větších klecí sčítání nebo násobení.
- Test jednoznačnosti. Backtracking s propagací hledá nejvýš dvě řešení. Druhé řešení stačí jako důkaz, že úloha je vadná.
- Oprava a hodnocení. Dokud jsou řešení dvě, generátor vybere pole, kde se liší, a buď změní operaci jeho klece, nebo pole z klece oddělí. Hotovou úlohu ohodnotí logický řešitel.
Ve vzorku 6 100 úloh potřeboval generátor průměrně 2,5 až 3,1 opravy na úlohu (podle velikosti mřížky). Bez oprav má jediné řešení jen asi čtvrtina náhodných úloh (kapitola 10).
12.2Hodnocení obtížnosti
Řešitel zkouší techniky v pevném pořadí (tab. 0.2) a vždy použije nejlehčí, která něco přinese. Úroveň úlohy je úroveň nejtěžší použité techniky. Jiný řešitel s jiným pořadím nebo jinými technikami může stejné úloze přidělit jinou úroveň – hodnocení je vlastnost dvojice „úloha + řešitel“.
| Mřížka | úloh | 1 | 2 | 3 | 4 | 5 | mimo |
|---|---|---|---|---|---|---|---|
| 4 × 4 | 1 500 | 781 | 655 | 44 | 5 | 13 | 2 |
| 5 × 5 | 1 500 | 324 | 1 032 | 99 | 18 | 24 | 3 |
| 6 × 6 | 2 500 | 47 | 1 626 | 519 | 79 | 171 | 58 |
| 7 × 7 | 600 | 2 | 351 | 149 | 23 | 50 | 25 |
Obtížnost úlohy se dá odhadnout od oka: hodně jednopolových klecí a součinů znamená lehkou úlohu, velké součtové klece a klece 1− nebo 2÷ těžkou. Minihra výše tenhle odhad trénuje.
12.3Kalkudoku ve škole
Miyamoto hádanku vymyslel pro výuku a její síla je v tom, že spojuje počítání s logikou: žák procvičuje sčítání, násobilku a dělení, a přitom musí zdůvodňovat, proč číslo patří právě sem. Pro výuku se osvědčuje:
- Malé mřížky a jen + a − pro mladší děti (3 × 3 a 4 × 4), násobení a dělení až s násobilkou.
- Mluvit nahlas: „sem patří 3, protože…“ – zdůvodnění je cennější než správná číslice.
- Tvořit vlastní úlohy: vyplnit latinský čtverec 4 × 4, nakreslit klece, spočítat cíle a dát spolužákovi. Kdo vyrobí úlohu se dvěma řešeními, pochopí, proč generátor testuje jednoznačnost.
- Rozložit cíle: všechny sady pro 12× v mřížce 6 × 6 jsou krátká lekce o dělitelích.
12.4Zdravé hraní
Kalkudoku je studijní materiál a hra pro radost. Hrajte s mírou a bez sázek a peněz. Když se zaseknete, dejte si pauzu nebo použijte nápovědu – vyřešená úloha s nápovědou naučí víc než nedokončená. Rekordy a série ve 3D hře jsou jen pro vás a ukládají se v prohlížeči; nemusíte je honit. U dětí je dobré hlídat čas u obrazovky stejně jako u každé jiné hry.
Úloha z neznámého zdroje nemusí mít jediné řešení. Když se zdá, že „nejde bez hádání“, může být chyba v zadání – generátor průvodce i hra jednoznačnost ověřují, ručně opsané úlohy ne.
12.5Procvičení
- Generátor: latinský čtverec → klece → operace → test dvou řešení → oprava a hodnocení.
- Úroveň je nejtěžší technika, kterou řešitel potřebuje; závisí i na řešiteli.
- Ve škole kalkudoku spojuje počty se zdůvodňováním; děti si mohou úlohy vyrábět.
- Hrajte pro radost a s mírou – bez sázek a peněz.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky podle úrovní
| Technika | Úroveň | Kapitola |
|---|---|---|
| Jednopolová klec | 1 | 2 |
| Jediný kandidát | 1 | 4 |
| Skrytý singl | 1 | 4 |
| Klec s jedinou možností | 1 | 2 |
| Poslední pole klece | 2 | 3 |
| Kandidáti klece | 2 | 3 |
| Povinná číslice klece | 3 | 5 |
| Nahá dvojice, skrytá dvojice, nahá trojice | 3 | 7 |
| Pravidlo součtu řádku (i součinu) | 4 | 6 |
| X-wing | 4 | 7 |
| Souhra klecí | 5 | 8 |
| mimo škálu – techniky nad rámec průvodce | – | 11 |
Vzorce na jednom místě
Klece s jedinou možností – tahák
| Mřížka | + | − | × | ÷ |
|---|---|---|---|---|
| 4 × 4 | 3, 4, 6, 7 | 3 | všechny | 3, 4 |
| 5 × 5 | 3, 4, 8, 9 | 4 | všechny | 3, 4, 5 |
| 6 × 6 | 3, 4, 10, 11 | 5 | všechny kromě 6 a 12 | 4, 5, 6 |
Zdroje a předpoklady
Ověřeno 8. 11. 2026. Historické údaje jsou z oficiálních stránek hry a z encyklopedických a odborných zdrojů; matematické výsledky z původních prací nebo databáze OEIS. Čísla, která průvodce sám počítá, jsou spočítaná skriptem nad stejným kódem jako laboratoře.
Historie, pravidla a jméno
- Oficiální stránky hry KenKen (kenkenpuzzle.com, oddíl About): vznik v roce 2004, autor Tetsuya Miyamoto, přístup „The Art of Teaching Without Teaching“, uvedení v USA firmou Nextoy LLC v roce 2008, mřížky 3 × 3 až 9 × 9 a čtyři operace; údaj „KenKen® is a registered trademark of KenKen Puzzle, LLC“. Ověřeno 8. 11. 2026.
- Encyklopedické heslo KenKen (anglická Wikipedie): vznik 2004, ochranná známka KenKen a KenDoku (Nextoy, LLC), knihy nakladatelství Gakken a R. Fuhrer (2007), The Times od března 2008, The New York Times (článek z 8. 2. 2009), názvy Calcudoku a Mathdoku, varianty bez znamének a s jinými operacemi. Ověřeno 8. 11. 2026.
- Encyklopedické heslo Tetsuya Miyamoto (anglická Wikipedie): narozen 1959, rok vzniku hádanky 2003, japonský název 賢くなるパズル (Kashikoku-Naru-Puzzle), metoda „Teaching Without Teaching“. Ověřeno 8. 11. 2026.
- Shortz, W.: A New Puzzle Challenges Math Skills. The New York Times, 8. 2. 2009 (podle některých citací 9. 2. 2009). Ověřeno 8. 11. 2026 podle sekundárních citací.
Latinské čtverce
- OEIS A002860 (počet latinských čtverců řádu n) a A000315 (redukované latinské čtverce); McKay, B. D.; Wanless, I. M. (2005): On the number of Latin squares. Annals of Combinatorics 9(3), 335–344. Ověřeno 8. 11. 2026.
- Euler, L. (1782): Recherches sur une nouvelle espèce de quarrés magiques; Tarry, G. (1900–1901): Le problème des 36 officiers; Bose, R. C.; Shrikhande, S. S.; Parker, E. T. (1960): Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture. Canadian Journal of Mathematics 12, 189–203. Ověřeno 8. 11. 2026.
- van Lint, J. H.; Wilson, R. M.: A Course in Combinatorics, Cambridge University Press (kapitola o permanentech a asymptotice počtu latinských čtverců).
- Fisher, R. A. (1935): The Design of Experiments. Oliver and Boyd (latinský čtverec jako plán polního pokusu).
Algoritmy a složitost
- Colbourn, C. J. (1984): The complexity of completing partial Latin squares. Discrete Applied Mathematics 8(1), 25–30, doi 10.1016/0166-218X(84)90075-1. Ověřeno 8. 11. 2026.
- Haraguchi, K.; Ono, H. (2013): BlockSum is NP-Complete. IEICE Transactions on Information and Systems E96.D(3), 481–488, doi 10.1587/transinf.E96.D.481. Ověřeno 8. 11. 2026 (abstrakt).
- Haraguchi, K.; Ono, H. (2015): How Simple Algorithms Can Solve Latin Square Completion-Type Puzzles Approximately. Journal of Information Processing – aproximace pro sudoku, futoshiki a KenKen. Ověřeno 8. 11. 2026 (abstrakt).
- Knuth, D. E. (2000): Dancing Links. In: Millennial Perspectives in Computer Science, Palgrave, 187–214; arXiv:cs/0011047.
Modelové předpoklady laboratoří
Všechny úlohy, mřížky a statistiky počítá kód průvodce. Jednoznačnost se ověřuje backtrackingem s propagací n-tic klecí a singlů a s heuristikou MRV, který hledá dvě řešení; každá z 54 úloh uložených na stránce má ověřeně jediné řešení. Logický řešitel zkouší techniky v pevném pořadí podle tab. B.1 a vždy použije nejlehčí dostupnou; úroveň úlohy je nejvyšší úroveň použité techniky. Jiný řešitel s jiným pořadím nebo jinými technikami může stejné úloze přidělit jinou úroveň, a „mimo škálu“ proto neznamená „nejtěžší“, jen „nad rámec technik průvodce“. Vzorek 6 100 úloh (1 500 úloh 4 × 4, 1 500 úloh 5 × 5, 2 500 úloh 6 × 6 a 600 úloh 7 × 7) vytvořil generátor z kapitoly 12 s pevnými semínky a čtyřmi styly velikosti klecí; výsledky jsou opakovatelné. Simulace jednoznačnosti v kapitole 10 používá jeden konkrétní náhodný model klecí a operací a její čísla se k jinému generátoru přenášet nedají. Počty latinských čtverců do řádu 6, rozklady cílů, počty uzlů a velikosti převodů jsou spočítané laboratořemi nebo skriptem; počty pro řády 7 až 9 jsou převzaté z OEIS a ověřené jen přepočtem vztahu L(n) = n! (n − 1)! R(n).
Co zůstává nejisté
Rok vzniku hry uvádějí prameny jako 2004 (oficiální stránky) i 2003 (životopisné heslo autora). Vlastníka ochranné známky uvádějí oficiální stránky jako KenKen Puzzle, LLC, encyklopedické heslo jako Nextoy, LLC. Přesný den prvního článku v The New York Times se v citacích liší (8. nebo 9. 2. 2009). Tarryho důkaz pro řád 6 se datuje rokem 1900 i 1901 a práce Bose, Shrikhande a Parkera rokem 1959 i 1960. Samostatný ověřený důkaz NP-úplnosti právě pro kalkudoku se všemi čtyřmi operacemi se nepodařilo najít; přesnou definici hádanky BlockSum z práce Haraguchiho a Ona průvodce ověřil jen z abstraktu, a proto neuvádí, zda výsledek pokrývá kalkudoku přímo.