← Herna
Kalkudoku ve 3D
📖 Průvodce
📖 Průvodce: KenKen a kalkudoku12 kapitol hned pod hrou ↓
KenKen a kalkudoku🧭 Další průvodci a hry
INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

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.

krok řešení–
technika–
vyplněno–
nejvyšší úroveň–
Úvodem

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

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Pravidla, pojmy a historiezákladymříž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í tahyzákladyjednopolové klece, klece s jedinou možností (tabulka pro 4 × 4 a 6 × 6), poslední pole v řádku a sloupci
3 Kandidáti klecezákladyrozklady 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 sloupcezákladylatinský čtverec, jediný kandidát, skrytý singl, poznámky tužkou, kontrola chyb
5 Povinné číslicepokročilípovinná číslice klece, klec v jednom řádku, prvočísla 5 a 7, parita
6 Pravidlo součtu řádku a sloupcepokroč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-wingpokročilínahé a skryté dvojice, nahé trojice, X-wing, jak je hledat
8 Souhra klecí a variantypokročilízkusmé dosazení n-tice, varianta bez znamének, jen sčítání, velké mřížky, řešení na čas
9 Latinské čtvercemistr a vědapoč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ědapočty rozkladů, nejjednoznačnější a nejvíc nejednoznačné cíle, prvočísla, simulace jednoznačnosti
11 Algoritmy a složitostmistr a vědan-tice jako omezení, propagace, backtracking, exact cover a SAT, NP-úplnost doplňování latinských čtverců
12 Tvorba úloh a výukamistr a vědagenerá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.

Tab. 0.2Úrovně obtížnosti v průvodci a ve 3D hře
ÚroveňNejtěžší potřebná technikaKapitola
1Jednopolová klec, Klec s jedinou možností, Jediný kandidát, Skrytý singl2, 4
2Kandidáti klece, Poslední pole klece3
3Povinná číslice klece, Nahá dvojice (a trojice, skrytá dvojice)5, 7
4Pravidlo součtu řádku, X-wing6, 7
5Souhra klecí8
mimo škáluúloha potřebuje techniku nad rámec průvodce8, 11
Statistiky „ve vzorku“ se týkají 6 100 úloh 4 × 4 až 7 × 7, které generátor z kapitoly 12 vyrobil s pevnými semínky (náhodné klece a operace, jediné řešení ověřené prohledáváním) a řešitel průvodce ohodnotil. Všechny úlohy v laboratořích mají jediné řešení.

Čtyři druhy rámečků

Příklad Řešený krok nebo výpočet

Konkrétní situace z mřížky nebo výpočet, který si můžete ověřit v laboratoři.

Z historie

Jak hra vznikla, odkud má jméno, co dokázali matematici a jak se hádanka dostala do novin.

Mistrovská pomůcka

Rychlé pravidlo, zkratka nebo návyk, který používají zkušení řešitelé.

Pozor

Č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.

Hrajte

Kalkudoku ve 3D

Ř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.

Jak to funguje: každá úloha má jediné řešení a jde vyřešit logikou bez hádání – ověřuje to stejný druh řešitele, jaký popisuje kapitola 12. Nápověda trenéra má tři klepnutí: nejdřív ukáže, kde hledat, pak pojmenuje techniku a odkáže na kapitolu, kde se vykládá, a nakonec zapíše číslici. Panel možností klece vypíše sady číslic, které ještě splní cíl vybrané klece (kapitola 3). Poznámky tužkou, tahy zpět i znovu a kontrola chyb jsou samozřejmostí. Za rychlé vyřešení bez nápovědy a bez chyby jsou tři hvězdy. Rekordy, hvězdy a série denních výzev se ukládají jen ve vašem prohlížeči. Po vyřešení vyrostou věže do panoramatu a kamera obletí město.
Část IZáklady
1

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í.

zadánířešení2÷2−7+32−4÷48×2÷2−7+32−4÷48×2134432134121243
Obr. 1.1 Úloha 4 × 4 se sedmi klecemi (vlevo) a její jediné řešení (vpravo). Klec 48× ve tvaru L obsahuje dvě dvojky – smí, protože neleží ve stejném řádku ani sloupci. Jednopolová klec 3 je zadaná číslice.
Příklad krok za krokem
Projděte řešení úlohy z obr. 1.1 tak, jak ji řeší člověk: řešitel v každém kroku použije nejjednodušší techniku, pojmenuje ji a ukáže, odkud závěr plyne (modře) a co zapsal nebo škrtl (oranžově, červeně). V režimu „Vyřešte sami“ klepněte na pole a pak na číslici.
LABORATOŘ
Model: úloha z obr. 1.1 s jediným řešením. Řešitel zkouší techniky v pořadí podle tab. 0.2 a vždy použije nejlehčí, která něco přinese; kapitola u kroku říká, kde se technika vykládá.
Minihra: Kde je chyba?
Laboratoř ukáže vyplněnou mřížku 4 × 4. Někdy je v pořádku, jindy se v řádku a sloupci opakuje číslice nebo klec nedává svůj cíl. Klepněte na pole s chybou, nebo stiskněte „Bez chyby“. Kolo má šest úkolů a za aspoň pět správných získáte 15 XP.
MINIHRA
0 / 6
+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).

Pozor

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.

Součet a součin řádku\[ 1 + 2 + \dots + N = \frac{N(N+1)}{2}, \qquad 1 \cdot 2 \cdots N = N! \]

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:

Příklad Prvních sedm kroků

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

1782Euler: latinské čtverceúloha 36 důstojníků2004T. Miyamoto, Japonskohádanka pro žáky (uvádí se i 2003)2007R. Fuhrer objeví knihynakladatelství Gakken2008The Times, Londýnod března 20082009The New York Timesod února 2009osa není v měřítku; přerušení mezi lety 1782 a 2004
Obr. 1.2 Od latinských čtverců k novinové hádance. Latinské čtverce studoval Euler v 18. století (kapitola 9); kalkudoku je mladé, rozšířilo se během pěti let.
Z historie

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í

1
Mřížka 5 × 5: jaký je součet všech čísel v jednom řádku a v celé mřížce?
Řádek obsahuje 1 až 5: 15. Pět řádků: 75.
2
Smí klec 3− obsahovat tři pole?
Podle pravidel průvodce a novinových úloh ne: rozdíl a podíl se počítají jen ze dvou polí, větší číslo minus (nebo děleno) menší. Klece ze tří a více polí mají sčítání nebo násobení.
3
Klec ze dvou polí vedle sebe v řádku mřížky 4 × 4 má cíl 4×. Které číslice v ní jsou?
Dvě různé číslice (leží v jednom řádku) se součinem 4: jen 1 a 4. Dvojice 2 a 2 by se opakovala v řádku.
4
Klec 4× do tvaru L (tři pole) v mřížce 4 × 4: které sady připadají v úvahu?
{1, 1, 4} a {1, 2, 2}. Opakovaná číslice musí stát v rozích L, které nesdílejí řádek ani sloupec; každá sada má proto jediné pořadí: (1, 4, 1) a (2, 1, 2), kde prostřední číslo je v ohybu. Sada {1, 4} se třemi poli nejde.
5
Proč dobře zadaná úloha nepotřebuje žádné předvyplněné číslice kromě jednopolových klecí?
Informaci nesou cíle klecí. Řešení je jediné, protože kombinace cílů vylučuje všechny ostatní latinské čtverce – pro 4 × 4 jich je 576 (kapitola 9).
Co si odnést
  • 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.
Část IZáklady
2

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.

7+34344 × 4: 7+jen 3 a 43−14144 × 4: 3−jen 1 a 430×56566 × 6: 30×jen 5 a 615+4564564566 × 6: 15+jen 4 a 5 a 6
Obr. 2.1 Čtyři klece s jedinou možností. Malé číslice v polích jsou kandidáti, které cíl připouští. Sada je jistá, pořadí v polích ještě ne – to rozhodnou řádky a sloupce.
Tabulka klecí s jedinou možností
Zvolte velikost mřížky, počet polí klece v jedné řadě a operaci. Laboratoř vypíše všechny cíle, které mohou nastat; oranžově jsou ty se jedinou sadou číslic. Klepnutím na cíl zobrazíte jeho sady a počet pořadí.
LABORATOŘ
Model: klec leží v jednom řádku nebo sloupci, takže číslice v ní jsou různé. Tabulka je spočítaná výčtem všech n-tic čísel 1 až N, které dají cíl zvolenou operací.
Minihra: Najdi první tahy
V každé úloze označte klepnutím všechny klece, u kterých hned víte, které číslice v nich budou: jednopolové klece a klece s jedinou možností. Pak stiskněte „Vyhodnotit“. Kolo má čtyři úlohy; za aspoň tři bez chyby získáte 15 XP.
MINIHRA
0 / 4
+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ů.

Tab. 2.1Cíle klecí ze dvou polí s jedinou sadou číslic
OperaceMřížka 4 × 4Mříž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, 12vš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}
Klec ze dvou polí leží vždy v jedné řadě, takže číslice jsou různé. Tabulku pro jiné velikosti spočítá laboratoř.

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).

Mistrovská pomůcka

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).

Příklad Jedna klec, celý řádek

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ů

  1. Zapište všechny jednopolové klece a škrtněte jejich čísla v řádcích a sloupcích.
  2. Projděte klece s jedinou možností a jejich sady zapište tužkou do polí.
  3. Hledejte řady, kde už z klecí víte skoro vše – poslední volné pole i dvojice, které se „zamknou“.
Pozor

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í

1
Mřížka 6 × 6, klec 11+ ze dvou polí. Co v ní je?
5 a 6 – jediná dvojice různých čísel do 6 se součtem 11.
2
Mřížka 6 × 6, klec 12× ze dvou polí. Je to klec s jedinou možností?
Ne: 12 = 2 · 6 = 3 · 4. Dvě sady, tedy kandidáti 2, 3, 4, 6.
3
Mřížka 4 × 4, klec 2÷. Kolik má sad?
Dvě: {1, 2} a {2, 4}. Dvojka je ale v obou – to je povinná číslice klece (kapitola 5).
4
Mřížka 5 × 5, klec ze dvou polí s rozdílem 4. Co v ní je?
1 a 5: rozdíl N − 1 dá jen nejmenší a největší číslo.
5
Mřížka 6 × 6, klec 15+ ze tří polí v řádku. Co v ní je a co z toho plyne pro zbytek řádku?
{4, 5, 6}. Ve zbylých třech polích řádku musí být 1, 2 a 3.
Co si odnést
  • 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.
Část IZáklady
3

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.

12×23212×1432÷12346123462 · 3 · 2 = 12dvojky nesdílejí řadu1 · 4 · 3 = 12bez opakování6 × 6: 2÷5 nikdy
Obr. 3.1 Klec 12× do tvaru L v mřížce 4 × 4 má sadu {2, 2, 3} (dvojky v rozích, které nesdílejí řadu) i sadu {1, 3, 4}. Vpravo klec 2÷ v mřížce 6 × 6: kandidáti 1, 2, 3, 4, 6 – pětka v ní být nemůže.
Kalkulačka klece
Zvolte velikost mřížky, tvar klece, operaci a cíl. Laboratoř vypíše všechny sady číslic, oranžově ty s opakovanou číslicí, a do polí klece napíše kandidáty. Volba „?“ je klec bez znaménka z kapitoly 8.
LABORATOŘ
Model: výčet všech n-tic čísel 1 až N v polích klece, které dají cíl a v nichž se stejné číslo neobjeví dvakrát v jednom řádku nebo sloupci. Kandidát pole je číslo, které je na jeho místě aspoň v jedné n-tici.
+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.

Kandidáti pole p v kleci K\[ \mathrm{kand}(p) = \{\, t_p : t \in T(K),\ t_q \in \mathrm{kand}(q) \text{ pro všechna pole } q \in K \,\} \]

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.

Tab. 3.1Sady klecí s rozdílem a podílem pro mřížky 4 × 4 a 6 × 6
Cíl4 × 46 × 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}.

Pozor

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í.

Příklad Klec 8+ v mřížce 6 × 6

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.

Poslední pole\[ x = c - \sum_{q \ne p} v_q, \qquad x = \frac{c}{\prod_{q \ne p} v_q}, \qquad x \in \{v \pm c\}, \qquad x \in \{v \cdot c,\ v / c\} \]

3.7Procvičení

1
Mřížka 6 × 6, klec 4− ze dvou polí. Které číslice v ní být nemohou?
3 a 4: sady jsou jen {1, 5} a {2, 6}.
2
Mřížka 6 × 6, klec 3÷. V jednom poli je 6. Co je ve druhém?
2 (6 ÷ 3). Možnost 6 · 3 = 18 je mimo rozsah.
3
Mřížka 6 × 6, klec 6+ do tvaru L (tři pole). Které sady připadají v úvahu?
{1, 2, 3} a {1, 1, 4}; u druhé jsou jedničky v rozích L, které nesdílejí řadu.
4
Mřížka 4 × 4, klec 16× do L. Které sady?
{2, 2, 4} a {1, 4, 4}, opakované číslo v rozích: n-tice (2, 4, 2) a (4, 1, 4).
5
Klec 2− v mřížce 6 × 6, v jednom poli je 3 a v řádku druhého pole už je 1. Co patří do druhého pole?
3 ± 2 dává 1 nebo 5; jednička už v řádku je, takže 5 (Poslední pole klece spolu s řádkem).
Co si odnést
  • 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.
Část IZáklady
4

Řá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.

1−63−48×9+520×10+108×20×9+30×20×2÷12345124514523423412412412415121251514512451231236362414512451232361234561234561234512451231234561234561234566635643
Obr. 4.1 Skrytý singl: ve 3. řádku (modře) může číslice 3 stát už jen v poli ř3s4 (oranžově), i když to pole má ještě jiné kandidáty. Ostatní pole řádku trojku nepřipouštějí – vylučují ji sloupce nebo klece.
Tužka a guma
Vyřešte úlohu sami. Klepněte na pole a pak na číslici; s tlačítkem ✎ píšete poznámky. „Kandidáti z řad“ doplní poznámky jen podle řádků a sloupců, „Kandidáti z klecí“ je zúží i podle n-tic klecí. Nápověda ukáže další logický krok a jeho techniku.
LABORATOŘ
Model: tři úlohy z banky průvodce s ověřeně jediným řešením. Nápověda hledá nejjednodušší logický krok podle tab. 0.2; kontrola porovná zapsané číslice s řešením.
Minihra: Najdi singl
Laboratoř ukáže rozpracovanou úlohu s kandidáty zúženými podle klecí. Klepněte na pole, kam jde hned zapsat číslici – buď má jediného kandidáta, nebo je skrytým singlem v řádku či sloupci. Kolo má pět úkolů; za aspoň čtyři správné získáte 15 XP.
MINIHRA
0 / 5
+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.

1−63−48×9+520×10+108×20×9+30×20×2÷1234512345123451234512345123461234612346123461234614546412345612345612345614512345612341234561234561234561451234561234123456123456123456123456123456123412345612345612345665
Obr. 4.2 Jediný kandidát: v poli ř3s3 (oranžově) zbývá jen 4. Modře jsou vyplněná pole stejného řádku a sloupce, která ostatní čísla vylučují; zbytek obstaraly klece.

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í.

Skrytý singl\[ \big|\{\, p \in R : d \in \mathrm{kand}(p) \,\}\big| = 1 \ \Rightarrow\ \text{to jediné pole je } d \]

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

  1. Kandidáty pište do polí klecí s jedinou možností hned – jejich sada je jistá.
  2. U ostatních klecí pište kandidáty, až když se řady vyčerpají; jinak je mřížka plná čísel, která nic neříkají.
  3. 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.
Mistrovská pomůcka

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á.

Pozor

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í

1
Kolik sousedů má pole v mřížce 6 × 6?
2 · (6 − 1) = 10: pět v řádku a pět ve sloupci.
2
V řádku mřížky 5 × 5 je klec 9+ ze dvou polí a klec 2÷ ze dvou polí. Co je v pátém poli?
Klec 2÷ je {1, 2} nebo {2, 4}; klec 9+ je {4, 5}. Čtyřka nemůže být v řádku dvakrát, takže 2÷ = {1, 2} a páté pole je 3. Kontrola: 4 + 5 + 1 + 2 + 3 = 15.
3
Jaký je rozdíl mezi jediným kandidátem a skrytým singlem?
Jediný kandidát se dívá na jedno pole (zbylo mu jedno číslo), skrytý singl na jednu řadu a jedno číslo (zbylo mu jedno pole).
4
Řádek mřížky 6 × 6 je vyplněný a jeho součet je 21. Je určitě správně?
Ne nutně: 1, 2, 3, 3, 6, 6 má také součet 21. Je potřeba vidět i to, že se čísla neopakují (nebo zkontrolovat i součin 720 – ten má řádek 1, 2, 3, 3, 6, 6 roven 648).
Co si odnést
  • Ř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.
Část IIPokročilí
5

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.

144×120×2×11+143−3−2÷180×24×16+14+1123462346234612122356236236235612345612345623412346235623561234623562356123462356123461234612345623456236123612346123456123456234561234612356123456514
Obr. 5.1 Klec 2× (oranžově) v 1. řádku mřížky 6 × 6 obsahuje jedničku ve všech n-ticích. Jinde v 1. řádku proto jednička být nemůže – červeně škrtnutí kandidáti v polích ř1s1 a ř1s2.
Povinná číslice klece
Rozpracovaná úloha těsně před použitím techniky. Klepnutím na pole vyberete jeho klec; laboratoř vypíše n-tice, které ještě odpovídají kandidátům, povinné číslice a co z nich plyne pro řady. „Použít škrty“ škrtne kandidáty a dokončí jednoduché kroky, které se tím otevřou.
LABORATOŘ
Model: čtyři úlohy 6 × 6 z banky průvodce, každá zastavená těsně před prvním použitím techniky Povinná číslice klece. N-tice jsou pořadí čísel v polích klece, která splní cíl, neporuší řady a souhlasí s kandidáty.
Minihra: Co v kleci musí být?
Laboratoř ukáže klec, velikost mřížky a cíl. Vyberte všechna čísla, která v kleci budou v každém případě (nebo „žádná“), a stiskněte „Vyhodnotit“. Kolo má pět klecí; za aspoň čtyři správné odpovědi získáte 15 XP.
MINIHRA
0 / 5
+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.

Povinná číslice klece\[ \forall t \in T(K)\ \exists p \in K \cap R : t_p = d \ \Rightarrow\ d \notin \mathrm{kand}(q) \text{ pro } q \in R \setminus K \]

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.

Příklad Klec 60× ve sloupci

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.

Prvočíslo p > N/2\[ p \mid c \iff p \in \text{sada klece} \qquad (c = \text{cíl součinové klece},\ N/2 < p \le N) \]

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á.

Mistrovská pomůcka

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ě.

Pozor

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í

1
Mřížka 6 × 6, klec 10× ze dvou polí v řádku. Co se dá škrtnout ve zbytku řádku?
10 = 2 · 5 je jediná sada, takže 2 i 5 jsou povinné a ve zbytku řádku je škrtneme.
2
Mřížka 6 × 6, klec 12× ze tří polí v řádku. Je v ní povinné číslo?
Sady {1, 2, 6} a {1, 3, 4}: povinná je jednička.
3
Mřížka 7 × 7, klec 28× ze dvou polí. Co v ní je?
28 = 4 · 7; sedmička je jediný násobek sedmi, takže sada {4, 7}.
4
Mřížka 6 × 6, klec 9+ ze tří polí v řádku. Je v ní povinné číslo?
Sady {1, 2, 6}, {1, 3, 5} a {2, 3, 4}. Žádné číslo není ve všech třech, takže ne.
5
Mřížka 6 × 6, klec 24× ze tří polí v řádku. Je pětka kandidát?
Ne: 24 není dělitelné pěti. Sady {1, 4, 6} a {2, 3, 4} – a povinná je čtyřka.
Co si odnést
  • 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−.
Část IIPokročilí
6

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.

1−13+7+14+18+332×53×12+120×60×6×123124123561234624564561234512346456123122612656124121245645645623562346234564561261361232456123434531112233445566
Obr. 6.1 Pravidlo součtu sloupce: 6. sloupec (šedě) má součet 21. Leží v něm celé klece 7+ a 12+ (modře), dohromady 19, a jediné další volné pole ř3s6. To tedy musí být 21 − 19 = 2.
Označ oblast
Klepnutím na čísla řádků vlevo nebo sloupců nahoře (případně na pole) vyberte oblast řad. Laboratoř spočítá její součet nebo součin, najde klece celé uvnitř se známým výsledkem (modře) a klece přesahující ven (oranžově) a zjistí, zda z toho jde dopočítat jediné pole.
LABORATOŘ
Model: čtyři úlohy 6 × 6 z banky průvodce zastavené před prvním použitím pravidla. Klec má „známý součet“, když všechny její n-tice, které ještě odpovídají kandidátům, mají stejný součet (u součinu obdobně). Vyčnívající pole se počítají jen tehdy, když je volné jediné.
+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.

Oblast w řad mřížky N × N\[ S_w = w \cdot \frac{N(N+1)}{2}, \qquad P_w = (N!)^w \]
Tab. 6.1Součet a součin jedné řady
Nsoučet řadysoučin řadysoučet mřížky
4102440
51512075
621720126
7285 040196
83640 320288
945362 880405

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.

Vnitřní zbytek\[ x = S_w - \sum_{K \subseteq \text{oblast}} s(K) - \sum_{\text{vyplněná}} v \]

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.

Příklad Vyčnívající pole ve dvou řádcích

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).

Mistrovská pomůcka

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.

Pozor

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í

1
Mřížka 6 × 6, 1. řádek: klec 11+ na třech polích, klec 3− na dvou polích a jedno volné pole, které patří do klece zasahující do 2. řádku. Dá se volné pole dopočítat?
Zatím ne. Klec 3− je {1, 4}, {2, 5} nebo {3, 6} se součty 5, 7 nebo 9, takže pole je 21 − 11 − 5 = 5, 3 nebo 1. Víme ale, že je liché. Až kandidáti vyřadí dvě sady klece 3−, pravidlo pole určí.
2
Mřížka 4 × 4, 4. sloupec: klec 7+ (dvě pole) a klec 2÷ (dvě pole). Co o kleci 2÷ řekne součet sloupce?
Sloupec má součet 10, klec 7+ dává 7, takže 2÷ musí mít součet 3: sada {1, 2}. Se sadou {2, 4} by byl součet sloupce 13.
3
Mřížka 6 × 6, řádky 5 a 6 (součet 42) obsahují celé klece se součty 9, 11, 6, 8 a 5 a jedno další pole. Kolik v něm je?
42 − (9 + 11 + 6 + 8 + 5) = 42 − 39 = 3.
4
Mřížka 6 × 6, jeden sloupec: klece celé uvnitř mají součiny 30 a 12 a zbývá jediné pole. Jaký je jeho obsah podle pravidla součinu?
720 ÷ (30 · 12) = 720 ÷ 360 = 2.
Co si odnést
  • Ř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.
Část IIPokročilí
7

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.

13+3−2÷60×412+1−1−9+4−4÷6+11+6×6÷9+12346123612345615623562362361235615623561362461461234123426261414131324565623231616454524245532424
Obr. 7.1 Nahá dvojice ve 4. sloupci: pole ř3s4 a ř5s4 (modře) mají jen kandidáty {2, 4}. Dvojka a čtyřka se rozdělí mezi ně, a proto je ve zbytku sloupce škrtneme (červeně).
Najdete vzor?
Laboratoř ukáže úlohu těsně před použitím zvolené techniky. Zkuste vzor najít sami, pak klepněte na „Ukázat“ – pole vzoru zmodrají a škrtnutí kandidáti zčervenají. „Použít“ škrty provede, „Jiný příklad“ načte další úlohu.
LABORATOŘ
Model: úlohy 6 × 6 z banky průvodce, zastavené před prvním použitím techniky. Kandidáti jsou zúžení všemi lehčími technikami (úroveň 1 a 2 a povinné číslice).
Minihra: Pojmenuj techniku
Laboratoř ukáže krok řešení: modře pole, ze kterých závěr plyne, červeně škrtnutí kandidáti. Vyberte techniku. Kolo má pět kroků; za aspoň čtyři správné získáte 20 XP.
MINIHRA
0 / 5
+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.

Nahá podmnožina\[ |C| = k,\quad \Big|\bigcup_{p \in C} \mathrm{kand}(p)\Big| = k \ \Rightarrow\ \text{tato čísla škrtneme v } R \setminus C \]

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.

15+3÷14+217+72×10×11+2÷2−4+10×3−4−13561314561456346135613124561245613463461356251245612456134634613525124512346346116633333332462524513333
Obr. 7.2 X-wing na číslici 3: v řádcích 5 a 6 může trojka stát jen ve sloupcích 3 a 4 (modře, oranžové kroužky). Obě trojky z těchto řádků obsadí sloupce 3 a 4, takže ve zbytku sloupců 3 a 4 (řádky 1 až 4) trojku škrtneme – červeně.
Mistrovská pomůcka

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.

Pozor

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í

1
Řádek mřížky 6 × 6 má volná pole s kandidáty {1, 3}, {1, 3}, {1, 3, 5}, {2, 5, 6}. Co škrtneme?
Nahá dvojice {1, 3} v prvních dvou polích: ze třetího pole škrtneme 1 a 3, zbude 5 (Jediný kandidát). Pak ze čtvrtého pole zmizí 5.
2
Pole s kandidáty {2, 4}, {4, 5}, {2, 5} ve sloupci. Je to nahá trojice?
Ano, dohromady jen {2, 4, 5}. Ve zbytku sloupce škrtneme 2, 4 a 5.
3
Ve 3. řádku mohou čísla 1 a 6 stát jen v polích ř3s2 a ř3s5; ř3s2 má kandidáty {1, 4, 6}, ř3s5 {1, 2, 6}. Co plyne?
Skrytá dvojice {1, 6}: z ř3s2 škrtneme 4, z ř3s5 škrtneme 2.
4
Číslo 5 může ve sloupcích 2 a 6 stát jen v řádcích 1 a 4. Kde ho škrtneme?
X-wing po sloupcích: v řádcích 1 a 4 mimo sloupce 2 a 6.
Co si odnést
  • 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.
Část IIPokročilí
8

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.

30×72×20×8+1−4+10+11+24×60×11+120×35232353434353546462323465634235232326412615412651115643
Obr. 8.1 Souhra klecí: klec 11+ (oranžově) má podle kandidátů tři n-tice. N-tice (5, 3, 3) by zablokovala sousední klec 72×, takže vypadne a z pole ř6s3 škrtneme trojku (červeně).
Zkoušení n-tic
Laboratoř vypíše všechny n-tice vybrané klece, které odpovídají kandidátům, a u každé řekne, zda projde, nebo co by zablokovala. Klepnutím na pole vyberete jinou klec. „Použít škrty“ škrtne kandidáty, které nejsou v žádné procházející n-tici, a dokončí kroky, které se tím otevřou.
LABORATOŘ
Model: čtyři úlohy 6 × 6 z banky průvodce zastavené před prvním použitím souhry klecí. N-tice se dosadí, kandidáti v jejích řadách se škrtnou a zkontroluje se, zda každé číslo má v řadě ještě místo a zda jde splnit každá klec, které se dosazení dotklo. Hloubka je jen jeden krok – žádné větvení.
Minihra: Která operace?
Varianta bez znamének: klec ukazuje jen cíl. Z velikosti mřížky, počtu polí a cíle poznejte operaci – v každém kole je jediná možná. Kolo má šest klecí; za aspoň pět správných získáte 15 XP.
MINIHRA
0 / 6
+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.

Souhra klecí\[ F' = \{\, t \in F : \text{dosazení } t \text{ nezablokuje řadu ani sousední klec} \,\}, \qquad \mathrm{kand}(p) \leftarrow \{ t_p : t \in F' \} \]

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í.

244123267
Obr. 8.2 Kalkudoku 4 × 4 bez znamének s ověřeně jediným řešením. Zkuste ho: klec 24 ve třech polích může být jen součin, klec 7 ve dvou polích jen součet 3 + 4. Řešení je v procvičení 8.7.

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.

Mistrovská pomůcka

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.

Pozor

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í

1
Bez znamének, mřížka 5 × 5, klec 20 ve dvou polích. Operace a sada?
Součet je nejvýš 9, rozdíl 4, podíl 5. Takže součin: 4 · 5.
2
Bez znamének, mřížka 6 × 6, klec 5 ve dvou polích. Které sady?
Součet: {1, 4}, {2, 3}; rozdíl: {1, 6}; součin: {1, 5}; podíl: {1, 5}. Čtyři různé sady.
3
Vyřešte úlohu z obr. 8.2.
Řádky shora: 2 3 4 1 / 4 1 2 3 / 1 2 3 4 / 3 4 1 2. Klec 24 = 2 · 3 · 4, klec 12 ve sloupci = 1 · 3 · 4, klec 3 = 1 + 2, klec 2 = 1 · 2 (nebo 2 ÷ 1), klec 6 = 3 + 1 + 2 (i 3 · 1 · 2), klec 7 = 3 + 4.
4
Klec 1− v řádku mřížky 6 × 6 má podle kandidátů n-tice (3, 4) a (4, 3). Ve stejném řádku je klec 8+ ze dvou polí s kandidáty jen 2, 3, 5, 6. Pomůže souhra?
Ano: klec 1− v každém případě spotřebuje 3 i 4. Klec 8+ tedy nemůže být {3, 5} a zbývá {2, 6}. To je zároveň povinná číslice klece – souhra jen ukáže, odkud se vzala.
Co si odnést
  • 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.
Část IIIMistr a věda
9

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.

Počítadlo latinských čtverců
Zvolte řád n. Laboratoř prohledá všechny latinské čtverce (do n = 5) nebo jen redukované (první řádek i sloupec 1, 2, …, n) a ukáže prvních šest. Graf ukazuje počty až do n = 9 na logaritmické ose; řády 7 až 9 jsou převzaté z literatury.
LABORATOŘ

Model: backtracking po polích s bitovými maskami řádků a sloupců; uzel je jedno dosazené číslo. Vztah L(n) = n! · (n − 1)! · R(n) platí pro všechna n a laboratoř ho pro n ≤ 5 ověřuje přímo.
Řecko-latinský čtverec
Dva latinské čtverce přes sebe: latinská písmena a řecká. Když se každá dvojice objeví právě jednou, jsou čtverce ortogonální. Zkuste řády 3 až 7 a zamíchejte řádky, sloupce a symboly – ortogonalita zůstane. Pro řád 6 dvojice neexistuje.
LABORATOŘ
Model: pro prvočíselné n čtverce (i + j) mod n a (2i + j) mod n, pro n = 4 sčítání a násobení v tělese o čtyřech prvcích. Zamíchání permutuje řádky, sloupce a symboly obou čtverců.
+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

Redukované čtverce\[ L(n) = n! \cdot (n-1)! \cdot R(n) \]
Tab. 9.1Počty latinských čtverců (OEIS A002860 a A000315)
nR(n) redukovanýchL(n) všech
111
212
3112
44576
556161 280
69 408812 851 200
716 942 08061 479 419 904 000
8535 281 401 856108 776 032 459 082 956 800
9377 597 570 964 258 8165 524 751 496 156 892 842 531 225 600
Řády 1 až 6 spočítala laboratoř průvodce, řády 7 až 9 jsou z literatury (příloha C); vztah mezi sloupci byl přepočítán v přesné celočíselné aritmetice.

Žá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.

Příklad Kolik kalkudoku „sedí“ na 4 × 4

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.

ABCDBADCCDABDCBAαβγδγδαβδγβαβαδγ
Obr. 9.1 Řecko-latinský čtverec 4 × 4: latinská písmena tvoří latinský čtverec, řecká také a každá z 16 dvojic se objeví jednou. Pro n = 4 ho dává aritmetika tělesa o čtyřech prvcích.
Z historie

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.

DBCEACABDEBEACDECDABADEBCvlhkostrostesklon pozemku5 odrůd, 25 parcelkaždá odrůda jednouv každém řádkui v každém sloupcivliv vlhkosti i sklonuse rozloží rovnoměrněna všechny odrůdy
Obr. 9.2 Polní pokus s pěti odrůdami A až E na 25 parcelách podle latinského čtverce. Každá odrůda je jednou v každém řádku (různá vlhkost) a jednou v každém sloupci (různý sklon).

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í

1
Ověřte L(4) = 576 ze vztahu s redukovanými čtverci.
4! · 3! · R(4) = 24 · 6 · 4 = 576.
2
Vypište všechny čtyři redukované latinské čtverce 4 × 4 (stačí 2. až 4. řádek).
2143 / 3412 / 4321; 2143 / 3421 / 4312; 2341 / 3412 / 4123; 2413 / 3142 / 4321. (Laboratoř je ukáže v režimu redukované, n = 4.)
3
Proč neexistuje řecko-latinský čtverec řádu 2?
Čtverce 2 × 2 jsou jen dva: 12/21 a 21/12. Přes sebe dají dvojice (1, 2), (2, 1), (2, 1), (1, 2) – dvojice (1, 1) a (2, 2) chybějí.
4
Kolik nejvýš navzájem ortogonálních latinských čtverců řádu 5 může existovat?
n − 1 = 4. Pro prvočíslo 5 je to dosažitelné: čtverce (k · i + j) mod 5 pro k = 1, 2, 3, 4.
5
Jaký je log₁₀ L(6) a kolik číslic má L(9)?
L(6) = 812 851 200 ≈ 10^8,91. L(9) ≈ 5,5 · 10^27, má 28 číslic.
Co si odnést
  • Ř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ů.
Část IIIMistr a věda
10

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.

Součet, 3 pole v řadě (6 × 6)01236789101112131415cíl součtuSoučin, 2 pole (6 × 6)01223456810121518202430cíl součinujediná sada číslicvíc sad
Obr. 10.1 Počet sad číslic v mřížce 6 × 6. Vlevo součet tří polí v jedné řadě: symetrické rozložení s maximem tří sad uprostřed (9 až 12) a jedinou sadou na krajích. Vpravo součin dvou polí: 11 ze 13 cílů má jedinou sadu (oranžově).
Počítadlo rozkladů
Zvolte velikost mřížky, počet polí klece v jedné řadě a operaci. Graf ukáže počet sad číslic pro každý možný cíl; oranžově jsou cíle s jedinou sadou. Pod grafem jsou souhrny.
LABORATOŘ
Model: klec leží v jedné řadě, číslice jsou tedy různé. Sady jsou spočítané výčtem; odčítání a dělení jen pro dvě pole.
Simulace jednoznačnosti
Laboratoř vyrobí zvolený počet náhodných úloh – náhodný latinský čtverec, náhodné klece a operace – a u každé zjistí, zda má jediné řešení. Bez oprav, které dělá generátor z kapitoly 12. První běh má pevné semínko, tlačítko „Spustit znovu“ volí nové.
LABORATOŘ
Model: klece rostou z náhodných polí do velikosti 1 až 4 (podíly 8 %, 50 %, 32 % a 10 %), u varianty „klece 2–4 pole“ bez jednopolových. Operace se volí náhodně: u dvou polí z těch, které dávají celé kladné číslo, s vahami ÷ 1,2, − 1, + 0,7 a × 0,7; u větších klecí sčítání nebo násobení. Jednoznačnost testuje backtracking s propagací, který hledá dvě řešení. 95% interval je normální aproximace.
+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.

Rozsah a symetrie součtu\[ \frac{k(k+1)}{2} \le t \le k N - \frac{k(k-1)}{2}, \qquad s_k(t) = s_k\big(k(N+1) - t\big) \]

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.

Tab. 10.1Kolik cílů má jedinou sadu (klec v jedné řadě)
Mřížka, klec+−×÷
4 × 4, 2 pole4 z 51 ze 36 z 62 ze 3
6 × 6, 2 pole4 z 91 z 511 z 133 z 5
6 × 6, 3 pole4 z 10–12 z 16–
9 × 9, 2 pole4 z 151 z 826 z 315 z 8
9 × 9, 3 pole4 z 19–39 z 60–
Spočítáno výčtem v laboratoři. U sčítání mají v tabulce jedinou sadu vždy jen čtyři krajní cíle (dva nejmenší a dva největší).

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:

Tab. 10.2Podíl náhodných úloh s jediným řešením (bez oprav, 1 000 úloh, pevná semínka)
Varianta4 × 45 × 56 × 6
všechny operace28,2 %31,8 %27,5 %
jen sčítání23,1 %25,7 %24,0 %
bez znamének23,3 %27,9 %25,3 %
klece 2–4 pole18,8 %23,3 %21,3 %
95% interval spolehlivosti je při 1 000 úlohách zhruba ± 2,8 procentního bodu. Výsledek závisí na tom, jak velké klece generátor dělá a jak často volí kterou operaci – jiný generátor dá jiná čísla.
Pozor

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í

1
Kolik sad má součet 15 ze tří různých čísel 1 až 9?
Osm: {1, 5, 9}, {1, 6, 8}, {2, 4, 9}, {2, 5, 8}, {2, 6, 7}, {3, 4, 8}, {3, 5, 7}, {4, 5, 6}. Spolu s 14 a 16 je to maximum pro tři pole v 9 × 9.
2
Dokažte, že součet 2N − 1 ze dvou polí má jedinou sadu.
Dvě různá čísla nejvýš N dají nejvýš N + (N − 1) = 2N − 1, a to jen jako {N − 1, N}.
3
Mřížka 9 × 9, klec 18× ze dvou polí. Které sady?
{2, 9} a {3, 6}. Proto je 18 jedním z pěti cílů se dvěma sadami (6, 8, 12, 18, 24).
4
Simulace dala 275 jednoznačných z 1 000. Jaký je přibližný 95% interval?
p = 0,275, směrodatná chyba √(0,275 · 0,725 / 1000) ≈ 0,0141; interval 0,275 ± 1,96 · 0,0141, tedy asi 24,7 % až 30,3 %.
Co si odnést
  • 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.
Část IIIMistr a věda
11

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í.

startř1s1 = 1ř1s1 = 2ř1s1 = 3ř1s2 = 2ř1s2 = 4ř1s2 = 1ř1s2 = 4ř1s2 = 1sporsporspor… řešenínezkoušenoilustrační schéma: při sporu se algoritmus vrátí o úroveň výš a zkusí další číslici
Obr. 11.1 Strom prohledávání: algoritmus zkusí číslo, pokračuje dalším polem, a když narazí na spor, vrátí se o úroveň výš a zkusí jiné číslo (backtracking). Čím dřív spor pozná, tím menší strom.
Řešič 4 × 4 krok za krokem
Vyberte úlohu a metodu a procházejte řešení po krocích nebo ho přehrajte. Logický řešitel pojmenuje techniku každého kroku. U backtrackingu je oranžově zkoušené pole, červeně spor; propagace ukazuje kandidáty po každém uzlu. Dole jsou počty uzlů všech tří prohledávacích metod pro porovnání.
LABORATOŘ
Model: čtyři úlohy 4 × 4 z banky průvodce (úrovně 1, 2, 3 a 5). Backtracking plní pole po řádcích a čísla zkouší od nejmenšího; uzel je jedno zkusmo dosazené číslo. Propagace v každém uzlu opakuje zúžení podle n-tic klecí, jediné kandidáty a skryté singly a pak větví na poli s nejmenším počtem kandidátů (MRV).
+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ů.

04080120160106441úloha 1 (úroveň 1)154481úloha 2 (úroveň 2)24222úloha 3 (úroveň 3)61352úloha 4 (úroveň 5)naivní backtrackings kontrolou klecípropagace + nejméně možností
Obr. 11.2 Počet uzlů prohledávání pro čtyři úlohy 4 × 4 z laboratoře. Kontrola klecí ušetří u úlohy 2 přes dvě třetiny pokusů (154 → 48), u úlohy 3 skoro nic (24 → 22); propagace s heuristikou nejméně možností vyřeší úlohy 1 a 2 bez jediného pokusu a úlohy 3 a 4 po jednom.

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.

Příklad Stejná úloha, tři metody

Ú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.

Velikost matice\[ 3N^2 \text{ sloupců}, \qquad \sum_{K} |T(K)| \text{ řádků} \]

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ě.

Latinská část formule (párové kódování)\[ N^3 \text{ proměnných}, \qquad 3N^2 + 3N^2\binom{N}{2} \text{ klauzulí}; \quad N = 6:\ 216 \text{ proměnných},\ 108 + 1\,620 = 1\,728 \text{ klauzulí} \]

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.

Pozor

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í

1
Kolik sloupců má matice přesného pokrytí pro kalkudoku 9 × 9?
3 · 81 = 243.
2
Proč propagace vyřeší úlohy úrovně 1 a 2 bez větvení?
Obsahuje všechny jejich techniky: zúžení podle n-tic klecí (klece s jedinou možností, kandidáti klece, poslední pole), jediné kandidáty a skryté singly.
3
Kolik proměnných má převod kalkudoku 9 × 9 na SAT bez pomocných proměnných klecí?
9³ = 729.
4
Proč naivní backtracking zkouší víc uzlů než backtracking s kontrolou klecí?
Pozná porušení klece až po vyplnění všech jejích polí, takže zbytečně prochází větve, které už dřív nemohly vést k řešení.
5
Je kalkudoku 6 × 6 „NP-úplná úloha“?
Ne v pravém smyslu: složitost se týká rodiny úloh s rostoucím N. Jedna mřížka pevné velikosti je konečná úloha.
Co si odnést
  • 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á.
Část IIIMistr a věda
12

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.

1. latinský čtverecnáhodné řešení2. klecenáhodné tvary3. operacecíle podle řešení4. testjediné řešení?5. hodnoceníúroveň 1–5víc řešení → oprava klece nebo operace a nový test
Obr. 12.1 Pět kroků generátoru. Když test najde dvě řešení, generátor změní operaci klece nebo oddělí pole, ve kterém se řešení liší, a testuje znovu.
Generátor krok za krokem
Zvolte velikost, styl klecí a operace a stiskněte postupně 1 až 5 (nebo „Vše najednou“). Uvidíte latinský čtverec, klece, cíle, výsledek testu jednoznačnosti – při dvou řešeních červeně pole, kde se liší – a nakonec úroveň obtížnosti.
LABORATOŘ
Model: stejné jádro jako v ostatních laboratořích. Test jednoznačnosti je backtracking s propagací, který hledá nejvýš dvě řešení. Oprava vybere náhodné pole, kde se dvě nalezená řešení liší, a buď změní operaci jeho klece, nebo pole z klece oddělí jako jednopolovou klec. Hodnocení dělá logický řešitel s technikami z tab. 0.2.
Minihra: Odhadni obtížnost
Podívejte se na úlohu a odhadněte, jakou úroveň 1 až 5 jí přidělí řešitel průvodce. Kolo má pět úloh; za aspoň tři přesné odhady získáte 15 XP.
MINIHRA
0 / 5
+Teorie: generátor, jednoznačnost, hodnocení obtížnosti, výuka a zdravé hraní

12.1Pět kroků generátoru

  1. 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í.
  2. 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.
  3. 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í.
  4. Test jednoznačnosti. Backtracking s propagací hledá nejvýš dvě řešení. Druhé řešení stačí jako důkaz, že úloha je vadná.
  5. 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“.

060012001800471162625193794171558mimoúroveň podle nejtěžší potřebné techniky (2 500 náhodných úloh 6 × 6 s jediným řešením)
Obr. 12.2 Rozdělení úrovní ve vzorku 2 500 úloh 6 × 6. Nejčastější je úroveň 2 (65 %), úroveň 3 má 21 %, vyšší úrovně dohromady 12 %. Úroveň 5 je častější než 4: souhra klecí zachrání úlohy, kde pravidlo součtu ani X-wing nepomohou.
Tab. 12.1Úrovně ve vzorku 6 100 úloh podle velikosti mřížky
Mřížkaúloh12345mimo
4 × 41 500781655445132
5 × 51 5003241 0329918243
6 × 62 500471 6265197917158
7 × 76002351149235025
Pevná semínka, čtyři styly velikosti klecí, všechny operace. Úroveň 1 je běžná jen u 4 × 4; větší mřížky skoro vždy potřebují aspoň kandidáty klecí.
Mistrovská pomůcka

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.

Pozor

Ú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í

1
Vyrobte úlohu 3 × 3 z čtverce 123 / 231 / 312 se třemi klecemi po třech polích (po řádcích) a operací +. Má jediné řešení?
Ne: každý řádek má součet 6, takže klece 6+ splní všech 12 latinských čtverců 3 × 3. Klece musí kombinovat různé řady a operace.
2
Proč generátor opravuje úlohu právě v poli, kde se dvě řešení liší?
Jen změna v takovém poli může jedno z řešení vyloučit. Změna jinde by obě řešení zachovala.
3
Úloha potřebuje jednou X-wing a jinak jen singly. Jakou má úroveň?
4 – rozhoduje nejtěžší použitá technika.
4
Ve vzorku 4 × 4 byla úroveň 1 u 781 z 1 500 úloh. Kolik je to procent?
52,1 %.
Co si odnést
  • 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.
PřílohaA

Slovníček

Česká hesla s anglickým termínem. Hledat lze v obou jazycích.

PřílohaB

Vzorce a přehledy

Techniky podle úrovní

Tab. B.1Techniky průvodce a hry v pořadí, v jakém je řešitel zkouší
TechnikaÚroveňKapitola
Jednopolová klec12
Jediný kandidát14
Skrytý singl14
Klec s jedinou možností12
Poslední pole klece23
Kandidáti klece23
Povinná číslice klece35
Nahá dvojice, skrytá dvojice, nahá trojice37
Pravidlo součtu řádku (i součinu)46
X-wing47
Souhra klecí58
mimo škálu – techniky nad rámec průvodce–11

Vzorce na jednom místě

Součet a součin řady (kap. 1, 6)\[ \frac{N(N+1)}{2}, \qquad N!, \qquad \text{oblast } w \text{ řad: } w\frac{N(N+1)}{2},\ (N!)^w \]
Kandidáti klece (kap. 3)\[ \mathrm{kand}(p) = \{\, t_p : t \in T(K),\ t_q \in \mathrm{kand}(q)\ \forall q \in K \,\} \]
Skrytý singl (kap. 4)\[ \big|\{\, p \in R : d \in \mathrm{kand}(p) \,\}\big| = 1 \ \Rightarrow\ \text{to pole je } d \]
Povinná číslice klece (kap. 5)\[ \forall t \in T(K)\ \exists p \in K \cap R : t_p = d \ \Rightarrow\ d \notin \mathrm{kand}(q),\ q \in R \setminus K \]
Vnitřní zbytek (kap. 6)\[ x = S_w - \sum_{K \subseteq \text{oblast}} s(K) - \sum_{\text{vyplněná}} v \]
Nahá podmnožina (kap. 7)\[ |C| = k,\ \Big|\bigcup_{p \in C} \mathrm{kand}(p)\Big| = k \ \Rightarrow\ \text{tato čísla škrtneme v } R \setminus C \]
Rozsah součtu k různých čísel (kap. 10)\[ \frac{k(k+1)}{2} \le t \le kN - \frac{k(k-1)}{2}, \qquad s_k(t) = s_k\big(k(N+1)-t\big) \]
Latinské čtverce (kap. 9)\[ L(n) = n!\,(n-1)!\,R(n), \qquad L(n)^{1/n^2} \sim \frac{n}{e^2} \]
Interval spolehlivosti simulace (kap. 10)\[ \hat p \pm 1{,}96\sqrt{\frac{\hat p(1-\hat p)}{M}} \]
Převody (kap. 11)\[ \text{exact cover: } 3N^2 \text{ sloupců},\ \sum_K |T(K)| \text{ řádků}; \qquad \text{SAT: } N^3 \text{ proměnných} \]

Klece s jedinou možností – tahák

Tab. B.2Klece ze dvou polí s jedinou sadou
Mřížka+−×÷
4 × 43, 4, 6, 73všechny3, 4
5 × 53, 4, 8, 94všechny3, 4, 5
6 × 63, 4, 10, 115všechny kromě 6 a 124, 5, 6
PřílohaC

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.

Interaktivní průvodce KenKen a kalkudoku (listopad 2026). Studijní materiál o hře – hrajte pro radost a s mírou, bez sázek a peněz. KenKen je ochranná známka svého vlastníka; průvodce s ním není spojen a nejmenuje ani nedoporučuje knihy, aplikace či programy.