Kakuro
Součtová křížovka
od první kombinace po algoritmy
Na pozadí řeší počítač kakuro tak jako člověk. V každém kroku hledá nejjednodušší techniku, která ještě něco přinese – od jediné kombinace a průniku běhů po rozdíl součtů a souhru běhů – a pojmenuje ji. Modře jsou pole a běhy, ze kterých závěr plyne, oranžově nápovědy, zapsaná číslice nebo škrtnutí kandidáti. Techniky vysvětlují kapitoly 2 až 8 a stejný řešitel hodnotí obtížnost úloh v kapitole 12.
Jak průvodce používat
Kakuro je křížovka, ve které místo slov stojí čísla. Do bílých polí se píší číslice 1 až 9 tak, aby každá souvislá řada dala součet z nápovědy a žádná číslice se v ní neopakovala. Je to „sudoku s počítáním“: stejná radost z čisté logiky, jen místo skenování řádků a bloků sčítáte a vybíráte kombinace. Průvodce vede od pravidel a prvních jistých polí přes poznámky tužkou a pokročilé techniky až ke kombinatorice součtů, složitosti a k tomu, jak kakuro řeší a vyrábí počítač. Je pro hráče sudoku, kteří chtějí zkusit něco nového, pro rodiče a děti, které si při tom procvičí sčítání, 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 nebo běhu, kde si věc vyzkoušíte klepáním. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, proč technika funguje, ř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 kakuro ve 3D: desku z břidlicových bloků s mosaznými nápovědami, pět obtížností podle technik z tohoto průvodce, panel kombinací u vybraného pole a trenéra, 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 | bílé a černé pole, nápověda, běh, proč se číslice neopakují; od amerických Cross Sums přes japonské kakuro po evropskou vlnu roku 2005 |
| 2 Jediná kombinace | základy | rozsah součtů, „magické bloky“ – součty s jedinou kombinací, souměrnost malých a velkých součtů, jak si je pamatovat |
| 3 Průnik běhů a poslední pole | základy | průnik množin číslic dvou křížících se běhů, dopočet posledního pole, kde úlohu začít |
| 4 Kandidáti tužkou | základy | jak psát poznámky, škrtání po každém zápisu, jediný kandidát, co v dlouhém běhu chybí, chyby z nepozornosti |
| 5 Vyloučení kombinací a povinná číslice | pokročilí | práce se seznamem kombinací, škrtání podle křížících se běhů, číslice, která v běhu být musí, skrytý singl v běhu |
| 6 Meze součtu a nahé dvojice | pokročilí | nejmenší a největší zbytek běhu, úplná kontrola součtu, parita, nahá dvojice a trojice v běhu |
| 7 Rozdíl součtů | pokročilí | proč se součet vodorovných nápověd rovná součtu svislých, oblast s jedním polem navíc, vztah k pravidlu 45 v Killer sudoku |
| 8 Souhra běhů a velké úlohy | pokročilí | zkoušení kombinací čtyř běhů ve čtverci 2 × 2 naráz, postup na velké mřížce, hledání chyb, hranice mezi logikou a hádáním |
| 9 Kombinatorika součtů | mistr a věda | kolik kombinací má každá délka a každý součet, souměrnost d ↦ 10 − d, doplněk do devíti, permutace v běhu |
| 10 Matematika a složitost | mistr a věda | kakuro jako soustava lineárních rovnic s celočíselnými omezeními, hodnost, jednoznačnost, NP-úplnost, vztah ke Killer sudoku |
| 11 Jak kakuro řeší počítač | mistr a věda | bitové masky kombinací, propagace omezení, backtracking s heuristikou nejméně možností, počítání řešení, SAT a celočíselné programování v kostce |
| 12 Tvorba úloh a varianty | mistr a věda | rozvržení, plnění číslicemi, ověření jednoznačnosti, hodnocení obtížnosti podle technik, varianty, zdravé hraní |
Co budete potřebovat
Tužku, gumu a papír se čtverečky – 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 do 45 a umět odečítat; dítě, které zvládne malou násobilku, zvládne i první kakuro. Od kapitoly 9 se hodí kombinační čísla, v kapitolách 10 a 11 trocha lineární algebry 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 hru, poznámky tužkou a Killer sudoku s pravidlem 45 v průvodci Sudoku, sčítání a rozklady čísel pro děti v průvodci Matematika pro 1. stupeň, kombinatoriku, soustavy rovnic a hodnost matice v průvodci Matematika, důkaz sporem a výrokovou logiku (základ převodu na SAT) v průvodci Logika a kritické myšlení a algoritmy, složitost a NP-úplnost obecně v průvodci Informatika.
Značení a předpoklady
Pole se v celém průvodci značí ř3s5 = 3. řádek shora, 5. sloupec zleva; počítá se i horní řádek a levý sloupec, ve kterých stojí jen nápovědy. Běh se zapisuje součet/délka, tedy 7/3 je běh tří polí se součtem 7; šipka → označuje vodorovný běh, ↓ svislý. Laboratoře, hero i 3D hra používají řešitel, který v každém kroku zkouší techniky od nejjednodušší.
| Úroveň | Nejtěžší potřebná technika | Kapitola |
|---|---|---|
| 1 | jediná kombinace, průnik běhů, poslední pole běhu | 2, 3 |
| 2 | jediný kandidát, vyloučení kombinací | 4, 5 |
| 3 | povinná číslice, meze součtu, nahá dvojice v běhu | 5, 6 |
| 4 | rozdíl součtů | 7 |
| 5 | souhra běhů | 8 |
| mimo škálu | úloha potřebuje víc než techniky 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, kdo ji pojmenoval a co o ní dokázali matematici.
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 aplikace či programy; historické údaje a matematické výsledky mají v příloze C zdroj a datum ověření (8. 11. 2026). Úlohy, tabulky kombinací, 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 (kombinace a permutace, počítání podmnožin s daným součtem, souměrnosti, vytvořující funkce v kostce) a soustavy lineárních rovnic na úrovni úvodních vysokoškolských kurzů; informatika – úvod do algoritmů prohledávání (backtracking, heuristika nejméně možností, propagace omezení, bitové masky) a teorie složitosti (NP-úplnost, převod na SAT a celočíselné programování); pravidla – klasické kakuro podle pramenů uvedených v příloze C.
Kakuro 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 kakuro na desce z břidlicových bloků s mosaznými čísly nápověd; bílá pole jsou keramické kostky. Kameru jde natočit a v nastavení přepnout Pohled 3D / 2D shora. Na výběr je Klasické (velikost a obtížnost podle úrovně), Denní výzva (v daný den stejná úloha pro všechny, obtížnost podle dne v týdnu), Pro děti (malé mřížky s jednoduchými součty) a Velké (mřížka až 12 × 12 pro vytrvalé). Obtížnost 1 až 5 odpovídá technikám z průvodce: 1 jediná kombinace z kapitoly 2, průnik běhů a poslední pole z kapitoly 3, 2 navíc jediný kandidát z kapitoly 4 a vyloučení kombinací z kapitoly 5, 3 povinná číslice, meze součtu a nahé dvojice z kapitoly 6, 4 rozdíl součtů z kapitoly 7 a 5 souhra běhů z kapitoly 8. Ovládání v kostce: klepněte na pole a pak na číslo; na klávesnici šipky, 1–9, Delete, N přepne poznámky, T zavolá nápovědu, Z a Y vrací a opakují tahy.
Pravidla, pojmy a historiezáklady
Do každého bílého pole napište jednu číslici 1 až 9. Každá souvislá řada bílých polí – vodorovná i svislá – musí dát součet, který stojí v nápovědě před ní, a žádná číslice se v jedné řadě nesmí opakovat. To je celé pravidlo. Všechno ostatní – kombinace, průniky, meze i rozdíly součtů – jsou jen jeho důsledky. Kapitola zavádí slovník, se kterým pracuje celý průvodce, a ukazuje, jak hra vznikla.
Kakuro je křížovka, kde místo legendy „řeka ve Francii, 5 písmen“ stojí „součet 11, dvě pole“. A stejně jako v křížovce se slova křižují: číslice, kterou napíšete do vodorovného „slova“, je zároveň písmenem svislého. Kdo umí číst obě nápovědy najednou, má vyhráno.
+Teorie: pravidla přesně, čtení nápověd, proč se číslice neopakují, historie
1.1Pravidla přesně
Mřížka se skládá z bílých polí, do kterých se píší číslice, a černých polí. Černé pole je buď prázdné, nebo nese nápovědu – součet, rozdělený úhlopříčkou na dvě části. Běh je souvislá řada bílých polí ve vodorovném nebo svislém směru, ohraničená černými poli nebo okrajem; má 2 až 9 polí. Každé bílé pole leží v právě jednom vodorovném a právě jednom svislém běhu.white cell, black cell, clue, run (entry)
Řešení přiřadí každému bílému poli p číslici xp tak, aby pro každý běh B s nápovědou sB platily dvě podmínky:
Dobrá úloha má právě jedno řešení a dá se k němu dojít úvahou, bez hádání. Všechny úlohy v průvodci i ve 3D hře takové jsou; jak se to ověřuje, ukazuje kapitola 12.
1.2Jak se čte nápověda
Číslo nad úhlopříčkou (vpravo nahoře) patří vodorovnému běhu, který začíná vpravo od černého pole. Číslo pod úhlopříčkou (vlevo dole) patří svislému běhu, který začíná pod ním. Černé pole tedy může nést dvě nápovědy, jednu nebo žádnou. V horním řádku a levém sloupci stojí jen nápovědy, nikdy bílá pole.
Černé pole ř5s3 má nad úhlopříčkou 4: vodorovný běh ř5s4–ř5s5 má součet 4. Dvě různé číslice se součtem 4 jsou jen 1 a 3. Svislý běh 7/3 v 5. sloupci (ř3s5–ř5s5) smí jen 1, 2 a 4. Pole ř5s5 leží v obou: společná je jediná číslice 1. Tak začíná řešení – a právě tuhle úvahu rozebírá kapitola 3.
1.3Proč se číslice v běhu neopakují
Zákaz opakování není ozdoba. Bez něj by běh 4/2 mohl být 1 + 3, 3 + 1 i 2 + 2 a běh 18/2 by šel vyplnit 9 + 9. Hlavně by úlohy přestaly být jednoznačné: úloha z obr. 1.1 má s pravidlem právě jedno řešení, bez něj by měla 566 řešení (spočítáno úplným výčtem). Díky zákazu opakování je obsah běhu množina různých číslic, tzv. kombinace, a na kombinacích stojí celá technika řešení.combination, digit set
Ze stejného důvodu má nápověda běhu dvou polí jen hodnoty 3 až 17: nejmenší je 1 + 2, největší 8 + 9. Obecně pro běh k polí platí
Číslice se nesmí opakovat jen v jednom běhu. Ve stejném řádku mřížky, který černé pole rozdělí na dva běhy, se stejná číslice objevit smí. Kakuro nemá žádné bloky jako sudoku: v řešení z obr. 1.1 stojí jednička třikrát (ř3s2, ř4s4 a ř5s5), pokaždé v jiném vodorovném i jiném svislém běhu.
1.4Z historie
Hádanka vyšla poprvé v USA pod jménem Cross Sums. Will Shortz, redaktor křížovek deníku The New York Times, ji datuje do čísla duben/květen 1950 časopisu Official Crossword Puzzles nakladatelství Dell; autorem byl podle stejného pramene kanadský stavitel Jacob E. Funk (jiný pramen spojuje Funkovo jméno s názvem Cross Sums až s rokem 1966). V polovině 60. let už vycházela v každém hádankovém časopise Dell. Do Japonska ji na počátku 80. let přenesl časopis Nikoli a jeho zakladatel Maki Kaji: podle pramenů nakladatele Conceptis už roku 1980, podle japonské Wikipedie ji Nikoli poprvé otiskl v lednu 1982 a v srpnu 1983 ji uvedl měsíčník NikoList. Japonsky se jmenovala kasan kurosu (加算クロス, „sčítací kříž“), z čehož vzniklo zkrácené kakuro – podle Conceptis pod tímto jménem vyšla roku 1986 první sbírka. Do roku 1992 byla nejoblíbenější hádankou Nikoli, než ji předstihlo sudoku. V Evropě se rozšířila v září 2005 na vlně obliby sudoku: jako první ji začal otiskovat britský deník The Guardian, po něm The Telegraph a Daily Mail.
1.5Kakuro a sudoku
| Sudoku | Kakuro | |
|---|---|---|
| číslice | 1–9 | 1–9 |
| skupina bez opakování | řádek, sloupec, blok (vždy 9 polí) | běh (2 až 9 polí) |
| informace v zadání | vepsané číslice (vodítka) | součty běhů (nápovědy) |
| každé pole patří do | 3 skupin | 2 běhů |
| klíčová dovednost | skenování | kombinace součtů |
| nejbližší příbuzný | Killer sudoku – sudoku s klecemi a součty (průvodce Sudoku, kapitola 9) | |
1.6Procvičení
- Běh = souvislá řada bílých polí; součet z nápovědy, číslice 1–9, v běhu bez opakování.
- Nápověda nad úhlopříčkou patří vodorovnému běhu vpravo, pod úhlopříčkou svislému běhu dole.
- Hra vznikla v USA jako Cross Sums (1950), jméno kakuro jí dalo japonské Nikoli, do Evropy přišla v roce 2005.
Jediná kombinacezáklady
Některé součty jde v daném počtu polí složit jediným způsobem: 3 ve dvou polích je vždy 1 + 2, 17 ve dvou polích vždy 8 + 9, 6 ve třech polích vždy 1 + 2 + 3. Řešitelé jim říkají magické bloky. Kdo je pozná na první pohled, ví hned po přečtení nápovědy, které číslice v běhu stojí – zbývá jen zjistit pořadí. Je to první technika hry a základ všech dalších.
Nápověda je jako zámek a kombinace číslic jako klíče. Většina zámků má klíčů víc – součet 15 ve třech polích otevře osm různých trojic. Magický blok je zámek s jediným klíčem: nemusíte zkoušet, stačí ho poznat.
+Teorie: rozsah součtů, magické bloky, souměrnost, jak si je pamatovat
2.1Rozsah součtů
Běh k polí obsahuje k různých číslic. Nejmenší součet dají nejmenší číslice 1, 2, …, k, největší ty největší 9, 8, …, 10 − k. Mezi tím jde dosáhnout každého součtu: z libovolné kombinace se dá zvýšit součet o 1 výměnou jedné číslice za o jedna větší, dokud nejsou všechny číslice „nahoře“.
| Polí | Nejmenší součet | Největší součet | Možných součtů | Kombinací celkem | Součtů s jedinou kombinací |
|---|---|---|---|---|---|
| 2 | 3 | 17 | 15 | 36 | 4 |
| 3 | 6 | 24 | 19 | 84 | 4 |
| 4 | 10 | 30 | 21 | 126 | 4 |
| 5 | 15 | 35 | 21 | 126 | 4 |
| 6 | 21 | 39 | 19 | 84 | 4 |
| 7 | 28 | 42 | 15 | 36 | 4 |
| 8 | 36 | 44 | 9 | 9 | 9 |
| 9 | 45 | 45 | 1 | 1 | 1 |
2.2Magické bloky
Jediná kombinace je technika: součet a délka běhu připouštějí jedinou množinu číslic, a do všech prázdných polí běhu se proto smějí psát jen číslice této množiny. Platí to i pro rozpracovaný běh – zbývá-li ve dvou prázdných polích doplnit 4 a jednička ani trojka v běhu ještě nejsou, je to zase jen 1 + 3.unique combination, magic block
| Polí | Součet → kombinace |
|---|---|
| 2 | 3 → 1 2 · 4 → 1 3 · 16 → 7 9 · 17 → 8 9 |
| 3 | 6 → 1 2 3 · 7 → 1 2 4 · 23 → 6 8 9 · 24 → 7 8 9 |
| 4 | 10 → 1 2 3 4 · 11 → 1 2 3 5 · 29 → 5 7 8 9 · 30 → 6 7 8 9 |
| 5 | 15 → 1 2 3 4 5 · 16 → 1 2 3 4 6 · 34 → 4 6 7 8 9 · 35 → 5 6 7 8 9 |
| 6 | 21 → 1–6 · 22 → 1–5 a 7 · 38 → 3 5 6 7 8 9 · 39 → 4–9 |
| 7 | 28 → 1–7 · 29 → 1–6 a 8 · 41 → 2 4 5 6 7 8 9 · 42 → 3–9 |
| 8 | 36 až 44: všechny číslice kromě 45 − s |
| 9 | 45 → 1–9 |
2.3Proč leží na krajích
Nejmenší součet k(k + 1)/2 má jedinou kombinaci 1, 2, …, k. Součet o 1 větší vznikne jedině tak, že největší číslici k nahradíte k + 1 – jinak by se dvě číslice srazily. O 2 větší součet už jde dvěma způsoby: největší číslici zvýšit o 2, nebo dvě největší o 1. U běhů 2 až 7 polí proto mají jedinou kombinaci právě dva nejmenší a ze souměrnosti (oddíl 2.4) dva největší součty. Osm polí je výjimka: osm z devíti číslic určuje ta jediná, která chybí, a ta je 45 − s.
2.4Souměrnost malých a velkých součtů
Nahraďte v kombinaci každou číslici d číslicí 10 − d: z 1 + 2 + 4 = 7 se stane 9 + 8 + 6 = 23. Číslice zůstanou různé a součet s běhu k polí přejde na 10k − s. Proto má každý malý součet „zrcadlový“ velký se stejným počtem kombinací a magické bloky chodí v párech.
Druhá souměrnost: místo číslic, které v běhu jsou, se dívejte na ty, které chybějí. Běh 4 polí se součtem 10 (1 2 3 4) má doplněk 5 6 7 8 9 – pět číslic se součtem 35. Proto má 10/4 stejně kombinací jako 35/5.
Pamatujte si jen nejmenší součty: 3 a 4 pro dvě pole, 6 a 7 pro tři, 10 a 11 pro čtyři, 15 a 16 pro pět. Největší dopočítáte zrcadlem 10k − s: pro dvě pole 20 − 3 = 17 a 20 − 4 = 16, pro tři pole 30 − 6 = 24 a 30 − 7 = 23. Kombinace k nim vzniknou stejně: u druhého nejmenšího součtu se poslední číslice zvětší o 1 (1 2 4, 1 2 3 5), u druhého největšího se první zmenší o 1 (6 8 9, 5 7 8 9).
2.5Když kombinací je víc, ale něco je jisté
I bez magického bloku může být jisté, že některá číslice v běhu je, nebo že některé chybějí. Součet 8 ve třech polích má dvě kombinace, 1 2 5 a 1 3 4 – jednička je v obou, a v běhu tedy být musí. Kalkulačka ji ukáže jako „povinnou číslici“. S tím pracuje kapitola 5.
| Běh | Kombinace | Vždy obsahuje |
|---|---|---|
| 8/3 | 1 2 5 · 1 3 4 | 1 |
| 22/3 | 5 8 9 · 6 7 9 | 9 |
| 12/4 | 1 2 3 6 · 1 2 4 5 | 1 a 2 |
| 13/4 | 1 2 3 7 · 1 2 4 6 · 1 3 4 5 | 1 |
| 27/4 | 3 7 8 9 · 4 6 8 9 · 5 6 7 9 | 9 |
| 28/4 | 4 7 8 9 · 5 6 8 9 | 8 a 9 |
Magický blok říká, které číslice v běhu jsou, ne kde. Běh 4/2 je 1 + 3, ale zda je jednička vlevo, nebo vpravo, rozhodne až křížící se běh. Nejčastější chyba začátečníků je napsat 1 a 3 „od oka“ a pak celou úlohu přepisovat.
2.6Procvičení
- Běh k polí má součet od k(k + 1)/2 do k(19 − k)/2.
- Magické bloky: dva nejmenší a dva největší součty každé délky 2–7, každý součet osmi polí a 45 v devíti polích – celkem 34.
- Zrcadlo d ↦ 10 − d mění součet s na 10k − s se stejným počtem kombinací.
Průnik běhů a poslední polezáklady
Každé bílé pole leží ve dvou bězích, vodorovném a svislém, a musí vyhovět oběma. Smí v něm tedy stát jen číslice, které připouští vodorovný běh a zároveň svislý. Když je taková číslice jediná, pole je vyřešené – to je průnik běhů. Druhá technika je ještě prostší: zbývá-li v běhu jediné prázdné pole, dopočítá se odečtením – poslední pole běhu. Těmito dvěma kroky se vyřeší všechny úlohy úrovně 1.
Představte si dvě skupiny přátel, které si domlouvají společný večer. Jedni můžou v pondělí nebo ve středu, druzí ve středu nebo v pátek. Termín, který vyhovuje oběma, je jediný – středa. Průnik běhů funguje stejně: vodorovný běh nabízí své číslice, svislý své, a pole dostane tu, kterou nabízejí oba.
+Teorie: průnik množin, poslední pole, řešený příklad, kde začít
3.1Průnik běhů
Označme M(B) množinu číslic, které se mohou objevit v prázdných polích běhu B: sjednocení všech kombinací, které dávají zbývající součet ve zbývajícím počtu polí a neobsahují číslice, které už v běhu stojí. Pole p leží ve vodorovném běhu H(p) a svislém běhu V(p), takže jeho číslice musí patřit do obou množin.run intersection, cross reference
Průnik funguje nejlépe tam, kde se kříží dva magické bloky s jedinou společnou číslicí. Mezi běhy dvou polí je takových dvojic součtů třináct a vyplatí se je znát nazpaměť:
| Křížení | Pole | Křížení | Pole |
|---|---|---|---|
| 3/2 × 4/2 | 1 | 7/2 × 15/2 | 6 |
| 3/2 × 11/2 | 2 | 8/2 × 16/2 | 7 |
| 4/2 × 6/2 | 1 | 9/2 × 16/2 | 7 |
| 4/2 × 11/2 | 3 | 9/2 × 17/2 | 8 |
| 4/2 × 12/2 | 3 | 14/2 × 16/2 | 9 |
| 5/2 × 13/2 | 4 | 16/2 × 17/2 | 9 |
| 6/2 × 14/2 | 5 |
3.2Poslední pole běhu
Je-li v běhu vyplněno všechno kromě jednoho pole, jeho číslice je zbytek součtu. Je to nejjistější krok v celé hře a po každém zápisu stojí za to podívat se na oba běhy, kterými pole prochází – často se tím „rozsype“ celý řetěz dalších polí.last cell of a run
Dopočtená číslice musí ležet mezi 1 a 9 a nesmí se v běhu opakovat. Vyjde-li 0, 10 nebo číslice, která v běhu už je, nespletla se úloha – spletli jste se dřív. Vraťte se k poslednímu zápisu, který nebyl jistý.
3.3Řešený příklad: první kakuro krok za krokem
| Krok | Pole | Technika | Úvaha |
|---|---|---|---|
| 1 | ř5s5 = 1 | průnik | 4/2 smí {1, 3}, 7/3 smí {1, 2, 4} |
| 2 | ř5s4 = 3 | poslední pole | 4 − 1 |
| 3 | ř3s5 = 2 | průnik | 11/4 smí {1, 2, 3, 5}; ve svislém 7/3 zbývá 6 do dvou polí: {2, 4} |
| 4 | ř4s5 = 4 | poslední pole | 7 − 2 − 1 |
| 5 | ř3s2 = 1 | průnik | v 11/4 zbývá 9 do tří polí: {1, 3, 5}; svislý 7/3 smí {1, 2, 4} |
| 6 | ř3s4 = 5 | průnik | v 11/4 zbývá 8 do dvou polí: {3, 5}; ve svislém 9/3 zbývá 6: {1, 2, 4, 5} |
| 7 | ř3s3 = 3 | poslední pole | 11 − 1 − 5 − 2 |
| 8 | ř4s4 = 1 | poslední pole | 9 − 5 − 3 |
| 9 | ř4s2 = 2 | průnik | v 15/4 zbývá 10 do dvou polí: {2, 3, 7, 8}; ve svislém 7/3 zbývá 6: {2, 4} |
| 10 | ř4s3 = 8 | poslední pole | 15 − 2 − 1 − 4 |
| 11 | ř2s2 = 4 | poslední pole | 7 − 1 − 2 |
| 12 | ř2s3 = 7 | poslední pole | 11 − 4 |
Ve 3. řádku (běh 11/4) už stojí 1 a 2, zbývá 11 − 3 = 8 do dvou polí bez jedničky a dvojky: jen 3 + 5. Svislý běh 9/3 ve 4. sloupci (ř3s4–ř5s4) má z kroku 2 trojku na ř5s4, takže zbývá 6 do dvou polí bez trojky: 2 + 4 nebo 1 + 5. Pole ř3s4 leží v obou: {3, 5} ∩ {1, 2, 4, 5} = {5}.
3.4Kde úlohu začít
Hledejte krátké běhy s krajními součty – magické bloky z kapitoly 2 – a jejich křížení. Nejčastěji leží v rozích a u okrajů mřížky, kde jsou běhy krátké. Ve vzorku 1 347 úloh mělo 997 (74 %) hned na začátku aspoň jedno pole, které jde vyplnit průnikem dvou prázdných běhů; průměrně 1,16 takového pole na úlohu. Ve zbylé čtvrtině je první krok jen poznámka tužkou – kapitola 4.
Po každém zápisu se podívejte na oba běhy, kterými pole prochází: zbylo v některém jediné prázdné pole? Zmenšil se zbývající součet natolik, že z něj vznikl magický blok (třeba 4 do dvou polí)? Zkušení řešitelé tak postupují „po vlně“ od posledního zápisu a celou mřížku znovu prohledávají až ve chvíli, kdy vlna utichne.
3.5Průnik, který jen škrtá
Není-li průnik jediná číslice, i tak zužuje možnosti. Pole na křížení běhů 12/2 a 8/3 smí jen {3, 4, 5} – z šesti číslic běhu 12/2 ({3, 4, 5, 7, 8, 9}) a pěti číslic běhu 8/3 ({1, 2, 3, 4, 5}) zbyly tři. Takové zúžení se zapisuje tužkou do pole a je to první krok k poznámkám v kapitole 4. Řešitel průvodce ho počítá jako průnik běhů úrovně 1, jen místo zápisu číslice škrtá kandidáty.
3.6Procvičení
- Pole smí jen číslice, které připouští jeho vodorovný i svislý běh – průnik množin.
- Poslední prázdné pole běhu se dopočítá: součet minus ostatní číslice.
- Začínejte u krátkých běhů s krajními součty a po každém zápisu kontrolujte oba běhy pole.
Kandidáti tužkou a jediný kandidátzáklady
Ve větších úlohách průnik a poslední pole brzy nestačí: pole má tři, čtyři možnosti a žádná není jistá. Pak pomůže tužka. Do pole se drobně zapíšou číslice, které v něm ještě mohou stát – kandidáti – a po každém zápisu se škrtají. Když v poli zbude jediný kandidát, je vyřešené. Kapitola ukazuje, jak poznámky psát, aby pomáhaly a nemátly, a jak rychle zjistit, které číslice v dlouhém běhu chybějí.
Poznámky jsou jako seznam podezřelých v detektivce. Na začátku je podezřelý skoro každý, ale každé nové alibi někoho vyškrtne. Když na seznamu zbude jediné jméno, je to pachatel – a jeho zatčení dá alibi dalším.
+Teorie: jak psát poznámky, škrtání, jediný kandidát, chybějící číslice, typické chyby
4.1Jak psát poznámky
Kandidáti pole p, značení K(p), jsou číslice, které v poli ještě mohou stát. Píší se drobně a vždy na stejné místo jako na telefonní klávesnici: 1 vlevo nahoře, 5 uprostřed, 9 vpravo dole. Oko pak pozná číslici podle polohy, ne podle tvaru, a prázdné místo hned prozradí, že číslice chybí.candidate, pencil mark
Poznámky začínají průnikem běhů z kapitoly 3: do pole se napíšou jen číslice, které smí jeho vodorovný i svislý běh. Nepište je do všech polí najednou. Vyplatí se tam, kde je kandidátů málo (dva až čtyři), a v místech, kde jste se zasekli.
4.2Škrtání po každém zápisu
Zapsaná číslice d v poli p mění dvě věci v obou bězích pole: číslici d už nesmí žádné jiné pole běhu, a zbývající součet se zmenší o d. Druhá změna je zrádnější – zbývající součet může vytvořit nový magický blok a z poznámek pak zmizí víc číslic než jen d.
Běh 15/3 má osm kombinací a smí všechny číslice 1–9. Zapíšete-li do jednoho pole 9, zbývá 6 do dvou polí bez devítky: 1 + 5 nebo 2 + 4. Kandidáti obou prázdných polí se tím zúží z devíti na {1, 2, 4, 5}. Zapíšete-li místo toho 7, zbývá 8: 1 + 7 je zakázané (sedmička už je), zbývá 2 + 6 a 3 + 5, tedy {2, 3, 5, 6}.
4.3Jediný kandidát
Když v poli po škrtání zbude jediná číslice, patří tam. Sám o sobě je to nejjednodušší závěr, ale dojít k němu vyžaduje poctivé poznámky – proto je jediný kandidát v průvodci technikou úrovně 2. Řešitel ho použil v 1 176 z 1 347 úloh vzorku (87 %).sole candidate, naked single
4.4Co v dlouhém běhu chybí
Běh sedmi polí se součtem 41 má jedinou kombinaci, ale vypsat ji z hlavy je pracné. Snazší je počítat chybějící číslice: všech devět dává 45, chybějící dvě tedy dávají 45 − 41 = 4, a to je jedině 1 + 3. V běhu jsou všechny číslice kromě 1 a 3. U osmi polí chybí jediná číslice 45 − s, u devíti polí žádná.
| Součet | Chybí | Součet | Chybí |
|---|---|---|---|
| 28 | 8 9 | 36 | 1 8 · 2 7 · 3 6 · 4 5 |
| 29 | 7 9 | 37 | 1 7 · 2 6 · 3 5 |
| 30 | 6 9 · 7 8 | 38 | 1 6 · 2 5 · 3 4 |
| 31 | 5 9 · 6 8 | 39 | 1 5 · 2 4 |
| 32 | 4 9 · 5 8 · 6 7 | 40 | 1 4 · 2 3 |
| 33 | 3 9 · 4 8 · 5 7 | 41 | 1 3 |
| 34 | 2 9 · 3 8 · 4 7 · 5 6 | 42 | 1 2 |
| 35 | 1 9 · 2 8 · 3 7 · 4 6 |
4.5Chyby z nepozornosti
Čtyři nejčastější chyby: (1) zapsanou číslici škrtnete jen ve vodorovném běhu a zapomenete na svislý; (2) přečtete nápovědu ze špatné strany úhlopříčky a řešíte svislý běh s vodorovným součtem; (3) počítáte s celou nápovědou místo zbývajícího součtu rozpracovaného běhu; (4) v dopočtu použijete číslici, která už v běhu stojí. Každá z nich vede ke sporu až o mnoho kroků později – a pak je těžké najít, kde se stala.
Kontrolujte dvojí účetnictví: u rozpracovaného běhu si zapište zbývající součet a zbývající počet polí (třeba „8 do 2“). Když se po zápisu nová dvojice čísel nerovná staré minus zapsaná číslice a minus jedno pole, máte chybu hned, ne o deset kroků později.
4.6Procvičení
- Kandidáti pole = průnik číslic, které smí jeho vodorovný a svislý běh; pište je vždy na stejné místo.
- Po každém zápisu přepočítejte oba běhy pole: zakázanou číslici i nový zbývající součet.
- V dlouhém běhu počítejte chybějící číslice: jejich součet je 45 − s.
Vyloučení kombinací a povinná číslicepokročilí
Pokročilý řešitel nemyslí v jednotlivých číslicích, ale v kombinacích. Běh 12/3 má sedm možných kombinací; jakmile víte, že jedno jeho pole smí jen 8 nebo 9, pět z nich odpadne a zbudou 1 3 8 a 1 2 9. Tomu se říká vyloučení kombinací. Ze zbylých kombinací pak často plyne víc: jednička je v obou, takže v běhu být musí – a smí-li ji jediné pole, patří tam.
Kombinace jsou jako kandidátky ve volbách: každá je celá sada jmen. Zjistíte-li, že jeden okrsek nevolil nikoho z kandidátky, celá kandidátka padá – i se jmény, která jste o sobě nic nevěděli. A jméno, které stojí na všech zbylých kandidátkách, zvolené bude určitě.
+Teorie: seznam kombinací, vyloučení kombinací, povinná číslice, skrytý singl v běhu
5.1Seznam kombinací jako stav běhu
Rozpracovaný běh popisují tři údaje: zbývající součet r, počet prázdných polí m a množina U už zapsaných číslic. Možné kombinace jsou množiny m číslic se součtem r, které se s U neprotínají. Zkušení řešitelé si u těžkých běhů nepíšou kandidáty do polí, ale seznam kombinací k nápovědě – a škrtají v něm.combination list
5.2Vyloučení kombinací
Kombinace M může v běhu opravdu stát, jen když jde její číslice rozdělit do prázdných polí tak, aby každá padla na pole, které ji má mezi kandidáty. Dvě rychlé zkoušky odhalí většinu nesmyslů: (a) některé pole nemá žádnou číslici z M; (b) některá číslice z M nemá v běhu žádné pole. Kombinace, které neprojdou, se škrtnou a kandidáti polí se zúží na sjednocení zbylých kombinací.combination elimination
Přesná zkouška je úloha o párování: číslice z M na jedné straně, prázdná pole na druhé, hrana tam, kde je číslice kandidátem pole. Kombinace sedí, právě když existuje párování, které pokryje všechna pole (Hallova věta o párování). U běhů do pěti polí to člověk zvládne zkusmo; řešitel průvodce používá obě rychlé zkoušky a úplnou kontrolu nechává technice meze součtu v kapitole 6.
5.3Kombinace dvou křížících se běhů
Kandidáty, podle kterých se kombinace škrtají, dodává hlavně křížící se běh. Platí to i obráceně: kombinace dvou běhů se musí shodnout ve společném poli. Má-li vodorovný běh jen kombinace, které na křížení dávají 8 nebo 9, a svislý jen kombinace s 5, 6 nebo 9 v tomtéž poli, zbývá ve společném poli jen 9 – a všechny kombinace obou běhů bez devítky odpadnou. Je to průnik běhů z kapitoly 3, jen počítaný z aktuálních seznamů kombinací místo z prázdných běhů.
Běh 20/3 má kandidáty {5, 7, 8}, {3, 5, 7, 8} a {4, 5, 7, 8}. Ze čtyř kombinací 3 8 9, 4 7 9, 5 6 9 a 5 7 8 obsahují první tři devítku, kterou nemá žádné pole – odpadají podle zkoušky (b). Zbude 5 7 8 a všechny tři číslice jsou povinné: trojka a čtyřka se škrtnou z druhého a třetího pole.
5.4Povinná číslice
Číslice, která je ve všech zbylých kombinacích běhu, v běhu stát musí, i když zatím nevíte kde. Součet 8 ve třech polích je 1 2 5 nebo 1 3 4 – jednička je povinná vždy. Povinné číslice z prázdného běhu ukazuje tabulka 2.3; v rozpracovaných bězích jich po vyloučení kombinací přibývá.required digit
5.5Skrytý singl v běhu
Má-li povinná číslice v běhu jediné pole, kde je kandidátem, patří tam – bez ohledu na to, kolik dalších kandidátů to pole má. Je to obdoba skrytého singlu ze sudoku, jen „jednotkou“ není řádek či blok, ale běh a jeho zbylé kombinace.hidden single in a run
U běhů se dvěma nebo třemi kombinacemi si je napište rovnou vedle nápovědy, třeba „15/4: 1347 1257 1248 1239“. Pod seznamem je povinná číslice vidět na první pohled a po každém škrtu v křížícím se běhu stačí projít seznam, ne pole. Na velkých mřížkách tím ušetříte víc času než jakoukoli jinou technikou.
Povinná číslice neříká, že ji jiné pole běhu mít nesmí – říká jen, že v běhu někde je. Škrtat ji v ostatních polích můžete teprve tehdy, když víte, kde stojí. Opačná chyba: zapomenout, že povinnou číslici „spotřebovanou“ v běhu už nesmí mít žádné další jeho pole.
5.6Jak často techniky pomohou
Ve vzorku 1 347 úloh použil řešitel vyloučení kombinací v 1 284 úlohách (95 %) a povinnou číslici v 748 (56 %). Vyloučení kombinací je tak po průniku a posledním poli nejpoužívanější technikou vůbec; v úlohách úrovně 2 a výš bez něj řešení nejde.
5.7Procvičení
- Kombinace odpadá, když některé pole nemá žádnou její číslici nebo některá její číslice nemá pole.
- Číslice ve všech zbylých kombinacích je povinná; vejde-li se jen do jednoho pole, patří tam.
- U těžkých běhů pište seznam kombinací k nápovědě a škrtejte v něm.
Meze součtu a nahé dvojicepokročilí
Když kombinací zbývá hodně, pomůže hrubší, ale rychlá úvaha: kolik nejméně a kolik nejvíc mohou dát ostatní pole běhu? Z toho plyne, jak velké smí být zbylé pole – meze součtu. Obecněji: pokud zbytek běhu se svými kandidáty potřebný součet dát nemůže, pole danou číslici mít nesmí. Druhá technika kapitoly je známá ze sudoku: dvě pole běhu se stejnou dvojicí kandidátů si ji rozdělí mezi sebe – nahá dvojice – a nikdo jiný v běhu ji mít nesmí.
Tři kamarádi skládají 20 korun. Petr má u sebe 3 až 5 korun, Jana 5 až 7. Dohromady dají nejméně 8 a nejvíc 12 – Tomáš tedy musí přidat aspoň 8. Nemusíte vědět, kolik přesně má kdo v kapse; stačí znát krajní možnosti.
+Teorie: meze, úplná kontrola součtu, parita, nahé dvojice a trojice
6.1Meze součtu
V rozpracovaném běhu zbývá součet r do prázdných polí. Vyberte jedno pole p. Ostatní prázdná pole dají se svými kandidáty – bez opakování – nejméně L a nejvýš H. Pak pole p musí ležet mezi r − H a r − L. Kandidáti mimo toto rozpětí se škrtají.sum bounds, min/max analysis
6.2Úplná kontrola součtu
Meze jsou rychlé, ale hrubé: zbytek běhu dá nejméně 6 a nejvýš 12, a přesto nemusí umět dát 9. Přesná úvaha zní: číslice d v poli p obstojí, jen když ostatní prázdná pole umějí se svými kandidáty, bez opakování a bez d dát přesně r − d. Když to nejde, d se z pole škrtá. Ve hře i v průvodci spadá tato úvaha pod stejný název – meze součtu.
Člověk to zkouší pro malé běhy v hlavě; počítač projde všechny podmnožiny číslic, které ostatní pole mohou dát (nejvýš 512 masek, kapitola 11). Úplná kontrola zahrnuje i vyloučení kombinací z kapitoly 5 včetně pasti s párováním.
Běh 20/3 s kandidáty {3, …, 9}, {3, 4, 5} a {5, 6, 7}. První pole: zbytek dá 8 až 12, takže první pole je 8 až 12, tedy 8 nebo 9. Druhé pole: zbytek dá 3 + 5 = 8 až 9 + 7 = 16, tedy druhé pole je 4 až 12 – trojka padá. Třetí pole: zbytek dá 3 + 4 = 7 až 9 + 5 = 14, třetí pole je 6 až 13 – pětka padá. Zbude {8, 9}, {4, 5}, {6, 7} a všechny tři kombinace 9 5 6, 8 5 7 a 9 4 7 jsou dál ve hře.
6.3Parita
Součet je lichý, právě když obsahuje lichý počet lichých čísel. U běhu dvou polí to znamená: lichý součet = jedno pole liché a druhé sudé; sudý součet = obě lichá, nebo obě sudá. V předvolbě C smí druhé pole běhu 10/2 jen sudé číslice, takže i první musí být sudé – 1, 3, 7 a 9 se škrtají, i když meze by je pustily.parity
Mezi číslicemi 1–9 je pět lichých a čtyři sudé. Běh devíti polí má proto vždy pět lichých; běh osmi polí, kterému chybí lichá číslice (lichý rozdíl 45 − s, tedy sudý součet), má čtyři liché a čtyři sudé. Parita je rychlá kontrola i při hledání chyby: lichý součet běhu se samými sudými kandidáty znamená, že někde je omyl.
6.4Nahá dvojice a trojice v běhu
Mají-li dvě pole běhu dohromady jen dva kandidáty – třeba obě {5, 6} –, jedno z nich je 5 a druhé 6. Ostatní pole běhu proto 5 ani 6 mít nesmějí. Stejně tři pole s nejvýš třemi kandidáty dohromady tvoří nahou trojici. Na rozdíl od sudoku se tu navíc mění zbývající součet: dvojice {5, 6} „spotřebuje“ 11 a zbytek běhu musí dát nápovědu minus 11.naked pair, naked triple
Nahá dvojice platí jen uvnitř jednoho běhu. Dvě pole s {5, 6}, která leží každé v jiném běhu, nic neříkají – pětka i šestka se mohou objevit v obou. A dvojice musí být opravdu nahá: pole {5, 6} a pole {5, 6, 8} dvojici netvoří.
6.5Jak často techniky pomohou
Ve vzorku 1 347 úloh použil řešitel meze součtu v 1 002 úlohách (74 %) a nahou dvojici nebo trojici v 275 (20 %). Meze se uplatní hlavně v delších bězích a u krajních součtů. Nahá dvojice je vzácnější, protože v krátkém běhu ji často předběhne poslední pole běhu nebo vyloučení kombinací.
6.6Procvičení
- Pole leží mezi r − H a r − L, kde L a H jsou nejmenší a největší součet zbytku běhu.
- Úplná kontrola: číslice d obstojí, jen když zbytek umí dát přesně r − d.
- Nahá dvojice v běhu vylučuje své číslice ze zbytku běhu a „spotřebuje“ jejich součet.
Rozdíl součtůpokročilí
Každé bílé pole leží v jednom vodorovném a jednom svislém běhu. Sečtete-li tedy všechny vodorovné nápovědy, dostanete totéž co součtem všech svislých – obojí je součet všech číslic v mřížce. Stejná úvaha funguje i na menší oblasti: vyberte několik vodorovných běhů a k nim svislé běhy, které jimi procházejí. Pokrývají-li svislé běhy navíc jediné prázdné pole, jeho hodnota je rozdíl součtů. Je to technika, která nepotřebuje žádné kandidáty – jen sčítání.
Účetní kontroluje tabulku tak, že sečte řádky a pak sloupce: oba součty se musí rovnat. Když jeden sloupec přesahuje tabulku o jednu buňku, rozdíl obou součtů je přesně hodnota té buňky. Kakuro je taková tabulka – řádky jsou vodorovné běhy, sloupce svislé.
+Teorie: rovnost součtů, oblast a rozdíl, odvození na příkladech, pravidlo 45 v Killer sudoku
7.1Součet vodorovných nápověd = součet svislých
Sečtěte číslice všech bílých polí dvakrát: jednou po vodorovných bězích, jednou po svislých. Protože každé pole leží v právě jednom vodorovném a v právě jednom svislém běhu, každá číslice se v obou součtech objeví právě jednou. Oba součty se proto rovnají – a rovnají se součtu všech nápověd daného směru. Je to dvojí počítání, jeden z nejužitečnějších triků kombinatoriky.double counting
V úloze z kapitoly 1: 11 + 11 + 15 + 4 = 41 = 7 + 18 + 9 + 7. Rovnost platí pro každou úlohu a je to zároveň kontrola, že jste nápovědy opsali správně.
7.2Oblast a rozdíl
Vyberte množinu A vodorovných běhů. Každé pole běhů z A leží v nějakém svislém běhu; množina B těchto svislých běhů pokrývá všechna pole z A a případně ještě další pole E, která do A nepatří. Sečtením po obou směrech:sum difference, innies and outies
Je-li v E jediné prázdné pole a ostatní pole E jsou vyplněná, hodnota prázdného pole je rozdíl součtů minus vyplněná pole. Úplně stejně jde začít svislými běhy a přidat vodorovné. Je-li v E prázdných polí víc, dostanete aspoň jejich součet – a s ním můžete pracovat jako s malým „neviditelným během“ (meze, kombinace).
7.3Odvození na příkladech
V pozici z obr. 7.1 má pole ř4s3 kandidáty {4, 5, 6} a svislý běh 15/3 ani vodorovný běh 19/3 ve 4. řádku je dál nezúží – každá ze tří číslic se v nich dá doplnit. Žádný běh sám o sobě pole neurčí. Rozdíl součtů je přesto okamžitý: 18 − 13 = 5. Kontrola v řešení: 6/2 = 2 + 4, 7/2 = 1 + 6, svislý 3/2 = 2 + 1 a 15/3 = 4 + 6 + 5.
V příkladu B vyberte svislé běhy 13/2, 22/3 a 19/3: pokrývají 8 polí se součtem 54. Vodorovné běhy, které jimi procházejí, mají nápovědy 25/4, 24/3 a 10/2 – dohromady 59 na 9 polích. Navíc je jediné pole, ř7s5, a v něm stojí 59 − 54 = 5. Oblasti nemusí být čtverec; stačí, aby se oba směry lišily o jedno prázdné pole.
7.4Vztah k pravidlu 45 v Killer sudoku
V Killer sudoku (průvodce Sudoku, kapitola 9) dává každý řádek, sloupec a blok součet 45. Klece, které leží uvnitř několika jednotek a jen jedním polem z nich vyčnívají, prozradí hodnotu toho pole: součet klecí minus 45 krát počet jednotek. V kakuru roli „45“ hrají nápovědy běhů druhého směru – jinak je úvaha stejná: dvojí sečtení téže oblasti a rozdíl tam, kde se pokrytí liší. Řešitelé Killer sudoku říkají polím uvnitř oblasti „innies“ a vyčnívajícím „outies“.
Oblast hledejte tam, kde je skupina vodorovných běhů ohraničená černými poli a svislé běhy z ní vyčnívají jen málo – typicky blok 2 × 2 nebo 2 × 3 v rohu, ze kterého jeden svislý běh pokračuje o pole dál. Pomáhá i opačný pohled: pole, které „trčí“ z jinak uzavřené oblasti, je kandidát na rozdíl součtů.
Do oblasti patří celé běhy. Vyberete-li vodorovný běh jen napůl, rovnost neplatí. A svislé běhy musí být všechny, které vybranými poli procházejí – chybí-li jeden, je rozdíl o jeho součet špatně.
7.5Jak je technika vzácná
Řešitel průvodce zkouší rozdíl součtů až po všech technikách úrovně 1 až 3. Ve vzorku 1 347 úloh ho potřeboval jen ve 43 (3,2 %); úloh, pro které je to nejtěžší technika (úroveň 4), bylo 29. Člověk ho ale používá častěji – často je rychlejší než dlouhá práce s kandidáty, i když by úloha šla vyřešit i bez něj.
7.6Procvičení
- Součet všech vodorovných nápověd se rovná součtu všech svislých – dvojí počítání.
- Vybrané běhy jednoho směru a běhy druhého směru, které jimi procházejí: rozdíl jejich součtů je součet polí navíc.
- Je to obdoba pravidla 45 z Killer sudoku; hledejte uzavřené bloky, ze kterých jeden běh vyčnívá.
Souhra běhů a velké úlohypokročilí
Nejtěžší technika hry se dívá na čtyři běhy najednou. Dva vodorovné a dva svislé běhy, které se kříží ve čtverci 2 × 2 bílých polí, se navzájem omezují víc, než prozradí kterýkoli z nich zvlášť. Souhra běhů vyzkouší všechna dosazení kandidátů do čtyř polí čtverce a ponechá jen ta, se kterými jdou všechny čtyři běhy poskládat. Co neprojde, se škrtá. Kapitola pak ukazuje, jak postupovat na velké mřížce, jak hledat chyby a kde končí logika a začíná hádání.
Čtyři lidé si sedají ke čtvercovému stolu. Každá dvojice sousedů u jedné hrany má své přání – tihle chtějí sedět vedle sebe, tamti ne. Každé přání zvlášť připouští mnoho zasedacích pořádků, ale všem čtyřem hranám najednou vyhoví jen jeden. Souhra běhů hledá právě takové zasedací pořádky pro čtyři čísla.
+Teorie: čtverec 2 × 2, řešený příklad, velká mřížka, hledání chyb, hranice hádání
8.1Čtverec 2 × 2 a čtyři běhy
Čtverec 2 × 2 bílých polí leží vždy na křížení dvou vodorovných běhů (horní a dolní řádek čtverce) a dvou svislých (levý a pravý sloupec); každý vodorovný kříží oba svislé. Jednotlivé techniky z kapitol 3 až 6 se dívají na jeden běh nebo jedno křížení. Souhra běhů zkouší kombinace všech čtyř běhů naráz:run interplay, joint combination check
- vypište všechna dosazení kandidátů do čtyř polí čtverce, ve kterých se v žádném běhu neopakuje číslice;
- u každého dosazení ověřte všechny čtyři běhy: dají ostatní pole běhu se svými kandidáty přesně zbývající součet?
- dosazení, které neprojde aspoň jedním během, odpadá; v každém poli čtverce zůstanou jen číslice z dosazení, která prošla.
Jednodušší úvahu „kombinace dvou křížících se běhů se musí shodnout ve společném poli“ už znáte z kapitoly 5 – patří do průniku běhů a vyloučení kombinací. Souhra běhů jde dál: dvojice běhů se v jednom poli shodnout mohou, a přesto nejde všechny čtyři běhy poskládat zároveň.
8.2Řešený příklad
| ř2s4 | ř2s5 | ř3s4 | ř3s5 | Výsledek |
|---|---|---|---|---|
| 1 | 3 | 2 | 7 | ✗ → 17/3: na ř3s3 by muselo být 17 − 2 − 7 = 8, smí jen 6, 7, 9 |
| 1 | 3 | 2 | 9 | ✗ ↓ 10/2: 3 + 9 = 12, ne 10 |
| 3 | 1 | 1 | 7 | ✗ ↓ 10/2: 1 + 7 = 8, ne 10 |
| 3 | 1 | 1 | 9 | ✓ projde: 3 + 1 = 4, 1 + 9 = 10, ř4s4 = 6 − 3 − 1 = 2, ř3s3 = 17 − 1 − 9 = 7 |
| 3 | 1 | 2 | 7 | ✗ → 17/3: na ř3s3 by muselo být 8 |
| 3 | 1 | 2 | 9 | ✗ ↓ 6/3: na ř4s4 by muselo být 6 − 3 − 2 = 1, smí jen 2, 3 |
Žádný ze čtyř běhů by sám nic neškrtl: běh 4/2 připouští 1 + 3 v obou pořadích, běh 10/2 dvojice 1 + 9 i 3 + 7, a tak dál. Teprve dohromady zbude jediná možnost: ř2s4 = 3, ř2s5 = 1, ř3s4 = 1, ř3s5 = 9. V příkladu B je dosazení 42 a projde opět jediné (2, 8, 3, 9); 28 z nich vyloučí vodorovný běh 10/2, 7 běh 16/3, 4 svislý 5/2 a 2 svislý 21/3.
8.3Proč to není hádání
Souhra běhů zkouší, ale konečně a předem ohraničeně: čtyři pole, nejvýš 94 = 6 561 dosazení (v praxi desítky), a každé se ověří jen na čtyřech bězích. Výsledek – co neprojde, neplatí – je pravdivý bez ohledu na zbytek mřížky. Je to totéž, co dělá řešitel s tužkou, když si na okraj vypíše tabulku možností. Hádání je něco jiného: zvolit číslici a řešit s ní dál celou mřížku, dokud nenarazíte na spor (oddíl 8.6).
8.4Postup na velké mřížce
- Magické bloky a jejich křížení – projděte všechny krátké běhy s krajními součty (kapitoly 2 a 3).
- Dlouhé běhy – spočítejte chybějící číslice 45 − s (kapitola 4).
- Poznámky jen tam, kde jsou krátké – do polí se dvěma až čtyřmi kandidáty; u dlouhých běhů seznam kombinací k nápovědě.
- Vlna od posledního zápisu – po každém zápisu oba běhy pole: poslední pole, nový magický blok, škrty v kombinacích.
- Zaseknutí – povinné číslice a meze (kapitoly 5 a 6), pak rozdíl součtů na uzavřených oblastech (kapitola 7) a nakonec souhra běhů ve čtvercích, kde se kříží běhy s málo kombinacemi.
Ve vzorku mají úlohy 9 × 9 průměrně 36 bílých polí a řešitel je projde za 68 kroků, úlohy 10 × 10 mají 42 polí a 84 kroků. Souhru běhů potřebovalo 382 z 1 347 úloh (28 %).
8.5Hledání chyb
Chyba se v kakuru projeví jedním ze tří příznaků: v běhu se opakuje číslice, zbývající součet nejde doplnit (je záporný, nebo ho prázdná pole nemohou dát), nebo poli nezbyl žádný kandidát. Řešitel průvodce kontroluje všechny tři před každým krokem. Člověku pomůže kontrola parity (kapitola 6), rovnost součtů obou směrů (kapitola 7) a „dvojí účetnictví“ zbývajícího součtu (kapitola 4).
Když najdete spor, nemažte poslední zápis automaticky. Chyba bývá o několik kroků dřív – typicky škrt, který jste provedli jen v jednom ze dvou běhů pole. Vraťte se k poslednímu zápisu, u kterého si nejste jistí důvodem, ne k poslednímu zápisu vůbec.
8.6Kdy se ze zkoušky stává hádání
Zkouška je logická, dokud je ohraničená: víte předem, kolik možností prověříte, a každou prověříte celou. Jakmile zvolíte číslici a řešíte s ní dál celou mřížku v naději, že narazíte na spor, je to hádání (v informatice backtracking, kapitola 11). Dobrá úloha ho nepotřebuje: autor ji ověřil řešitelem, který zná jen logické techniky. Ve vzorku generátoru zůstalo 271 z 1 347 úloh (20 %) „mimo škálu“ – logické techniky průvodce na ně nestačily, a do hry proto nejdou.
Souhru běhů hledejte ve čtvercích 2 × 2, kde všechny čtyři běhy mají málo kombinací – typicky krátké běhy s krajními součty u okraje nebo dvojice polí se dvěma kandidáty. Čím méně dosazení, tím rychlejší tabulka; víc než asi 20 řádků na papíře nemá smysl psát.
8.7Procvičení
- Souhra běhů: všechna dosazení do čtverce 2 × 2 proti čtyřem běhům najednou; co neprojde, se škrtá.
- Ohraničená zkouška je logika, neohraničené zkoušení celé mřížky je hádání.
- Na velké mřížce: magické bloky, chybějící číslice, krátké poznámky, vlna od posledního zápisu, teprve pak těžké techniky.
Kombinatorika součtůmistr a věda
Kolik kombinací má každá dvojice délka–součet? Odpověď je pěkný kus kombinatoriky: počty tvoří souměrná „zvonová“ rozdělení, řádky pro k a 9 − k polí jsou stejné a celkem existuje 511 neprázdných množin číslic. Kapitola spočítá celou tabulku, vysvětlí obě souměrnosti a ukáže, kolik pořadí připadá na jednu kombinaci – a proč na pořadí v kakuru tolik záleží.
Hoďte devíti mincemi označenými 1 až 9 a sečtěte čísla mincí, které padly orlem. Každý z 512 výsledků je jedna množina číslic; součty uprostřed padají nejčastěji, krajní nejvzácněji. Tabulka kombinací kakura je přesně tohle rozdělení, jen rozložené podle toho, kolik mincí padlo.
+Teorie: tabulka kombinací, vytvořující funkce, souměrnosti, nejčetnější součty, permutace
9.1Počet kombinací
Označme c(k, s) počet k-prvkových podmnožin množiny {1, …, 9} se součtem s. Bez ohledu na součet je k-prvkových podmnožin \( \binom{9}{k} \), takže součet řádku tabulky je kombinační číslo: 36, 84, 126, 126, 84, 36, 9 a 1 pro k = 2 až 9. Všech neprázdných podmnožin je 29 − 1 = 511.number of combinations, binomial coefficient
| k | Součty | Počty kombinací | Celkem |
|---|---|---|---|
| 2 | 3–17 | 1 1 2 2 3 3 4 4 4 3 3 2 2 1 1 | 36 |
| 3 | 6–24 | 1 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 1 | 84 |
| 4 | 10–30 | 1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1 | 126 |
| 5 | 15–35 | 1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1 | 126 |
| 6 | 21–39 | 1 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 1 | 84 |
| 7 | 28–42 | 1 1 2 2 3 3 4 4 4 3 3 2 2 1 1 | 36 |
| 8 | 36–44 | 1 1 1 1 1 1 1 1 1 | 9 |
| 9 | 45 | 1 | 1 |
9.2Vytvořující funkce
Celou tabulku zakóduje jediný součin. Každá číslice d do množiny buď nepatří (člen 1), nebo patří a přidá jeden prvek a součet d (člen y xd). Roznásobením vznikne součet přes všech 512 podmnožin a koeficient u yk xs je právě c(k, s).generating function
Dosadíte-li x = 1, dostanete binomickou větu (1 + y)9 a součty řádků \( \binom{9}{k} \). Počítač tabulku ale nepočítá roznásobením – projde 512 bitových masek a každou zařadí podle počtu jedniček a součtu (kapitola 11).
9.3Dvě souměrnosti
Zrcadlo číslic. Zobrazení d ↦ 10 − d je vzájemně jednoznačné na {1, …, 9} a mění součet k-prvkové množiny ze s na 10k − s. Doplněk. Množina M a její doplněk do {1, …, 9} mají dohromady všech devět číslic a součet 45. Obě zobrazení jsou bijekce, a proto:
První rovnost dělá z každého řádku tabulky palindrom se středem 5k. Druhá říká, že řádky k a 9 − k jsou stejné (po složení obou zobrazení: c(k, s) = c(9 − k, s − 5(2k − 9)), tedy jen posunuté o 45 − 10k).
9.4Nejčetnější součty
| k | Střed 5k | Nejčetnější součty | Kombinací |
|---|---|---|---|
| 2 | 10 | 9, 10, 11 | 4 |
| 3 | 15 | 14, 15, 16 | 8 |
| 4 | 20 | 20 | 12 |
| 5 | 25 | 25 | 12 |
| 6 | 30 | 29, 30, 31 | 8 |
| 7 | 35 | 34, 35, 36 | 4 |
Nejvíc kombinací v celé hře – dvanáct – mají běhy 20/4 a 25/5. Pro řešitele jsou to nejméně informativní nápovědy: samy o sobě skoro nic nevyloučí a pomohou až v kombinaci s křížícími se běhy.
9.5Permutace v běhu
Kombinace říká, které číslice v běhu jsou; pořadí je další volba. Každou k-prvkovou množinu jde do k polí rozmístit k! způsoby, takže samostatný běh má c(k, s) · k! vyplnění. Běh 20/4 tedy 12 · 24 = 288, běh 4/2 jen 1 · 2 = 2. Pořadí v kakuru určují výhradně křížící se běhy – právě proto stojí celá technika na průnicích.
Z tab. 9.1: v každém řádku pro k = 2 až 7 jsou jedničky přesně dvě na začátku a dvě na konci (4 · 6 = 24), u osmi polí je jedniček devět a u devíti jedna. Celkem 24 + 9 + 1 = 34 magických bloků – stejné číslo jako v kapitole 2, tentokrát přečtené z tabulky.
9.6Procvičení
- Řádek k tabulky kombinací má součet \( \binom{9}{k} \); všech neprázdných množin číslic je 511.
- Souměrnosti: c(k, s) = c(k, 10k − s) a c(k, s) = c(9 − k, 45 − s).
- Nejvíc kombinací (12) mají 20/4 a 25/5; samostatný běh má c(k, s) · k! vyplnění.
Matematika a složitostmistr a věda
Kakuro je soustava lineárních rovnic: neznámé jsou bílá pole, rovnice jsou běhy. Lineární algebra ale sama nestačí – rovnic je vždy méně, než by bylo potřeba, a jedna z nich je navíc „zbytečná“. Řešení určí teprve celočíselnost (číslice 1–9) a zákaz opakování. Právě tahle kombinace dělá z kakura těžkou úlohu i pro počítač: obecná verze je NP-úplná. Kapitola ukazuje proč a co z toho plyne pro tvůrce úloh.
Z rovnic a + b = 10 a c + d = 10 nezjistíte nic určitého. Přidejte „všechna čísla jsou různé číslice od 1 do 9 a a je nejmenší“ – a najednou je možností jen pár. Kakuro je celé postavené na tom, že rovnice samy nestačí a rozhodují pravidla navíc.
+Teorie: soustava rovnic, hodnost, celočíselnost, jednoznačnost, NP-úplnost, Killer sudoku
10.1Kakuro jako soustava lineárních rovnic
Očíslujme bílá pole 1 až n a běhy 1 až m. Matice A typu m × n má jedničku v řádku běhu a sloupci pole, které do běhu patří, jinde nulu. Pravidlo součtů je soustava Ax = s, kde s je vektor nápověd. Každý sloupec matice má přesně dvě jedničky – jednu ve vodorovném a jednu ve svislém běhu.system of linear equations, incidence matrix
10.2Hodnost: proč rovnice nestačí
Sečtete-li všechny řádky vodorovných běhů, dostanete vektor samých jedniček – stejně jako součtem řádků svislých běhů (kapitola 7). Mezi rovnicemi je tedy vždy aspoň jedna závislost a hodnost je nejvýš m − 1. Přesněji: matici lze číst jako incidenční matici bipartitního grafu, jehož vrcholy jsou běhy a hrany pole (každé pole spojuje svůj vodorovný a svislý běh). Pro souvislý bipartitní graf je hodnost incidenční matice přesně počet vrcholů minus 1.rank, bipartite graph
Úloha z laboratoře má 12 polí a 8 běhů: hodnost 7 a pět volných parametrů. Lineární algebra sama tedy neurčí ani jedno pole. Ověřeno pro všech 1 347 úloh vzorku: hodnost vyšla vždy m − 1 a počet volných parametrů od 3 do 25.
10.3Celočíselnost a různost
Pětirozměrný prostor řešení soustavy zúží podmínka xp ∈ {1, …, 9} na konečně mnoho bodů: úloha z laboratoře by bez zákazu opakování měla 27 celočíselných řešení s číslicemi 1–9 (úloha z kapitoly 1 dokonce 566). Zákaz opakování vybere jediné. Teprve tato kombinace – lineární rovnice, celá čísla v mezích, nerovnosti mezi poli běhu – dává kakuru jeho obtížnost.
10.4Jednoznačnost a malé změny
Změníte-li jedinou nápovědu, porušíte rovnost součtů obou směrů a úloha nemá řešení vůbec. Změníte-li o stejné číslo jednu vodorovnou a jednu svislou nápovědu, rovnost zůstane. Pro úlohu z laboratoře: ze všech 32 takových změn o ±1 (4 vodorovné × 4 svislé běhy × 2 znaménka) dá 15 úlohu bez řešení, 10 úlohu s více řešeními a jen 7 opět úlohu s jediným řešením. Jednoznačnost je křehká vlastnost – a tvůrce ji musí ověřovat počítačem (kapitola 12).
Vyberte vodorovný běh 23/3 a zvyšte ho na 24: úloha nemá řešení – 24 ve třech polích je jen 7 8 9 a součty obou směrů se rozešly o 1. Zvyšte pak některý svislý běh o 1 a sledujte, zda vznikne jediné řešení, víc řešení, nebo zase žádné.
10.5NP-úplnost
Úloha patří do třídy NP, když jde navržené řešení rychle (v polynomiálním čase) ověřit – u kakura stačí sečíst běhy a zkontrolovat opakování. Je NP-úplná, když je navíc aspoň tak těžká jako každá úloha z NP: libovolnou z nich jde rychle převést na ni. Pro NP-úplné úlohy není znám algoritmus, který by je v nejhorším případě řešil v polynomiálním čase; pokud by existoval, platilo by P = NP.NP-completeness, polynomial reduction
NP-úplnost kakura (pod jménem CROSS SUM) dokázal Takahiro Seta v bakalářské práci na katedře informatiky Přírodovědecké fakulty Tokijské univerzity, odevzdané 5. února 2002 (vedoucí Hiroshi Imai). Na zobecněné kakuro (mřížka libovolné velikosti) převedl v polynomiálním čase známé NP-úplné úlohy: rozklad orientovaného grafu na kružnice (PARTITION INTO CIRCUITS) a varianty splnitelnosti 3SAT a ONE-IN-THREE 3SAT. Ukázal také, že NP-úplná je i otázka, zda úloha má jiné řešení než zadané (another solution problem, ASP) – přesně to, co musí ověřovat tvůrce úloh. Navazující článek T. Yato a T. Sety (IEICE Transactions on Fundamentals, 2003) dokazuje ASP-úplnost pro Slitherlink, Cross Sum a Number Place (sudoku). Nový důkaz NP-úplnosti kakura publikovali O. Ruepp a M. Holzer na konferenci FUN 2010.
Seta zkoumal i omezené varianty: kakuro zůstává NP-úplné, i když žádný běh nemá víc než 6 polí, a naopak s běhy nejvýš dvou polí jde vyřešit v lineárním čase. Pro hry s menším počtem číslic (3 až 6) nechala jeho práce otázku otevřenou.
NP-úplnost neříká, že je těžká každá úloha – úloha 9 × 9 z novin trvá počítači milisekundy. Mluví o nejhorším případě pro rostoucí velikost mřížky. Neříká ani, že úlohu nevyřeší člověk: dobrá úloha je navržená tak, aby šla logickými kroky.
10.6Vztah ke Killer sudoku
Killer sudoku sdílí s kakurem jádro: klec je skupina polí se součtem a číslice se v ní neopakují – tedy běh libovolného tvaru. Tabulky kombinací z kapitol 2 a 9 platí pro klece beze změny. Navíc ale platí pravidla sudoku (každý řádek, sloupec a blok obsahuje 1–9), takže jsou k dispozici součty 45 a pravidlo 45 – obdoba rozdílu součtů z kapitoly 7. V kakuru žádné „jednotky s 45“ nejsou, jen běhy; o to víc záleží na průnicích a na rovnosti součtů obou směrů.
10.7Procvičení
- Kakuro = soustava A x = s s celočíselnými omezeními a zákazem opakování; hodnost je počet běhů minus 1.
- Změna jediné nápovědy úlohu vždy pokazí; jednoznačnost je křehká a musí se ověřovat.
- Zobecněné kakuro je NP-úplné (Seta 2002), stejně jako otázka, zda má úloha jiné řešení.
Jak kakuro řeší počítačmistr a věda
Počítač řeší kakuro stejnými myšlenkami jako člověk, jen rychleji a bez únavy. Kombinace ukládá jako bitové masky, takže průnik běhů je jediná instrukce. Po každém zápisu propaguje omezení do obou běhů pole. A když logika nestačí, zkouší: zvolí pole, dosadí číslici a pokračuje; při sporu se vrátí – backtracking. Rozhoduje pořadí: pole s nejméně možnostmi napřed. Laboratoř ukáže, že kombinace a správné pořadí ušetří statisíce kroků.
Hledáte klíče v domě. Naivní postup prohledá místnosti podle čísel dveří. Chytrý začne tam, kde jsou jen dvě možná místa – v předsíni je buď v kapse kabátu, nebo na poličce. Backtracking s heuristikou nejméně možností dělá přesně tohle: kde je volba nejužší, tam se rozhoduje nejdřív.
+Teorie: bitové masky, propagace omezení, backtracking, MRV, počítání řešení, SAT a celočíselné programování
11.1Bitové masky kombinací
Množinu číslic zapíšeme jako devítibitové číslo: bit d − 1 je 1, právě když číslice d do množiny patří. Množina {1, 2, 4} je binárně 000001011, tedy 11. Všech masek je 29 = 512. Počet číslic je počet jedniček (popcount), sjednocení je bitové OR, průnik bitové AND. Tabulka KOMB[k][s] se seznamem masek pro každou délku a součet se spočítá jednou na začátku průchodem všech 512 masek.bitmask, popcount
Zde e je počet prázdných polí běhu, r zbývající součet a U maska zapsaných číslic. Protože možných trojic (e, r, U) je jen 10 · 46 · 512, dá se i výsledek M(B) uložit do tabulky a příště jen přečíst – laboratoře průvodce to tak dělají.
11.2Propagace omezení
Každý běh si drží tři čísla: masku zapsaných číslic, součet zapsaných číslic a počet prázdných polí. Zápis číslice je změní v obou bězích pole v konstantním čase a kandidáti všech polí obou běhů se tím okamžitě zúží. Opakované zužování, dokud se něco mění, se nazývá propagace omezení; logické techniky z kapitol 3 až 8 jsou její silnější a silnější formy. Silnější propagace stojí víc času na krok, ale ušetří kroky prohledávání.constraint propagation
11.3Backtracking
Rekurzivní prohledávání: vyber prázdné pole, postupně do něj dosazuj povolené číslice a pro každou se zanoř hlouběji. Nemá-li některé pole žádnou povolenou číslici, je to slepá ulička – vrať se o úroveň výš a zkus další číslici. Každé dosazení je uzel stromu prohledávání.backtracking, search tree, node
11.4Heuristika nejméně možností
Pořadí polí rozhoduje. Heuristika MRV (minimum remaining values) volí vždy pole s nejmenším počtem povolených číslic; má-li některé pole jedinou možnost, dosadí se bez větvení – to je jediný kandidát z kapitoly 4. Výsledek ukazuje tabulka: kombinace zmenší strom 60krát až 470krát, MRV pak ještě 4krát až 40krát.minimum remaining values (MRV)
| Úloha | Bílých polí | Naivní | Kombinace | MRV + kombinace |
|---|---|---|---|---|
| A (5 × 5) | 12 | 3 250 | 55 | 12 |
| B (7 × 7) | 26 | 206 387 | 1 728 | 42 |
| C (9 × 9) | 44 | 1 785 793 | 3 773 | 167 |
11.5Počítání řešení do dvou
Pro test jednoznačnosti nestačí najít řešení – je třeba vědět, že jiné neexistuje. Backtracking proto po prvním řešení nepřestane a hledá dál; jakmile najde druhé, skončí: úloha není jednoznačná. Když prohledá celý strom a druhé nenajde, řešení je jediné. Přesně tohle dělá generátor v kapitole 12 a laboratoř v kapitole 10 (tam do sta řešení).
Rychlý řešič kakura stojí na třech tabulkách: kombinace podle délky a součtu, množina číslic běhu podle (prázdných polí, zbytku, použitých číslic) a popcount. S nimi a s MRV vyřeší úlohu 9 × 9 nebo 10 × 10 z průvodce v průměru za 0,1 ms; hodnocení obtížnosti (kapitola 12), které zkouší techniky jednu po druhé, trvá zhruba padesátkrát déle (měřeno v Node.js na 120 úlohách).
11.6SAT a celočíselné programování v kostce
Univerzální řešiče umějí kakuro také. Pro celočíselné programování zavedeme binární proměnnou yp,d = 1, právě když v poli p stojí d:
Úloha A z laboratoře tak má 12 · 9 = 108 proměnných a 12 + 8 · 9 + 8 = 92 omezení. Převod na SAT (splnitelnost výrokové formule) používá stejné proměnné; „právě jedna číslice v poli“ a „číslice nejvýš jednou v běhu“ jsou krátké klauzule, součet běhu se zakóduje například výčtem povolených kombinací. Moderní SAT řešiče pak zvládnou i obří mřížky – ale pro novinové úlohy je vlastní backtracking s kombinacemi jednodušší a rychlejší.integer programming, SAT encoding
11.7Procvičení
- Množiny číslic jako 9bitové masky: průnik = AND, sjednocení = OR, počet = popcount.
- Backtracking s heuristikou nejméně možností a kombinacemi zmenší strom o několik řádů.
- Test jednoznačnosti: hledat dvě řešení; kakuro jde zapsat i jako 0–1 program nebo SAT.
Tvorba úloh a variantymistr a věda
Dobrá úloha kakura vzniká ve čtyřech krocích. Nejdřív rozvržení černých a bílých polí, obvykle středově souměrné. Pak plnění číslicemi, ze kterých se spočítají nápovědy. Třetí krok je nejtěžší: ověřit, že řešení je jediné, a dokud není, číslice měnit. Nakonec hodnocení obtížnosti podle technik, které řešitel potřebuje – stejně to dělá hra. Kapitolu uzavírají varianty kakura a pár slov o zdravém hraní.
Vyplnit mřížku číslicemi tak, aby se v bězích neopakovaly, zvládne počítač za milisekundu. Jenže z 1 200 takových náhodných vyplnění mělo jediné řešení jen 3. Skutečná práce autora začíná až potom: najít a odstranit všechny „záměny“, které by řešiteli dovolily jinou odpověď.
+Teorie: rozvržení, plnění číslicemi, ověření jednoznačnosti, hodnocení obtížnosti, varianty, zdravé hraní
12.1Rozvržení
Rozvržení je „kostra“ úlohy – kde jsou černá a kde bílá pole. Klasické kakuro má tato pravidla:grid layout
- Žádné osamělé pole. Každé bílé pole leží ve vodorovném i svislém běhu aspoň dvou polí. Takto definuje úlohu i Setova práce (kapitola 10).
- Běh má nejvýš 9 polí – jinak by se v něm musela některá číslice opakovat.
- Bílá pole jsou souvislá. Dvě oddělené části by byly dvě samostatné úlohy.
- Středová souměrnost – zvyklost, ne pravidlo: rozvržení vypadá stejně po otočení o 180°.
Generátor průvodce navíc rozbíjí každý celý bílý čtverec 3 × 3 černým polem a chce, aby bílá pole tvořila aspoň 42 % vnitřku mřížky. Laboratoř hlídá první tři pravidla a souměrnost doplňuje sama: klepnutí přepne i souměrné pole.
12.2Plnění číslicemi
Nejjednodušší je vyplnit bílá pole náhodně – backtrackingem s náhodným pořadím číslic, který hlídá jen neopakování v bězích – a nápovědy spočítat jako součty. Takové zadání ale skoro nikdy nemá jediné řešení: na náhodných rozvrženích 5 × 5 až 8 × 8 mělo jediné řešení jen 3 z 1 200 vyplnění (0,25 %). Generátor proto vyplnění dál upravuje horolezením: spočítá řešení, najde dvě různá, změní číslici v poli, kde se liší, a změnu ponechá, když se počet řešení nezvýšil. Občas přijme i horší změnu, aby neuvízl.hill climbing
Změněná číslice se nesmí v obou bězích pole opakovat. Při nastavení laboratoře (3 pokusy po 250 změnách) generátor našel jednoznačné vyplnění pro 37 ze 40 náhodných rozvržení 6 × 6 a pro 35 ze 40 rozvržení 8 × 8; zbytek vzdal v limitu – pak pomůže jiné rozvržení nebo nový pokus.
12.3Ověření jednoznačnosti a záměna v obdélníku
Jednoznačnost ověří backtracking, který hledá dvě řešení (kapitola 11). Nejsnáze viditelná příčina dvou řešení je záměna v obdélníku: pole a, b leží v jednom vodorovném běhu, pole c, d v jiném, a, c v jednom svislém a b, d v jiném svislém běhu. Mají-li číslice x, y / y, x, prohození na y, x / x, y zachová v každém ze čtyř běhů stejnou množinu číslic – tedy součet i neopakování. Úloha s takovým obdélníkem v řešení proto nikdy není jednoznačná.swap rectangle, deadly pattern
Z 1 200 náhodných vyplnění mělo víc řešení 1 197 a záměnu v obdélníku obsahovalo 255 z nich (21 %). Ostatní nejednoznačnosti jsou delší cykly záměn přes víc běhů – proto generátor nepátrá po obdélnících, ale počítá řešení. Ve vzorku 1 347 hotových úloh průvodce neobsahuje záměnu v obdélníku žádná, jak má být.
Úloha s víc řešeními není kakuro, ale loterie: řešitel musí v některém okamžiku hádat a „správná“ odpověď je ta, kterou autor náhodou zapsal. Z toho plyne i obrácená úvaha, kterou zkušení řešitelé využívají: věříte-li, že úloha je jednoznačná, obdélník x y / y x v ní vzniknout nemůže. Hra i průvodce ji ale jako techniku nepoužívají.
12.4Hodnocení obtížnosti podle technik
Řešitel průvodce zkouší techniky v pevném pořadí od nejlehčí a vždy provede první, která něco zapíše nebo škrtne. Úroveň úlohy je nejvyšší úroveň techniky, kterou při tom potřeboval: 1 jediná kombinace, průnik a poslední pole; 2 jediný kandidát a vyloučení kombinací; 3 povinná číslice, meze součtu a nahé dvojice; 4 rozdíl součtů; 5 souhra běhů. Úloha, kterou ani pak nedořeší, je „mimo škálu“. Tak hodnotí úlohy i hra a používá jen úrovně 1 až 5.difficulty rating
| Mřížka | Úloh | Bílých polí ⌀ | 1 | 2 | 3 | 4 | 5 | mimo škálu |
|---|---|---|---|---|---|---|---|---|
| 5 × 5 | 150 | 10,7 | 19 | 46 | 79 | 0 | 5 | 1 |
| 6 × 6 | 293 | 14,2 | 20 | 68 | 167 | 0 | 26 | 12 |
| 7 × 7 | 295 | 20,2 | 5 | 28 | 155 | 7 | 46 | 54 |
| 8 × 8 | 284 | 28,5 | 0 | 11 | 137 | 8 | 43 | 85 |
| 9 × 9 | 184 | 35,9 | 0 | 3 | 73 | 6 | 34 | 68 |
| 10 × 10 | 141 | 41,9 | 0 | 3 | 43 | 8 | 36 | 51 |
| Celkem | 1 347 | – | 44 | 159 | 654 | 29 | 190 | 271 |
Úroveň 4 je ve vzorku vzácná (29 úloh): rozdíl součtů přijde na řadu až po všech technikách úrovně 3 a vhodná oblast se v mřížce objeví jen občas. Úroveň říká, co musíte znát; jak dlouho budete počítat, závisí i na velikosti mřížky.
12.5Varianty
Menší číslice a krátké běhy. Seta ve své práci zavedl obecné (N, l, L)-kakuro: číslice 1 až N a každý běh má aspoň l a nejvýš L polí; klasické kakuro je (9, 2, 9). S běhy nejvýš dvou polí je úloha řešitelná v lineárním čase, (9, 2, 6) je stále NP-úplné a pro 3 ≤ N ≤ 6 nechal složitost otevřenou. Menší číslice jsou i dobrá cesta pro děti: s číslicemi 1 až 4 se počítá v hlavě.(N, l, L)-CROSS SUM
Předvyplněná pole. Seta definuje i „Hinted CROSS SUM“, kde jsou některé číslice zapsané předem. Autor tak může úlohu s víc řešeními udělat jednoznačnou bez změny nápověd – předvyplněná číslice třeba rozbije záměnu v obdélníku.
Kakuro s násobením. Nápověda je součin číslic běhu místo součtu. Pravidla se u různých vydavatelů liší – někde se používají číslice 1 až 9, jinde 2 až 9, a ne všude platí zákaz opakování. Kombinatorika je jiná: součin 24 ve dvou polích dává 3 · 8 i 4 · 6, ale součin 7 jen 1 · 7.cross products
Bez některých nápověd. Zásady autorů úloh na webu GMPuzzles připouštějí, že ne každý běh musí mít nápovědu – chybějící součet může řešitel odvodit z ostatních (například rozdílem součtů z kapitoly 7). Tytéž zásady zmiňují i výjimečné jednopolové běhy, které nápovědu nikdy nemají. Hra průvodce se drží klasických pravidel: každý běh má nápovědu a aspoň dvě pole.
12.6Zdravé hraní
Kakuro je klidná hra bez časového tlaku, a přesto umí „vtáhnout“ – ještě jeden běh, ještě jedna úloha. Pár zásad:
- Přestávky. Když se zaseknete, odejděte na pár minut. Čerstvý pohled často najde průnik, který jste přehlédli.
- Nehádejte. Úloha z hry jde vyřešit logikou; hádání vede k chybám, které se těžko hledají. Raději nápověda trenéra.
- Hrajte pro radost. Rekordy a série denních výzev jsou motivace, ne povinnost. Žádné sázky ani peníze.
- Oči a spánek. Večer odložte obrazovku včas; papírové kakuro je dobrá náhrada.
12.7Procvičení
- Rozvržení: žádné osamělé pole, běhy 2 až 9 polí, souvislá bílá pole, obvykle středová souměrnost.
- Náhodné vyplnění má jediné řešení jen výjimečně; generátor ho upravuje, dokud řešení není jediné.
- Obtížnost = nejtěžší potřebná technika. Varianty: menší číslice, předvyplněná pole, násobení, chybějící nápovědy.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky podle úrovní
| Úroveň | Techniky | Kapitola |
|---|---|---|
| 1 | Jediná kombinace, Průnik běhů, Poslední pole běhu | 2, 3 |
| 2 | + Jediný kandidát, Vyloučení kombinací | 4, 5 |
| 3 | + Povinná číslice, Meze součtu, Nahá dvojice v běhu | 5, 6 |
| 4 | + Rozdíl součtů | 7 |
| 5 | + Souhra běhů | 8 |
| mimo škálu | úloha je jednoznačná, ale technikami průvodce ji řešitel nedořeší | 12 |
Vzorce na jednom místě
Magické bloky
| Polí | Součet → kombinace |
|---|---|
| 2 | 3 → 12, 4 → 13, 16 → 79, 17 → 89 |
| 3 | 6 → 123, 7 → 124, 23 → 689, 24 → 789 |
| 4 | 10 → 1234, 11 → 1235, 29 → 5789, 30 → 6789 |
| 5 | 15 → 12345, 16 → 12346, 34 → 46789, 35 → 56789 |
| 6 | 21 → 123456, 22 → 123457, 38 → 356789, 39 → 456789 |
| 7 | 28 → 1234567, 29 → 1234568, 41 → 2456789, 42 → 3456789 |
| 8 | každý součet 36 až 44: chybí číslice 45 − s (9 bloků) |
| 9 | 45 → 123456789 |
Počty na jednom místě
| Údaj | Hodnota | Kde |
|---|---|---|
| kombinace pro běhy 2 až 9 polí / všechny neprázdné množiny číslic | 502 / 511 | kap. 9 |
| nejvíc kombinací pro jednu dvojici délka–součet | 12 (20/4 a 25/5) | kap. 9 |
| magické bloky (jediná kombinace) | 34 | kap. 2 |
| úloha z kapitoly 1 bez zákazu opakování | 566 řešení | kap. 1 |
| úlohy vzorku s polem jistým průnikem hned na začátku | 997 z 1 347 (74 %) | kap. 3 |
| uzly backtrackingu, úloha 9 × 9: naivní / kombinace / MRV | 1 785 793 / 3 773 / 167 | kap. 11 |
| náhodná vyplnění s jediným řešením | 3 z 1 200 (0,25 %) | kap. 12 |
| vzorek průvodce: úroveň 1 / 2 / 3 / 4 / 5 / mimo | 44 / 159 / 654 / 29 / 190 / 271 | 1 347 úloh, kap. 12 |
Zdroje a předpoklady
Historické údaje a výsledky výzkumu byly ověřeny na uvedených zdrojích. Ověřeno 8. 11. 2026.
Historie hry
- Conceptis Puzzles: Kakuro history (conceptispuzzles.com) – datace Willa Shortze (Official Crossword Puzzles, Dell, duben/květen 1950), autor Jacob E. Funk, rozšíření v časopisech Dell do poloviny 60. let, Nikoli 1980, jméno kakuro a první sbírka 1986, nejoblíbenější hádanka Nikoli do roku 1992, britské deníky v září 2005. Ověřeno 8. 11. 2026.
- Encyklopedické heslo Kakuro (Wikipedie, anglická verze) a prameny v něm citované – kasan kurosu, Funk a rok 1966, pořadí britských deníků (The Guardian, The Telegraph, Daily Mail), NP-úplnost podle Sety a Yata a Sety. Ověřeno 8. 11. 2026.
- Encyklopedické heslo カックロ (Wikipedie, japonská verze) – název 加算クロス, první otištění v časopise Puzzle Tsushin Nikoli č. 7 (leden 1982), uvedení v měsíčníku NikoList v srpnu 1983. Ověřeno 8. 11. 2026.
- Nikoli: Kakuro – pravidla a poznámka o prvním otištění (nikoli.co.jp, anglická verze). Ověřeno 8. 11. 2026.
- Pulham, A. (2005): sloupek o nástupu kakura v britských denících (2005), převzatý agregátorem zpráv inkl: kakuro v deníku The Guardian od 14. září, v The Telegraph o den později. Ověřeno 8. 11. 2026.
Matematika a algoritmy
- Seta, T. (2002): The complexities of puzzles, CROSS SUM and their another solution problems (ASP). Bakalářská práce (senior thesis), Department of Information Science, Faculty of Science, University of Tokyo, odevzdáno 5. 2. 2002, vedoucí H. Imai – definice CROSS SUM, (N, l, L)-CROSS SUM a Hinted CROSS SUM, převody z PARTITION INTO CIRCUITS, 3SAT a ONE-IN-THREE 3SAT. Ověřeno na plném textu 8. 11. 2026.
- Yato, T.; Seta, T. (2003): Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. IEICE Transactions on Fundamentals E86-A(5), 1052–1060. Stránka vydavatele nebyla dostupná; bibliografické údaje ověřeny z citací a výpisu vyhledávače 8. 11. 2026.
- Ruepp, O.; Holzer, M. (2010): The Computational Complexity of the Kakuro Puzzle, Revisited. In: Fun with Algorithms (FUN 2010), Lecture Notes in Computer Science 6099, Springer, 319–330. Ověřeno 8. 11. 2026 (bibliografické údaje a úvod abstraktu).
Tvorba úloh a varianty
- GMPuzzles (Grandmaster Puzzles): zásady pro autory kakura – ne každý běh musí mít nápovědu, jednopolové běhy jen výjimečně a nikdy s nápovědou. Ověřeno 8. 11. 2026.
- Kakuro s násobením (Cross Products): pravidla podle popisů několika vydavatelů nalezených vyhledávačem; liší se rozsahem číslic (1–9, nebo 2–9) a tím, zda se číslice smějí opakovat. Ověřeno 8. 11. 2026.
Modelové předpoklady laboratoří
Všechny tabulky kombinací, úlohy a statistiky počítá kód průvodce; každá úloha v textu a v laboratořích má ověřeně jediné řešení (backtracking s heuristikou MRV, který hledá dvě řešení). Logický řešitel zkouší techniky v pevném pořadí podle tabulky B.1 a ú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ň; „mimo škálu“ proto neznamená „nejtěžší“, jen „nad rámec technik průvodce“. Vzorek pro statistiky v kapitolách 3, 7 a 12 je 1 347 úloh 5 × 5 až 10 × 10 se středovou souměrností z generátoru z kapitoly 12. Počty uzlů v kapitole 11 jsou pevné; časy měří prohlížeč a liší se podle zařízení. Pole se v textu označují ř (řádek) a s (sloupec) včetně řádku a sloupce nápověd, horní levé pole je ř1s1.
Co zůstává nejisté
Rok, kdy Jacob E. Funk vymyslel Cross Sums, uvádějí prameny různě (1950 podle Conceptis a Shortze, 1966 v jiném pramenu). Rozcházejí se i data příchodu do Japonska (1980 podle Conceptis, leden 1982 a srpen 1983 podle japonské Wikipedie) a rok přejmenování na kakuro (1986) známe jen z jednoho pramene. Přesné datum prvního kakura v deníku The Guardian známe jen ze sloupku převzatého agregátorem, ne z archivu deníku. Z práce Ruepp a Holzer (2010) jsme ověřili jen bibliografické údaje a úvod abstraktu (nový důkaz NP-úplnosti); zda pozdější práce rozhodly složitost (N, l, L)-kakura pro 3 ≤ N ≤ 6, kterou Seta ponechal otevřenou, jsme neověřovali. Pravidla kakura s násobením se u vydavatelů liší a průvodce je proto popisuje jen obecně.