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

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.

krok řešení–
technika–
vyplněno–
kandidátů v poznámkách–
Úvodem

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

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Pravidla, pojmy a historiezákladybí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á kombinacezákladyrozsah 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í polezákladyprůnik množin číslic dvou křížících se běhů, dopočet posledního pole, kde úlohu začít
4 Kandidáti tužkouzákladyjak 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á číslicepokroč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é dvojicepokroč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é úlohypokroč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ědakolik 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žitostmistr a vědakakuro 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ědabitové 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 variantymistr a vědarozvrž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šší.

Tab. 0.2Úrovně obtížnosti v průvodci a ve 3D hře
ÚroveňNejtěžší potřebná technikaKapitola
1jediná kombinace, průnik běhů, poslední pole běhu2, 3
2jediný kandidát, vyloučení kombinací4, 5
3povinná číslice, meze součtu, nahá dvojice v běhu5, 6
4rozdíl součtů7
5souhra běhů8
mimo škáluúloha potřebuje víc než techniky průvodce8, 11
Statistiky „ve vzorku“ se týkají 1 347 úloh, které generátor z kapitoly 12 vyrobil s pevnými semínky (mřížky 5 × 5 až 10 × 10 včetně řádku a sloupce nápověd, středově souměrné rozvržení, jediné řešení) 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, kdo ji pojmenoval a co o ní dokázali matematici.

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

Hrajte

Kakuro ve 3D

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

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. Panel kombinací u vybraného pole vypíše kombinace vodorovného i svislého běhu a škrtne ty, které už nejdou (kapitola 5). Nápověda trenéra má tři stupně: první klepnutí ukáže, kam se dívat, druhé pojmenuje techniku a třetí ji provede; vždy s odkazem na kapitolu, kde se technika vykládá. Poznámky tužkou můžete psát ručně nebo nechat doplnit automaticky (kapitola 4), tahy jde vracet i opakovat a chyby kontrolovat hned, nebo až na konci. 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í se kostky ve vlně přetočí na zlatou stranu.
Část IZáklady
1

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.

zadánířešení71811971115412345123457181197111544713522814311234512345
Obr. 1.1 Malá úloha kakuro (vlevo) a její řešení (vpravo). Bílých polí je 12, běhů 8. Vodorovný běh 15/4 ve 4. řádku je podbarvený modře, svislý běh 18/3 ve 3. sloupci zeleně; jejich nápovědy jsou oranžové. Kříží se v poli ř4s3, kde v řešení stojí 8 – patří do obou součtů najednou: 2 + 8 + 1 + 4 = 15 a 7 + 3 + 8 = 18.
První kakuro
Klepněte na bílé pole: laboratoř podbarví oba jeho běhy, zvýrazní jejich nápovědy a vypíše, kolik kombinací číslic připadá v úvahu. Pak klepněte na číslici. „Zkontrolovat“ označí běhy, ve kterých se číslice opakuje nebo nesedí součet. Za vyřešení bez ukázání řešení získáte 15 XP.
LABORATOŘ
Model: úloha z obr. 1.1 – mřížka 5 × 5 včetně řádku a sloupce nápověd, 12 bílých polí, 8 běhů, jediné řešení, úroveň 1. Řešitel průvodce ji vyřeší za 12 kroků jen průnikem běhů a posledním polem běhu (kapitola 3). Zkuste začít v pravém dolním rohu: běh 4/2 jinak než 1 + 3 vyplnit nejde.
+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:

Pravidla kakuro\[ x_p \in \{1, \dots, 9\}, \qquad \sum_{p \in B} x_p = s_B, \qquad x_p \ne x_q \ \text{ pro } p \ne q,\ p, q \in B \]

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.

Příklad Pole ř5s3 v obr. 1.1

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

Rozsah součtu běhu k polí\[ 1 + 2 + \dots + k = \frac{k(k+1)}{2} \ \le\ s \ \le\ \frac{k(19-k)}{2} = 9 + 8 + \dots + (10-k) \]
Pozor

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

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

19501960197019801990200020101950Cross SumsDell, Official Crossword Puzzlespol. 60. letve všech hádankovýchčasopisech Dell1980–1983JaponskoNikoli: kasan kurosu1986jméno kakuroprvní sbírka Nikoli2002NP-úplnostT. Seta, Tokijská univerzitazáří 2005The Guardiana další deníky
Obr. 1.2 Kakuro v čase. Americké Cross Sums (1950), rozšíření v časopisech Dell, cesta do Japonska a jméno kakuro, důkaz NP-úplnosti (modře, kapitola 10) a evropská vlna roku 2005. Údaje, ve kterých se prameny rozcházejí, jsou uvedeny rozpětím; zdroje v příloze C.

1.5Kakuro a sudoku

Tab. 1.1Co mají kakuro a sudoku společného a čím se liší
SudokuKakuro
číslice1–91–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ří do3 skupin2 běhů
klíčová dovednostskenováníkombinace součtů
nejbližší příbuznýKiller sudoku – sudoku s klecemi a součty (průvodce Sudoku, kapitola 9)

1.6Procvičení

1
Běh tří polí má nápovědu 6. Které číslice v něm stojí?
1, 2 a 3 v nějakém pořadí. Nejmenší možný součet tří různých číslic je 1 + 2 + 3 = 6, takže jiná možnost není. Pořadí určí křížící se běhy.
2
Kolik různých hodnot může mít nápověda běhu dvou polí?
Od 1 + 2 = 3 do 8 + 9 = 17, tedy 15 hodnot. Součty 2 a 18 by vyžadovaly 1 + 1 nebo 9 + 9, a to pravidla zakazují.
3
Černé pole má nad úhlopříčkou 16 a pod ní 4; oba běhy mají dvě pole. Co v nich stojí?
Vodorovný běh vpravo od pole má součet 16: jedině 7 + 9. Svislý běh pod polem má součet 4: jedině 1 + 3. V obou případech zbývá určit jen pořadí.
4
V řádku mřížky stojí dvě trojky. Je to chyba?
Jen pokud leží ve stejném běhu. Oddělí-li je černé pole, jde o dva různé běhy a dvě trojky jsou v pořádku.
5
Sečtěte v obr. 1.1 všechny vodorovné nápovědy a pak všechny svislé. Co zjistíte?
Vodorovně 11 + 11 + 15 + 4 = 41, svisle 7 + 18 + 9 + 7 = 41. Obě čísla jsou součtem všech číslic v mřížce, protože každé bílé pole leží v jednom vodorovném a jednom svislém běhu. Tuhle rovnost využívá technika rozdílu součtů v kapitole 7.
Co si odnést
  • 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.
Část IZáklady
2

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.

Kalkulačka kombinací
Zvolte délku běhu a součet. Laboratoř vypíše všechny kombinace číslic. Klepnutím na číslici řeknete, že v běhu musí být (zeleně), dalším klepnutím, že tam nesmí být (červeně); třetí klepnutí podmínku zruší. Nevyhovující kombinace se přeškrtnou a vpravo dole uvidíte číslice, které jsou ve všech zbylých kombinacích.
LABORATOŘ
Model: kombinace je množina navzájem různých číslic 1–9 s daným počtem prvků a součtem; na pořadí nezáleží. Laboratoř je bere z předpočítané tabulky všech 511 neprázdných podmnožin číslic (jak se taková tabulka ukládá, ukazuje kapitola 11). Podmínky „musí / nesmí“ odpovídají poznámkám z křížících se běhů – přesně tak s nimi pracuje kapitola 5.
Minihra: Jediná, nebo víc?
Laboratoř ukáže součet a délku běhu. Rozhodněte, jestli má jedinou kombinaci číslic, nebo víc. Správná odpověď a seznam kombinací se ukážou až po volbě. Kolo má osm běhů a za aspoň šest správných odpovědí získáte 15 XP.
MINIHRA
0 / 8
+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“.

Tab. 2.1Rozsah součtů a počet kombinací pro běhy 2 až 9 polí
PolíNejmenší součetNejvětší součetMožných součtůKombinací celkemSoučtů s jedinou kombinací
231715364
362419844
41030211264
51535211264
6213919844
7284215364
83644999
94545111
Spočítáno výčtem všech podmnožin číslic 1–9. Součtů s jedinou kombinací je celkem 34.
2 pole3416173 pole6723244 pole101129305 polí151634356 polí212238397 polí282941428 polí36 až 44: chybí 45 − s9 polí45051015202530354045součet běhu
Obr. 2.1 Pro každou délku běhu vodorovná úsečka od nejmenšího po největší součet. Oranžové body jsou součty s jedinou kombinací („magické bloky“), malé šedé body součty s více kombinacemi. U délek 2 až 7 leží magické bloky vždy jen na krajích – dva nejmenší a dva největší součty. U osmi polí je magický každý součet.

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

Tab. 2.2Všech 34 součtů s jedinou kombinací
PolíSoučet → kombinace
23 → 1 2 · 4 → 1 3 · 16 → 7 9 · 17 → 8 9
36 → 1 2 3 · 7 → 1 2 4 · 23 → 6 8 9 · 24 → 7 8 9
410 → 1 2 3 4 · 11 → 1 2 3 5 · 29 → 5 7 8 9 · 30 → 6 7 8 9
515 → 1 2 3 4 5 · 16 → 1 2 3 4 6 · 34 → 4 6 7 8 9 · 35 → 5 6 7 8 9
621 → 1–6 · 22 → 1–5 a 7 · 38 → 3 5 6 7 8 9 · 39 → 4–9
728 → 1–7 · 29 → 1–6 a 8 · 41 → 2 4 5 6 7 8 9 · 42 → 3–9
836 až 44: všechny číslice kromě 45 − s
945 → 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.

Zrcadlo číslic a doplněk do devíti\[ s \ \leftrightarrow\ 10k - s \quad (d \mapsto 10 - d), \qquad (k,\ s)\ \leftrightarrow\ (9 - k,\ 45 - s) \quad (\text{chybějící číslice}) \]

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.

Mistrovská pomůcka

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.

Tab. 2.3Běhy 3 a 4 polí, které mají víc kombinací, ale povinnou číslici
BěhKombinaceVždy obsahuje
8/31 2 5 · 1 3 41
22/35 8 9 · 6 7 99
12/41 2 3 6 · 1 2 4 51 a 2
13/41 2 3 7 · 1 2 4 6 · 1 3 4 51
27/43 7 8 9 · 4 6 8 9 · 5 6 7 99
28/44 7 8 9 · 5 6 8 98 a 9
U dvou polí žádný takový součet není; u pěti polí jich je šest (17, 18, 19, 31, 32 a 33).
Pozor

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í

1
Jakou jedinou kombinaci má součet 29 ve čtyřech polích?
Největší součet čtyř polí je 6 + 7 + 8 + 9 = 30; o jedna menší vznikne jen zmenšením nejmenší číslice: 5 + 7 + 8 + 9.
2
Kolik kombinací má součet 23 ve třech polích a kolik součet 7 ve třech polích?
Obojí jednu: 6 + 8 + 9 a 1 + 2 + 4. Jsou to zrcadla: 30 − 7 = 23 a každá číslice d přejde na 10 − d.
3
Běh osmi polí má součet 40. Které číslice v něm stojí?
Všechny kromě 45 − 40 = 5, tedy 1, 2, 3, 4, 6, 7, 8 a 9. U osmi polí je každý součet magický.
4
Ve dvou prázdných polích rozpracovaného běhu zbývá doplnit 4. Je to vždy 1 + 3?
Jen pokud jednička a trojka v běhu ještě nejsou. Kdyby tam už jednička stála, nešlo by součet 4 doplnit vůbec – v úloze je chyba. Rozpracovaný běh se posuzuje podle zbývajícího součtu, počtu prázdných polí a už použitých číslic.
5
Proč má součet 10 ve dvou polích čtyři kombinace, ale součet 3 jen jednu?
10 = 1 + 9 = 2 + 8 = 3 + 7 = 4 + 6 (5 + 5 je zakázané), zatímco 3 = 1 + 2 jinak nejde. Součty uprostřed rozsahu mají nejvíc kombinací – celé rozdělení ukazuje kapitola 9.
Co si odnést
  • 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í.
Část IZáklady
3

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.

Křížení dvou běhů
Nastavte délku a součet vodorovného a svislého běhu, které se kříží v jednom poli. Laboratoř vypíše, které číslice smí každý běh (sjednocení všech jeho kombinací), a jejich průnik. Je-li průnik jediná číslice, pole se rovnou vyplní. Předvolby ukazují klasická křížení, která stojí za zapamatování.
LABORATOŘ
→ vodorovně
↓ svisle
Model: oba běhy jsou zatím prázdné. Množina číslic běhu je sjednocení všech jeho kombinací (kapitola 2); pole na křížení smí jen číslice z průniku obou množin. Prázdný průnik znamená, že taková dvojice nápověd se v dobré úloze vyskytnout nemůže.
Minihra: Najdi pole, které jde vyplnit
Laboratoř ukáže rozpracovanou úlohu úrovně 1 bez poznámek. Najděte pole, které jde vyplnit s jistotou – průnikem běhů nebo jako poslední pole běhu –, klepněte na ně a pak na číslici. Správnost a všechna jistá pole se ukážou až po volbě. Kolo má osm pokusů a za aspoň šest správných získáte 15 XP.
MINIHRA
0 / 8
+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 běhů\[ x_p \in M\big(H(p)\big) \cap M\big(V(p)\big), \qquad \big|M(H(p)) \cap M(V(p))\big| = 1 \ \Rightarrow\ x_p \text{ je ta jediná číslice} \]
71811971115411234512345
Obr. 3.1 První krok úlohy z kapitoly 1. Vodorovný běh 4/2 (modře) smí jen {1, 3}, svislý běh 7/3 (zeleně) jen {1, 2, 4}. Pole ř5s5 leží v obou a jejich průnik je jediná číslice 1 (oranžově).

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ěť:

Tab. 3.1Dvojice běhů dvou polí, jejichž průnik je jediná číslice (spočítáno výčtem všech 105 dvojic různých součtů)
KříženíPoleKříženíPole
3/2 × 4/217/2 × 15/26
3/2 × 11/228/2 × 16/27
4/2 × 6/219/2 × 16/27
4/2 × 11/239/2 × 17/28
4/2 × 12/2314/2 × 16/29
5/2 × 13/2416/2 × 17/29
6/2 × 14/25
Například 3/2 × 11/2: běh 3/2 smí {1, 2}, běh 11/2 smí {2, …, 9} (jednička by potřebovala desítku). Společná je jen 2. Tabulka platí pro prázdné běhy; v rozpracované úloze se množiny zmenšují a jistých průniků přibývá.

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

Poslední pole běhu\[ x_p = s_B - \sum_{q \in B,\ q \ne p} x_q \]
Pozor

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

7181197111544713522814311112576391084211234512345
Obr. 3.2 Pořadí, v jakém řešitel průvodce vyplní úlohu z kapitoly 1. Malé oranžové číslo vlevo nahoře je číslo kroku. Oranžově podbarvená pole vyřešil průnik běhů (5 kroků), modře poslední pole běhu (7 kroků).
Tab. 3.2Dvanáct kroků první úlohy (stejné pořadí jako na obr. 3.2)
KrokPoleTechnikaÚvaha
1ř5s5 = 1průnik4/2 smí {1, 3}, 7/3 smí {1, 2, 4}
2ř5s4 = 3poslední pole4 − 1
3ř3s5 = 2průnik11/4 smí {1, 2, 3, 5}; ve svislém 7/3 zbývá 6 do dvou polí: {2, 4}
4ř4s5 = 4poslední pole7 − 2 − 1
5ř3s2 = 1průnikv 11/4 zbývá 9 do tří polí: {1, 3, 5}; svislý 7/3 smí {1, 2, 4}
6ř3s4 = 5průnikv 11/4 zbývá 8 do dvou polí: {3, 5}; ve svislém 9/3 zbývá 6: {1, 2, 4, 5}
7ř3s3 = 3poslední pole11 − 1 − 5 − 2
8ř4s4 = 1poslední pole9 − 5 − 3
9ř4s2 = 2průnikv 15/4 zbývá 10 do dvou polí: {2, 3, 7, 8}; ve svislém 7/3 zbývá 6: {2, 4}
10ř4s3 = 8poslední pole15 − 2 − 1 − 4
11ř2s2 = 4poslední pole7 − 1 − 2
12ř2s3 = 7poslední pole11 − 4
Příklad Krok 6 podrobně

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.

Mistrovská pomůcka

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í

1
Pole leží na křížení běhů 16/2 a 17/2. Co v něm stojí?
16/2 smí {7, 9}, 17/2 smí {8, 9}. Průnik je 9.
2
Pole leží na křížení běhů 6/3 a 24/3. Co z toho plyne?
6/3 smí {1, 2, 3}, 24/3 smí {7, 8, 9}. Průnik je prázdný – taková dvojice nápověd v řešitelné úloze být nemůže. Pokud ji vidíte, špatně jste přečetli nápovědu nebo běh.
3
Běh 23/3 má vyplněno 9 a 6. Co patří do posledního pole?
23 − 9 − 6 = 8. Souhlasí to s jedinou kombinací 6 + 8 + 9.
4
V běhu 12/3 stojí v jednom poli 5, zbylá dvě pole jsou prázdná. Které číslice do nich připadají? A kdyby místo pětky stála šestka?
S pětkou zbývá 7 do dvou polí bez pětky: 1 + 6, 2 + 5 (zakázáno, pětka už je), 3 + 4 → {1, 3, 4, 6}. Se šestkou zbývá 6 do dvou polí bez šestky: {1, 2, 4, 5} (1 + 5, 2 + 4). Jakmile se vyplní jedno z polí, druhé je poslední pole běhu a dopočítá se.
5
Kolik procent úloh vzorku nemá na začátku žádné pole jisté průnikem běhů?
(1 347 − 997) / 1 347 = 350 / 1 347 ≈ 26 %. V nich se začíná poznámkami a jejich postupným škrtáním.
Co si odnést
  • 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.
Část IZáklady
4

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.

Tužka a guma
„Napsat poznámky“ doplní do každého prázdného pole kandidáty z průniku jeho dvou běhů. „Krok“ provede nejjednodušší techniku úrovně 1 nebo 2, která v pozici něco přinese, a zapíše ji do deníku: modře pole, ze kterých závěr plyne, oranžově zapsaná číslice, červeně škrtnutí kandidáti. „Dořešit“ dojde až na konec.
LABORATOŘ
Model: tři úlohy 7 × 7 včetně řádku a sloupce nápověd. Úloha A (20 bílých polí) je úrovně 1 a řešitel ji projde za 20 kroků bez jediné poznámky. Úlohy B (26 polí, 52 kroků) a C (22 polí, 33 kroků) jsou úrovně 2: potřebují jediný kandidát a vyloučení kombinací z kapitoly 5. Poznámky se počítají jen z pravidel a z technik, které laboratoř pojmenuje.
Co v dlouhém běhu chybí
V dlouhých bězích je snazší počítat číslice, které nejsou. Zvolte délku a součet: laboratoř spočítá součet chybějících číslic 45 − s a vypíše všechny možnosti, které dávají.
LABORATOŘ
Model: všech devět číslic dává dohromady 1 + 2 + … + 9 = 45. Chybí-li v běhu k polí 9 − k číslic, jejich součet je 45 − s. Místo kombinací k číslic stačí hledat kombinace 9 − k chybějících – u sedmi polí jen dvojice.
+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.

Kandidáti z průniku běhů\[ K(p) = M\big(H(p)\big) \cap M\big(V(p)\big) \]

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.

Příklad Běh 15/3 po prvním zápisu

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

Jediný kandidát\[ K(p) = \{d\} \ \Rightarrow\ x_p = d \]
1023336812273225221926615121626859745784357892345678934567892413578913456789345678923456793456793491241234343445457812345671234567
Obr. 4.1 Úloha B z laboratoře před prvním jediným kandidátem. Vyplněno je 6 z 26 polí, v poznámkách je 81 kandidátů. V poli ř2s6 (oranžově) zbyla jediná číslice 4. Svislý běh 6/2 je 1 + 5, nebo 2 + 4; pole ř3s6 pod ním ale smí jen 2 nebo 4 (to zařídil běh 32/5 ve 3. řádku), takže zbývá 2 + 4. Vodorovný běh 12/2 dvojku nepřipouští – a zbude čtyřka.

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

Chybějící číslice\[ \sum_{d \notin B} d = 45 - s_B, \qquad \text{běh } k \text{ polí postrádá } 9 - k \text{ číslic} \]
Tab. 4.1Běh sedmi polí: které dvě číslice chybějí
SoučetChybíSoučetChybí
288 9361 8 · 2 7 · 3 6 · 4 5
297 9371 7 · 2 6 · 3 5
306 9 · 7 8381 6 · 2 5 · 3 4
315 9 · 6 8391 5 · 2 4
324 9 · 5 8 · 6 7401 4 · 2 3
333 9 · 4 8 · 5 7411 3
342 9 · 3 8 · 4 7 · 5 6421 2
351 9 · 2 8 · 3 7 · 4 6
Chybějící dvojice má součet 45 − s; počet možností je počet kombinací dvou různých číslic s tímto součtem (kapitola 9).

4.5Chyby z nepozornosti

Pozor

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

Mistrovská pomůcka

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í

1
Běh 8 polí má součet 39. Která číslice v něm chybí?
45 − 39 = 6.
2
Běh 7 polí má součet 30. Které dvojice číslic mohou chybět?
Součet chybějících je 45 − 30 = 15: 6 + 9 nebo 7 + 8. Jistě tedy v běhu jsou 1, 2, 3, 4 a 5.
3
Pole leží ve vodorovném běhu, jehož prázdná pole smějí {2, 4, 6}, a ve svislém běhu, jehož prázdná pole smějí {1, 4, 7}. Co v poli stojí?
Průnik je {4} – jediný kandidát.
4
Do běhu 15/3 zapíšete 8. Které číslice smějí zbylá dvě pole?
Zbývá 7 do dvou polí bez osmičky: 1 + 6, 2 + 5, 3 + 4 → {1, 2, 3, 4, 5, 6}. Zmizely 7, 8 a 9.
5
V úloze A z laboratoře nejsou potřeba žádné poznámky. Jak to?
Je to úloha úrovně 1: v každé chvíli existuje pole jisté průnikem dvou běhů nebo poslední pole běhu. Poznámky jsou nástroj na pole, kde jistota hned není; u úrovně 1 takové pole nikdy nezůstane jako jediná možnost.
Co si odnést
  • 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.
Část IIPokročilí
5

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

Editor běhu: kombinace a povinné číslice
Jeden běh, jeho prázdná pole a jejich kandidáti. Klepnutím na číslici v poli ji škrtnete nebo vrátíte – jako by ji vyloučil křížící se běh. Laboratoř hned přeškrtne kombinace, které už nesedí, a vypíše proč. Červené číslice jdou škrtnout, zelená je povinná číslice, která se vejde jen do jednoho pole (skrytý singl v běhu). „Provést škrty“ je zapíše.
LABORATOŘ
Model: prázdný běh k polí se zbývajícím součtem s; kandidáti polí jsou zadané ručně nebo předvolbou. Kombinace odpadá, když některé pole nemá žádnou z jejích číslic, nebo když některá její číslice nemá v běhu pole, kam by se vešla. A: první pole smí jen 8 a 9. B: navíc třetí pole nesmí 1. C: kandidáti z rozpracované úlohy. D: všechny číslice 1–9 musí mít kam jít. Změna délky nebo součtu vrátí všem polím všechny kandidáty dovolené součtem.
Minihra: Které kombinace zbudou?
Laboratoř ukáže běh z rozpracované úlohy a kandidáty jeho prázdných polí. Označte všechny kombinace, které s kandidáty ještě sedí, a stiskněte „Vyhodnotit“. Uznává se jen přesná shoda. Kolo má pět úloh a za aspoň čtyři správné získáte 15 XP.
MINIHRA
0 / 5
+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

Kombinace rozpracovaného běhu\[ \mathcal{C}(B) = \Big\{\, M \subseteq \{1,\dots,9\} \setminus U :\ |M| = m,\ \sum_{d \in M} d = r \,\Big\} \]

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

Vyloučení kombinací\[ K(p) \leftarrow K(p) \cap \bigcup_{M \in \mathcal{C}'(B)} M \qquad \text{pro všechna prázdná } p \in B \]

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.

6104221717191513135678912312367898978923896789561234512345
Obr. 5.1 Vyloučení kombinací. Vodorovný běh 19/3 ve 4. řádku (modře) má pět kombinací: 2 8 9, 3 7 9, 4 6 9, 4 7 8 a 5 6 8. Pole ř4s4 smí jen 2 nebo 3 (svislý běh 6/3 nad ním), takže zůstávají jen kombinace s dvojkou nebo trojkou: 2 8 9 a 3 7 9. Pětka a šestka nejsou v žádné z nich – na ř4s3 se škrtají (červeně).

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

Příklad Předvolba D v laboratoři

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

Povinná číslice\[ d \in \bigcap_{M \in \mathcal{C}'(B)} M \ \Rightarrow\ d \text{ v běhu } B \text{ stojí} \]

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

301581332615126727789789789456789678923457897893457891211234512345
Obr. 5.2 Povinná číslice. Svislý běh 15/4 ve 4. sloupci (modře) má šest kombinací, ale pole ř3s4 smí jen 7, 8 nebo 9, takže zbývají čtyři: 1 3 4 7, 1 2 5 7, 1 2 4 8 a 1 2 3 9. Jednička je ve všech – v běhu být musí. Kandidáta 1 (zakroužkovaný) má jen pole ř2s4 (zeleně), a tak tam jednička patří, i když pole smí ještě 2 a 7.
Mistrovská pomůcka

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.

Pozor

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í

1
Běh 12/3, první pole smí jen 8 nebo 9. Které kombinace zůstanou a která číslice je povinná?
Z kombinací 1 2 9, 1 3 8, 1 4 7, 1 5 6, 2 3 7, 2 4 6 a 3 4 5 obsahují osmičku nebo devítku jen 1 2 9 a 1 3 8. Povinná je 1. Zbylá dvě pole smějí jen {1, 2, 3}.
2
Totéž, ale třetí pole nesmí 1. Kde stojí jednička?
Jednička je povinná, první pole ji mít nemůže (smí jen 8, 9) a třetí také ne – zbývá druhé pole. Skrytý singl v běhu.
3
Běh 10/2 má kandidáty {1, 2, 3, 4} a {6, 7, 8}. Které kombinace sedí?
10 = 1 + 9, 2 + 8, 3 + 7, 4 + 6. Kombinace 1 9 odpadá – devítka nemá pole. Zůstává 2 8, 3 7 a 4 6; žádná číslice není povinná.
4
Běh 13/4 má kombinace 1 2 3 7, 1 2 4 6 a 1 3 4 5. Jedničku smí jen jedno pole. Co platí?
Jednička je ve všech třech kombinacích, takže je povinná, a protože ji smí jediné pole, stojí v něm. To je předvolba C v laboratoři.
5
Běh 10/3 má kandidáty {1, 2}, {3, 7} a {3, 5, 7}. Které kombinace sedí? Pozor, jedna past projde oběma rychlými zkouškami.
Kombinace 10/3 jsou 1 2 7, 1 3 6, 1 4 5 a 2 3 5. Kombinace 1 4 5 odpadá podle zkoušky (a) – druhé pole nemá 1, 4 ani 5; 1 3 6 podle zkoušky (b) – šestka nemá pole. Kombinace 1 2 7 obě zkoušky projde, ale jednička i dvojka se vejdou jen do prvního pole, takže ji rozdělit nejde (párování neexistuje). Zbývá jen 2 3 5: první pole 2, druhé 3, třetí 5. Řešitel průvodce takovou past odhalí technikou meze součtu (kapitola 6), která zkouší zbytek běhu poctivě i s kandidáty.
Co si odnést
  • 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.
Část IIPokročilí
6

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.

Editor běhu: meze, parita a nahé dvojice
Stejný editor jako v kapitole 5, ale tentokrát počítá pro každé pole meze ze zbytku běhu a úplnou kontrolu: které číslice v poli projdou, když zbytek běhu se svými kandidáty musí dát přesně zbývající součet. Červené číslice jdou škrtnout. Najde také nahé dvojice a trojice. „Provést škrty“ je zapíše.
LABORATOŘ
Model: prázdný běh se zbývajícím součtem a ručně zadanými kandidáty. U každého pole je vypsané rozpětí, kam ho meze ze zbytku běhu pustí, a seznam číslic, které projdou úplnou kontrolou. A: kamarádi z úvodu. B: krátký běh s vysokým součtem. C: parita – sudý součet a sudé číslice ve druhém poli. D: nahá dvojice {1, 3} a meze zbytku.
Minihra: Platí vždy, nebo neplatí?
Rozhodněte o každém tvrzení o mezích, paritě a nahých dvojicích, jestli platí vždy, nebo ne. Vysvětlení se ukáže po výběru. Za aspoň pět správných ze sedmi získáte 15 XP.
MINIHRA
0 / 7
+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

Meze součtu\[ L = \min \sum_{q \ne p} x_q, \quad H = \max \sum_{q \ne p} x_q \ \Rightarrow\ r - H \ \le\ x_p\ \le\ r - L \]
61042217171915131356789123798978923896789131234512345
Obr. 6.1 Meze součtu. Ve vodorovném běhu 17/3 ve 3. řádku (modře) dají pole ř3s3 a ř3s4 se svými kandidáty dohromady nejméně 5 + 1 = 6 a nejvýš 9 + 3 = 12. Na ř3s5 proto musí být aspoň 17 − 12 = 5: jednička a trojka se škrtají (červeně) a zbudou 7 a 9.

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.

Úplná kontrola\[ d \in K(p) \text{ obstojí} \iff r - d \in \Big\{\, \textstyle\sum_{q \ne p} x_q :\ x_q \in K(q) \setminus \{d\},\ x_q \text{ navzájem různé} \Big\} \]

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

Příklad Předvolba A: kamarádi z úvodu

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

Parita\[ \sum_{p \in B} x_p \equiv \big|\{\,p \in B : x_p \text{ liché}\,\}\big| \pmod 2 \]
Mistrovská pomůcka

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á podmnožina\[ |C| = k,\ \Big|\bigcup_{p \in C} K(p)\Big| = k \ \Rightarrow\ d \notin K(q) \ \text{pro } q \in B \setminus C,\ d \in \bigcup_{p \in C} K(p) \]
211910142219917171667891234679568956789567912323123123456792346789123456787979565656656123456123456
Obr. 6.2 Nahá dvojice. Pole ř4s2 a ř4s3 (modře) ve vodorovném běhu 17/5 mají oba jen kandidáty 5 a 6 (zakroužkované). Jedno z nich je 5, druhé 6, takže pětka a šestka se škrtají na ř4s4, ř4s5 a ř4s6 (červeně). Zbylá tři pole pak musí dát 17 − 11 = 6, tedy 1 + 2 + 3.
Pozor

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í

1
Běh 15/2 má kandidáty {6, 7, 8, 9} a {7, 8}. Co plyne pro první pole?
Druhé pole je 7 nebo 8, první tedy 15 − 8 = 7 až 15 − 7 = 8: {7, 8}. Šestka a devítka padají (meze). To je předvolba B.
2
Běh 10/2: druhé pole smí jen sudé číslice. Které číslice smí první pole?
Součet 10 je sudý, druhé pole sudé, takže i první musí být sudé: 2, 4, 6, 8. Lichá 1, 3, 7 a 9 padají paritou – meze by je pustily.
3
Běh 18/4: dvě pole mají kandidáty {1, 3} a {1, 3}. Které číslice smějí zbylá dvě pole?
Dvojice spotřebuje 1 + 3 = 4, zbylá dvě pole dají 14 bez jedničky a trojky: 5 + 9 nebo 6 + 8 (7 + 7 je zakázané). Smějí tedy {5, 6, 8, 9} – předvolba D.
4
Ostatní pole běhu dají nejméně 6 a nejvýš 12, zbývající součet je 15. Může zkoumané pole obsahovat 4?
Podle mezí ne: pole musí být 15 − 12 = 3 až 15 − 6 = 9, a čtyřka v rozpětí je. Meze ji tedy neškrtnou. Zda zbytek umí dát přesně 11, rozhodne až úplná kontrola.
5
Kolik lichých číslic má běh osmi polí se součtem 40?
Chybí 45 − 40 = 5, tedy lichá číslice. Z pěti lichých zbudou čtyři. Kontrola parity: čtyři liché dají sudý součet, 40 je sudé.
Co si odnést
  • 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.
Část IIPokročilí
7

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

Rozdíl součtů na vybrané oblasti
Klepnutím do bílých polí vyberte běhy jednoho směru. Laboratoř přidá běhy druhého směru, které jimi procházejí (modré kroužky u jejich prvních polí), sečte obě skupiny nápověd a oranžově vyznačí pole, o která se pokrytí liší. Zbude-li jediné prázdné pole navíc, laboratoř ho dopočítá. „Úvaha řešitele“ ukáže oblast, kterou v pozici našel řešitel průvodce.
LABORATOŘ
Model: tři úlohy úrovně 4 ve stavu, kdy jim nestačí žádná technika úrovně 1 až 3. Příklad A (7 × 7, vyplněno 5 z 26 polí): vodorovné běhy 6/2 a 7/2. Příklad B (8 × 8, vyplněno 18 z 37 polí): tři svislé běhy proti třem vodorovným. Příklad C (7 × 7, vyplněno 5 z 22 polí): dva svislé běhy proti dvěma vodorovným. Výběr můžete libovolně měnit – laboratoř vždy spočítá, o kolik se oba směry liší.
+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

Rovnost součtů\[ \sum_{H} s_H \;=\; \sum_{p} x_p \;=\; \sum_{V} s_V \]

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

Rozdíl součtů\[ \sum_{p \in E} x_p \;=\; \sum_{V \in B} s_V \;-\; \sum_{H \in A} s_H \]

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

3152269697202919151418161424122081245456121231256789456784565789567857812489797895679589482612345671234567
Obr. 7.1 Příklad A z laboratoře. Vodorovné běhy 6/2 a 7/2 (modře, podtržené nápovědy) pokrývají čtverec ř2s2–ř3s3 se součtem 6 + 7 = 13. Svislé běhy, které jím procházejí – 3/2 a 15/3, oranžové nápovědy, modré kroužky u prvních polí –, pokrývají stejná čtyři pole a navíc pole ř4s3 (oranžově); jejich součet je 3 + 15 = 18. Na ř4s3 proto stojí 18 − 13 = 5.

7.3Odvození na příkladech

Příklad A: proč nic jiného nepomůže

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.

Příklad B: tři proti třem

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

Mistrovská pomůcka

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

Pozor

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í

1
Úloha má vodorovné nápovědy 16, 17, 24 a 23. Jaký je součet svislých nápověd?
16 + 17 + 24 + 23 = 80, protože oba součty se rovnají součtu všech číslic v mřížce.
2
Svislé běhy 5/2 a 6/2 pokrývají čtyři pole. Vodorovné běhy 7/2 a 11/3, které jimi procházejí, pokrývají tatáž pole a navíc jedno prázdné pole. Kolik v něm je?
(7 + 11) − (5 + 6) = 18 − 11 = 7. To je příklad C z laboratoře, pole ř3s5.
3
Rozdíl součtů vyšel 12, ale navíc jsou dvě pole a jedno z nich je vyplněné číslicí 4. Kolik je ve druhém?
12 − 4 = 8.
4
Rozdíl součtů vyšel 12 a navíc jsou dvě prázdná pole ve stejném běhu. Co víte?
Jejich součet je 12, takže tvoří „neviditelný běh“ 12/2: 3 + 9, 4 + 8 nebo 5 + 7. Jejich kandidáti se zúží na {3, 4, 5, 7, 8, 9}. Leží-li v různých bězích, opakovat se mohou a přibude i 6 + 6.
5
Proč rozdíl součtů nefunguje, když vyberete jen část vodorovného běhu?
Součet z nápovědy patří celému běhu. O části běhu víte jen to, že je menší než nápověda, a rovnost v oddíle 7.2 se rozpadne.
Co si odnést
  • 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á.
Část IIPokročilí
8

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.

Souhra běhů ve čtverci 2 × 2
Laboratoř ukáže rozpracovanou úlohu ve chvíli, kdy jí nestačí žádná technika úrovně 1 až 4. Čtverec 2 × 2 je modře, nápovědy čtyř běhů, které jím procházejí, oranžově. Pod mřížkou jsou běhy s kandidáty (čtverec v hranatých závorkách). „Zkoušet naráz“ vypíše všechna dosazení do čtverce a u každého běh, který ho vyloučí; pak se v mřížce ukážou škrty.
LABORATOŘ
Model: dvě úlohy 5 × 5 úrovně 5. Dosazení podle kandidátů jsou všechny čtveřice číslic, ve kterých má každé pole některého svého kandidáta a ve dvojicích téhož běhu se číslice neopakují. Dosazení projde, když každý ze čtyř běhů jde s ním doplnit – ostatní pole běhu se svými kandidáty dají přesně zbývající součet. Příklad A: 6 dosazení, projde 1. Příklad B: 42 dosazení, projde 1.
Minihra: Logika, nebo hádání?
Zařaďte každý postup: je to logický krok, nebo hádání? Vysvětlení se ukáže po výběru. Za aspoň pět správných ze šesti získáte 15 XP.
MINIHRA
0 / 6
+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

  1. vypište všechna dosazení kandidátů do čtyř polí čtverce, ve kterých se v žádném běhu neopakuje číslice;
  2. 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?
  3. dosazení, které neprojde aspoň jedním během, odpadá; v každém poli čtverce zůstanou jen číslice z dosazení, která prošla.
Souhra běhů\[ x_p \in \big\{\, t_p :\ t \in T,\ t \text{ vyhoví všem čtyřem běhům} \,\big\}, \qquad T = K(p_1) \times K(p_2) \times K(p_3) \times K(p_4) \]

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

610422171719151327316791989792389671234512345
Obr. 8.1 Příklad A z laboratoře. Čtverec ř2s4–ř3s5 (modře) má kandidáty {1, 3}, {1, 3}, {1, 2} a {7, 9}. Kříží se v něm vodorovné běhy 4/2 a 17/3 a svislé 6/3 a 10/2 (oranžové nápovědy). Ze šesti dosazení projde všemi čtyřmi běhy jen jedno; červeně jsou škrtnuté číslice, které v něm nejsou.
Tab. 8.1Všech šest dosazení do čtverce v příkladu A a běh, který je vyloučí
ř2s4ř2s5ř3s4ř3s5Výsledek
1327✗ → 17/3: na ř3s3 by muselo být 17 − 2 − 7 = 8, smí jen 6, 7, 9
1329✗ ↓ 10/2: 3 + 9 = 12, ne 10
3117✗ ↓ 10/2: 1 + 7 = 8, ne 10
3119✓ projde: 3 + 1 = 4, 1 + 9 = 10, ř4s4 = 6 − 3 − 1 = 2, ř3s3 = 17 − 1 − 9 = 7
3127✗ → 17/3: na ř3s3 by muselo být 8
3129✗ ↓ 6/3: na ř4s4 by muselo být 6 − 3 − 2 = 1, smí jen 2, 3
Dosazení (1, 3, 1, …) chybí, protože ř2s4 a ř3s4 leží ve stejném svislém běhu 6/3 a jednička by se v něm opakovala.

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

  1. Magické bloky a jejich křížení – projděte všechny krátké běhy s krajními součty (kapitoly 2 a 3).
  2. Dlouhé běhy – spočítejte chybějící číslice 45 − s (kapitola 4).
  3. 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ě.
  4. 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.
  5. 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).

Pozor

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.

Mistrovská pomůcka

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í

1
Kolik dosazení do čtverce 2 × 2 nejvýš existuje, má-li každé pole dva kandidáty?
2 · 2 · 2 · 2 = 16, bez opakování v bězích obvykle méně (v příkladu A 6, protože dvojice v běhu se nesmí rovnat).
2
V tab. 8.1 projde jediné dosazení. Co z něj zapíšete?
Všechna čtyři pole: ř2s4 = 3, ř2s5 = 1, ř3s4 = 1, ř3s5 = 9. A hned i ř3s3 = 7 a ř4s4 = 2 jako poslední pole běhů.
3
Řešitel zvolí v poli s kandidáty {3, 8} trojku, dořeší celou úlohu bez sporu a zapíše výsledek. Je to logické řešení?
Ne, je to hádání se štěstím. Logické by bylo ukázat, že osmička vede ke sporu – nebo najít techniku, která osmičku vyloučí bez zkoušení celé mřížky.
4
V poli nezbyl žádný kandidát. Co to znamená?
Někde je chyba – ve správně vedených poznámkách má každé prázdné pole aspoň jednoho kandidáta, totiž číslici z řešení.
5
Proč není souhra běhů totéž co průnik běhů?
Průnik se dívá na jedno pole a dva běhy, souhra na čtyři pole a čtyři běhy najednou. V příkladu A připouští každé křížení dvou běhů víc možností a teprve čtveřice běhů je zúží na jedinou.
Co si odnést
  • 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.
Část IIIMistr a věda
9

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.

Počítadlo kombinací
Zvolte délku běhu a součet. Graf ukáže počet kombinací pro všechny součty dané délky: oranžově součty s jedinou kombinací, zeleně zvolený součet. Pod grafem počet pořadí jedné kombinace, počet všech vyplnění samostatného běhu a obě souměrnosti.
LABORATOŘ
Model: počty jsou spočítané výčtem všech 511 neprázdných podmnožin číslic 1–9 (bitových masek, kapitola 11). „Vyplnění běhu“ je počet kombinací krát k! – kolika způsoby jde vyplnit samotný běh, kdyby ho nekřížily jiné běhy.
+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

Tab. 9.1Počet kombinací c(k, s) pro všechny délky a součty (od nejmenšího součtu po největší)
kSoučtyPočty kombinacíCelkem
23–171 1 2 2 3 3 4 4 4 3 3 2 2 1 136
36–241 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 184
410–301 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1126
515–351 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1126
621–391 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 184
728–421 1 2 2 3 3 4 4 4 3 3 2 2 1 136
836–441 1 1 1 1 1 1 1 19
94511
Spočítáno výčtem. Například pro k = 3 a s = 15 je desátá hodnota řádku 8: 1 5 9, 1 6 8, 2 4 9, 2 5 8, 2 6 7, 3 4 8, 3 5 7, 4 5 6. Běhů 2 až 9 polí je dohromady 502 kombinací, s jednopolními „běhy“ 511.
2 pole: 3–17střed 10, nejvíc 43 pole: 6–24střed 15, nejvíc 84 pole: 10–30střed 20, nejvíc 125 polí: 15–35střed 25, nejvíc 126 polí: 21–39střed 30, nejvíc 87 polí: 28–42střed 35, nejvíc 4
Obr. 9.1 Počet kombinací podle součtu pro délky 2 až 7 (svislé měřítko je u všech stejné, nejvyšší sloupec má 12 kombinací). Oranžové sloupce jsou magické bloky z kapitoly 2. Rozdělení jsou souměrná kolem středu 5k a dvojice 2 a 7, 3 a 6, 4 a 5 mají stejný tvar.

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

Vytvořující funkce kombinací\[ \prod_{d=1}^{9} \big(1 + y\,x^{d}\big) \;=\; \sum_{k=0}^{9} \sum_{s=0}^{45} c(k, s)\, y^{k} x^{s} \]

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:

Souměrnosti\[ c(k, s) = c(k,\ 10k - s), \qquad c(k, s) = c(9 - k,\ 45 - s) \]

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

Tab. 9.2Součty s nejvíce kombinacemi
kStřed 5kNejčetnější součtyKombinací
2109, 10, 114
31514, 15, 168
4202012
5252512
63029, 30, 318
73534, 35, 364

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.

Vyplnění samostatného běhu\[ N(k, s) = c(k, s) \cdot k! \]
Příklad Kolik je magických bloků

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í

1
Kolik kombinací má běh 3 polí se součtem 12? Vypište je.
Sedmá hodnota řádku k = 3: 7 – 1 2 9, 1 3 8, 1 4 7, 1 5 6, 2 3 7, 2 4 6, 3 4 5.
2
Bez počítání: kolik kombinací má 18/3, víte-li, že 12/3 jich má 7?
Zrcadlo: 10 · 3 − 12 = 18, takže také 7.
3
Kolik kombinací má 30/6? Použijte doplněk.
Doplněk: c(6, 30) = c(3, 15) = 8. Šest číslic se součtem 30 je přesně tolik jako trojic se součtem 15, které chybějí.
4
Kolika způsoby jde vyplnit samostatný běh 10/4?
Jediná kombinace 1 2 3 4 a 4! = 24 pořadí.
5
Kolik je dvojic (délka 2–9, součet), tedy různých nápověd s délkou?
15 + 19 + 21 + 21 + 19 + 15 + 9 + 1 = 120 (počty možných součtů z tab. 2.1). Z nich 34 jsou magické bloky.
Co si odnést
  • Řá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í.
Část IIIMistr a věda
10

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.

Měňte součty: jednoznačnost a soustava rovnic
Vyberte běh (tlačítkem nebo klepnutím na nápovědu v mřížce) a měňte jeho součet o ±1. Laboratoř pokaždé spočítá všechna řešení (do 100) a ukáže první z nich; oranžově jsou pole, ve kterých se liší první dvě nalezená řešení. Změnou jediné nápovědy úlohu vždy pokazíte – zkuste proč – a změnou jedné vodorovné a jedné svislé najdete jiné dobré i špatné úlohy.
LABORATOŘ
Model: úloha 5 × 5 s 12 bílými poli a 8 běhy (4 vodorovné, 4 svislé), původně s jediným řešením. Řešení počítá backtracking z kapitoly 11 až do 100 nalezených. Hodnost soustavy je spočítaná Gaussovou eliminací matice 8 × 12 z obr. 10.1.
+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

Kakuro jako celočíselná soustava\[ A\mathbf{x} = \mathbf{s}, \qquad x_p \in \{1, \dots, 9\}, \qquad x_p \ne x_q \ \text{ pro } p \ne q \text{ ve stejném běhu} \]
ř2s2ř2s3ř2s4ř3s2ř3s3ř3s4ř4s3ř4s4ř4s5ř5s3ř5s4ř5s5→ 23/3111= 23→ 7/3111= 7→ 17/3111= 17→ 11/3111= 11↓ 7/211= 7↓ 20/41111= 20↓ 14/41111= 14↓ 17/211= 17
Obr. 10.1 Matice soustavy pro úlohu z laboratoře: 8 běhů (řádky, → vodorovné modře, ↓ svislé zeleně) a 12 bílých polí (sloupce). Každý sloupec má dvě jedničky. Vpravo jsou nápovědy – pravé strany rovnic.

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

Hodnost a volné parametry\[ \operatorname{rank} A = m - 1, \qquad \dim \ker A = n - m + 1 \]

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

Příklad Laboratoř

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

Z historie

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.

Pozor

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í

1
Úloha má 20 bílých polí a 13 běhů a je souvislá. Jakou hodnost má soustava a kolik má volných parametrů?
Hodnost 12, volných parametrů 20 − 13 + 1 = 8.
2
Proč změna jediné nápovědy vždy vede k úloze bez řešení?
Součet vodorovných nápověd se musí rovnat součtu svislých (oba jsou součtem všech číslic). Změna jedné nápovědy rovnost poruší, takže žádné vyplnění nemůže vyhovět.
3
Ověřit navržené řešení kakura n × n trvá kolik operací, zhruba?
Každé pole se přičte do dvou běhů a porovná s ostatními číslicemi běhu – řádově n² operací (s malou konstantou). Rychlé ověření je jedna z podmínek příslušnosti do NP.
4
Co je „another solution problem“ a proč na něm záleží tvůrcům?
Otázka, zda úloha s daným řešením má ještě jiné řešení. Tvůrce potřebuje odpověď „ne“ – jinak úloha není jednoznačná. Seta ukázal, že i tahle otázka je u kakura NP-úplná; v praxi ji řeší backtracking, který hledá dvě řešení (kapitola 11).
5
Kolik celočíselných řešení s číslicemi 1–9 by měla úloha z laboratoře bez zákazu opakování?
27 (spočítáno úplným výčtem). Se zákazem opakování zůstane jediné.
Co si odnést
  • 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í.
Část IIIMistr a věda
11

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.

Backtracking pod lupou
Vyberte úlohu a strategii. Laboratoř úlohu vyřeší, hledá přitom dvě řešení (test jednoznačnosti) a spočítá uzly – každé dosazení číslice do pole. Graf porovná všechny tři strategie v logaritmickém měřítku. „Přehrát“ ukáže prvních až 6 000 dosazení a návratů, jak je algoritmus zkoušel.
LABORATOŘ
Model: naivní – pole v pořadí čtení, zkouší každou číslici, která v obou bězích ještě není, a kontroluje jen přetečení součtu a součet hotového běhu; kombinace – stejné pořadí, ale jen číslice z průniku kombinací obou běhů (bitové masky); MRV + kombinace – vždy pole s nejméně možnostmi. Úlohy: A z kapitoly 1 (12 polí), B z kapitoly 4 (26 polí), C je jedna z úloh úvodní ukázky (44 polí). Čas měří váš prohlížeč a liší se podle zařízení; počty uzlů jsou pevné.
+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

987654321číslo4/2 → {1, 3}00000010157/3 → {1, 2, 4}00000101111AND → {1}0000000011
Obr. 11.1 Průnik běhů jako jediná instrukce. Běh 4/2 smí {1, 3} = maska 5, běh 7/3 smí {1, 2, 4} = maska 11. Bitové AND dá masku 1 = {1}: pole na křížení je jednička (obr. 3.1). Sloupce jsou číslice 9 až 1, jako bity zleva doprava.
Množina číslic běhu z masek\[ M(B) = \bigvee_{\substack{m \in \mathrm{KOMB}[e][r] \\ m \wedge U = 0}} m, \qquad K(p) = M\big(H(p)\big) \wedge M\big(V(p)\big) \]

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)

Tab. 11.1Počet uzlů (dosazení) při hledání dvou řešení – úlohy z laboratoře
ÚlohaBílých políNaivníKombinaceMRV + kombinace
A (5 × 5)123 2505512
B (7 × 7)26206 3871 72842
C (9 × 9)441 785 7933 773167
Spočítáno stejným kódem, jaký běží v laboratoři. Úloha A s MRV potřebuje 12 uzlů na 12 polí: v každém kroku má některé pole jedinou možnost a strom se vůbec nevětví. Úroveň obtížnosti pro člověka a počet uzlů spolu souvisejí jen volně.

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

Mistrovská pomůcka

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:

Kakuro jako 0–1 program\[ \sum_{d=1}^{9} y_{p,d} = 1 \ \ \forall p, \qquad \sum_{p \in B} y_{p,d} \le 1 \ \ \forall B, d, \qquad \sum_{p \in B} \sum_{d=1}^{9} d \cdot y_{p,d} = s_B \ \ \forall B \]

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

1
Jakou masku má množina {2, 5, 9}?
21 + 24 + 28 = 2 + 16 + 256 = 274 (binárně 100010010).
2
Masky dvou běhů jsou 56 a 28. Co smí pole na jejich křížení?
56 = {4, 5, 6}, 28 = {3, 4, 5}; AND = 24 = {4, 5}.
3
Proč MRV v úloze A potřebuje jen 12 uzlů?
V každém kroku existuje pole s jedinou povolenou číslicí (průnik kombinací obou běhů). MRV ho vybere a dosadí bez větvení – je to úloha úrovně 1, kterou řeší průnik a poslední pole.
4
Kolik proměnných a omezení má 0–1 program pro úlohu B z laboratoře (26 polí, 16 běhů)?
26 · 9 = 234 proměnných; 26 + 16 · 9 + 16 = 186 omezení.
5
Backtracking našel první řešení. Proč nemůže skončit, když chceme ověřit jednoznačnost?
Jiné řešení by mohlo ležet v neprozkoumané části stromu. Jednoznačnost potvrdí jen úplné prohledání bez nalezení druhého řešení.
Co si odnést
  • 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.
Část IIIMistr a věda
12

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

Návrhář malé úlohy
Klepnutím přepínejte bílá a černá pole (horní řádek a levý sloupec zůstávají černé pro nápovědy). Kontrola průběžně hlídá osamělá pole, délky běhů a souvislost. „Vyplnit a ověřit“ najde číslice s jediným řešením a ohodnotí obtížnost technikami průvodce; „Náhodné rozvržení“ navrhne mřížku za vás.
LABORATOŘ
Model: rozvržení musí mít každé bílé pole ve vodorovném i svislém běhu o 2 až 9 polích a bílá pole musí být souvislá. Plnění: náhodné vyplnění bez opakování v bězích, pak horolezení – mění číslici v poli, kde se dvě nalezená řešení liší, a změnu ponechá, když počet řešení (počítaný do 40) neroste; nejvýš 3 pokusy po 250 změnách. Obtížnost: nejvyšší úroveň techniky, kterou řešitel průvodce použil (kapitoly 2 až 8). Úlohy „mimo škálu“ jsou jednoznačné, ale řešitel průvodce je bez zkoušení nedořeší.
+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

  1. Žá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).
  2. Běh má nejvýš 9 polí – jinak by se v něm musela některá číslice opakovat.
  3. Bílá pole jsou souvislá. Dvě oddělené části by byly dvě samostatné úlohy.
  4. Středová souměrnost – zvyklost, ne pravidlo: rozvržení vypadá stejně po otočení o 180°.
Středová souměrnost v mřížce n × n (r řádek, s sloupec; řádek 1 a sloupec 1 jsou nápovědy)\[ (r,\ s) \;\longleftrightarrow\; (n + 2 - r,\ \ n + 2 - s), \qquad 2 \le r, s \le n \]

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.

a) v pořádkub) osamělé polec) záměna 1 2 / 2 17181197111544713522814311063912663733331221
Obr. 12.1 a) Úloha z kapitoly 1: rozvržení bez osamělých polí s jediným řešením. b) Pole ř4s2 (oranžově) leží ve svislém běhu tří polí, ale vodorovně nemá bílého souseda – běh délky 1 je chyba rozvržení. c) Čtverec 2 × 2 s nápovědami 3/2 ve všech čtyřech bězích má dvě řešení: 1 2 / 2 1 i 2 1 / 1 2. Modrá a zelená pole si číslice prohodí a žádný součet se nezmění.

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

Krok horolezení (N = počet řešení, počítaný nejvýš do 40)\[ v' = v \text{ s jednou změněnou číslicí}, \qquad v \leftarrow v' \;\text{ pokud }\; N(v') \le N(v), \;\text{ jinak s pravděpodobností } 0{,}04 \]

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

Příklad Jak častá je záměna

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.

Pozor

Ú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

Tab. 12.1Úrovně 1 347 úloh z generátoru průvodce podle velikosti mřížky
MřížkaÚlohBílých polí ⌀12345mimo škálu
5 × 515010,7194679051
6 × 629314,2206816702612
7 × 729520,252815574654
8 × 828428,501113784385
9 × 918435,9037363468
10 × 1014141,9034383651
Celkem1 347–4415965429190271
Mřížka včetně řádku a sloupce nápověd. Všechny úlohy mají jediné řešení; generátor obtížnost nevolí, jen ji změří. S velikostí roste podíl úloh mimo škálu – z 1 ze 150 u 5 × 5 na 51 ze 141 u 10 × 10.

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

1
Mřížka 8 × 8 má středově souměrné rozvržení. Které pole je souměrné k ř3s5?
ř = 8 + 2 − 3 = 7, s = 8 + 2 − 5 = 5: ř7s5.
2
Proč rozvržení nesmí obsahovat běh deseti polí?
V běhu se číslice neopakují a různých číslic je jen devět.
3
V řešení najdete pole s číslicemi 4 7 (jeden vodorovný běh) a pod nimi 7 4 (jiný vodorovný běh), přičemž obě čtveřice leží ve stejných dvou svislých bězích. Co to znamená?
Záměna v obdélníku: prohozením na 7 4 / 4 7 vznikne druhé řešení se stejnými nápovědami. Úloha není jednoznačná.
4
Generátor vyrobil jednoznačnou úlohu, ale řešitel průvodce ji ohodnotil „mimo škálu“. Je to chyba?
Není. Řešení je jediné, jen k němu nevede žádná technika z kapitol 2 až 8 – řešitel by musel zkoušet. Hra takové úlohy nepoužije.
5
Kolik kombinací má v kakuru s násobením běh dvou polí se součinem 12, jsou-li číslice 1 až 9 bez opakování?
12 = 2 · 6 = 3 · 4, tedy dvě kombinace ({2, 6} a {3, 4}); 1 · 12 nejde, 12 není číslice.
Co si odnést
  • 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.
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.1Úrovně obtížnosti průvodce a hry
ÚroveňTechnikyKapitola
1Jediná kombinace, Průnik běhů, Poslední pole běhu2, 3
2+ Jediný kandidát, Vyloučení kombinací4, 5
3+ Povinná číslice, Meze součtu, Nahá dvojice v běhu5, 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
Řešitel průvodce zkouší techniky v pořadí poslední pole běhu, průnik běhů, jediná kombinace, jediný kandidát, vyloučení kombinací, povinná číslice, nahá dvojice v běhu, meze součtu, rozdíl součtů, souhra běhů a vždy provede první, která něco zapíše nebo škrtne. Úroveň úlohy je nejvyšší úroveň použité techniky.

Vzorce na jednom místě

Pravidla (kap. 1)\[ x_p \in \{1, \dots, 9\}, \qquad \sum_{p \in B} x_p = s_B, \qquad x_p \ne x_q \ \text{ pro } p \ne q \text{ ve stejném běhu} \]
Rozsah součtu běhu k polí (kap. 2)\[ \frac{k(k+1)}{2} \ \le\ s \ \le\ \frac{k(19-k)}{2} \]
Zrcadlo a doplněk (kap. 2, 9)\[ c(k, s) = c(k,\ 10k - s), \qquad c(k, s) = c(9 - k,\ 45 - s) \]
Průnik běhů a kandidáti (kap. 3, 4)\[ K(p) = M\big(H(p)\big) \cap M\big(V(p)\big), \qquad |K(p)| = 1 \ \Rightarrow\ x_p \text{ je ta jediná číslice} \]
Poslední pole a chybějící číslice (kap. 3, 4)\[ x_p = s_B - \sum_{q \in B,\ q \ne p} x_q, \qquad \sum_{d \notin B} d = 45 - s_B \]
Povinná číslice (kap. 5)\[ d \in \bigcap_{M \in \mathcal{C}'(B)} M \ \Rightarrow\ d \text{ v běhu } B \text{ stojí} \]
Meze součtu (kap. 6)\[ r - H \ \le\ x_p\ \le\ r - L, \qquad L, H = \text{nejmenší a největší součet zbytku běhu} \]
Rozdíl součtů (kap. 7)\[ \sum_{H} s_H = \sum_{V} s_V, \qquad \sum_{p \in E} x_p = \sum_{V \in B} s_V - \sum_{H \in A} s_H \]
Kombinatorika (kap. 9)\[ \prod_{d=1}^{9} \big(1 + y\,x^{d}\big) = \sum_{k, s} c(k, s)\, y^{k} x^{s}, \qquad \sum_{s} c(k, s) = \binom{9}{k}, \qquad N(k, s) = c(k, s) \cdot k! \]
Soustava rovnic (kap. 10)\[ A\mathbf{x} = \mathbf{s}, \qquad \operatorname{rank} A = m - 1, \qquad \dim \ker A = n - m + 1 \]
0–1 program (kap. 11)\[ \sum_{d} y_{p,d} = 1, \qquad \sum_{p \in B} y_{p,d} \le 1, \qquad \sum_{p \in B} \sum_{d} d\, y_{p,d} = s_B \]
Středová souměrnost (kap. 12; r řádek, s sloupec, mřížka n × n)\[ (r,\ s) \;\longleftrightarrow\; (n + 2 - r,\ n + 2 - s) \]

Magické bloky

Tab. B.2Všech 34 dvojic délka–součet s jedinou kombinací (spočítáno výčtem)
PolíSoučet → kombinace
23 → 12, 4 → 13, 16 → 79, 17 → 89
36 → 123, 7 → 124, 23 → 689, 24 → 789
410 → 1234, 11 → 1235, 29 → 5789, 30 → 6789
515 → 12345, 16 → 12346, 34 → 46789, 35 → 56789
621 → 123456, 22 → 123457, 38 → 356789, 39 → 456789
728 → 1234567, 29 → 1234568, 41 → 2456789, 42 → 3456789
8každý součet 36 až 44: chybí číslice 45 − s (9 bloků)
945 → 123456789

Počty na jednom místě

Tab. B.3Čísla z kapitol průvodce
ÚdajHodnotaKde
kombinace pro běhy 2 až 9 polí / všechny neprázdné množiny číslic502 / 511kap. 9
nejvíc kombinací pro jednu dvojici délka–součet12 (20/4 a 25/5)kap. 9
magické bloky (jediná kombinace)34kap. 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čátku997 z 1 347 (74 %)kap. 3
uzly backtrackingu, úloha 9 × 9: naivní / kombinace / MRV1 785 793 / 3 773 / 167kap. 11
náhodná vyplnění s jediným řešením3 z 1 200 (0,25 %)kap. 12
vzorek průvodce: úroveň 1 / 2 / 3 / 4 / 5 / mimo44 / 159 / 654 / 29 / 190 / 2711 347 úloh, kap. 12
PřílohaC

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

Interaktivní průvodce Kakuro (listopad 2026). 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, programy ani vydavatele sbírek.