Malované křížovky
Nonogramy – obrázky z čísel
od první řady po algoritmy
Na pozadí luští počítač malovanou křížovku tak jako člověk. V každém kroku hledá nejjednodušší techniku, která ještě něco přinese – od překryvu a hotové řady přes okraj a nedosažitelná pole po všechna umístění a zkoušku sporem – a pojmenuje ji. Modrý pruh je řada, ve které se právě přemýšlí, oranžově jsou nově zapsaná pole. Techniky vysvětlují kapitoly 2 až 6 a stejný řešitel hodnotí obtížnost vlastních křížovek v kapitole 12.
Jak průvodce používat
Malovaná křížovka – také japonská křížovka nebo nonogram – je mřížka s čísly u řádků a sloupců. Čísla říkají, jak dlouhé souvislé úseky polí se mají v řadě vybarvit. Kdo je správně vybarví, odkryje obrázek: hrnek, plachetnici, sovu nebo maják. Žádné slovo, žádné počítání do vysokých čísel, jen čistá logika řad, které se navzájem kříží. Průvodce vede od pravidel a prvních jistých polí přes techniky, které používají zkušení luštitelé, až ke kombinatorice, složitosti a k tomu, jak křížovky řeší a vyrábí počítač. Je pro začátečníky, rodiče s dětmi, luštitele, kteří se chtějí zlepšit, i pro studenty matematiky a informatiky.
Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra s vlastní řadou či mřížkou, 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 malované křížovky ve 3D: desku z dřevěných kostek, ze které vybarvená pole vyskakují, pět obtížností podle technik z tohoto průvodce, denní výzvu, malé mřížky pro děti a trenéra, který ukáže další logický krok a odkáže na kapitolu, kde se technika vykládá.
Mapa průvodce
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Pravidla, pojmy a historie | základy | řada, legenda, blok, vybarvené pole a křížek, volnost; jak hádanka vznikla v Japonsku a jak se dostala do Evropy |
| 2 Překryv a hotová řada | základy | nejlevější a nejpravější poloha bloků, překryv a jeho délka, řada, ve které už stojí všechny bloky |
| 3 Okraj a nedosažitelná pole | základy | jak vybarvené pole a křížek přitlačí bloky, dosah bloku, krátké mezery mezi křížky |
| 4 Komu patří vybarvený úsek | základy | přiřazování úseků k číslům legendy, pořadí bloků, doplnění a uzavření bloku, spolupráce řádku a sloupce |
| 5 Všechna umístění | pokročilí | průnik všech umístění bloků, jak je vypsat ručně, kdy najde víc než jednodušší techniky |
| 6 Zkouška sporem | pokročilí | co dělat, když se řady zaseknou; předpoklad, šíření, spor; proč to není hádání |
| 7 Velké a barevné křížovky | pokročilí | pořadí řad na mřížce 20 × 20, kontrola chyb, barevné křížovky a jejich mezery |
| 8 Dobrý obrázek | pokročilí | rozlišení a rastrování, proč některé obrázky mají víc řešení a jak je opravit, hustota a jednoznačnost |
| 9 Počítáme umístění, legendy a řešení | mistr a věda | vzorec C(n − s + 1, k), Fibonacciho čísla v počtu legend, kolik obrázků má jediné řešení – výčet a simulace |
| 10 Složitost a tomografie | mistr a věda | NP-úplnost (Ueda a Nagao 1996), rekonstrukce obrázku ze součtů (Ryser 1957), záměny 2 × 2 |
| 11 Jak křížovky řeší počítač | mistr a věda | řešič řady dynamickým programováním, fronta řad, zkouška sporem a prohledávání, relaxace a celočíselné programování |
| 12 Tvorba úloh a zdravé hraní | mistr a věda | od nápadu k mřížce, kontrola jednoznačnosti, hodnocení obtížnosti podle technik, křížovky ve škole, rozumná míra |
Co budete potřebovat
Tužku, gumu a čtverečkovaný papír – nebo jen prst na displeji. Všechny úlohy z průvodce jsou v laboratořích, takže tisknout nic nemusíte. Pro první část stačí umět sčítat malá čísla a počítat políčka; dítě, které spočítá do dvaceti, zvládne první křížovku 5 × 5. Od kapitoly 9 se hodí kombinační čísla, v kapitolách 10 a 11 trocha 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říbuzné logické hádanky s čísly v průvodcích Sudoku a Kakuro, souřadnice, sčítání a čtverečkovaný papír pro děti v průvodci Matematika pro 1. stupeň, kombinační čísla a posloupnosti v průvodci Matematika, důkaz sporem v průvodci Logika a kritické myšlení, odhady z náhodných pokusů v průvodci Statistika a algoritmy, dynamické programování a složitost 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. Pole v jedné řadě se číslují 1, 2, 3, … zleva doprava, u sloupce shora dolů. Vybarvené pole je tmavé, prázdné pole označuje křížek, neznámé pole je bílé. Laboratoře, hero i 3D hra používají stejného lidského řešitele, který v každé řadě zkouší techniky od nejjednodušší.
| Úroveň | Nejtěžší potřebná technika | Kapitola |
|---|---|---|
| 1 | Překryv, Hotová řada | 2 |
| 2 | Nedosažitelná pole, Okraj | 3 (přiřazování úseků v 4) |
| 3 | Všechna umístění | 5 |
| 4 | Zkouška sporem | 6 |
| mimo škálu | nestačí ani zkouška sporem s jedním polem | 11 |
Čtyři druhy rámečků
Konkrétní řada nebo mřížka, kterou si můžete ověřit v laboratoři.
Jak hádanka vznikla, kdo ji pojmenoval a co o ní dokázali matematici a informatici.
Rychlé pravidlo, zkratka nebo návyk, který používají zkušení luštitelé.
Č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). Křížovky, tabulky, 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 (kombinační čísla, hvězdičky a přepážky, Fibonacciho čísla, počítání 0–1 matic s danými součty) na úrovni úvodních vysokoškolských kurzů; informatika – dynamické programování, šíření omezení, prohledávání s návratem a teorie složitosti (NP-úplnost, převody) na úrovni úvodních vysokoškolských kurzů; pravidla – klasické černobílé a barevné malované křížovky podle pramenů uvedených v příloze C.
Malované křížovky ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
Luštěte na desce z dřevěných kostek; legenda stojí na lištách nahoře a vlevo a čísla hotových řad zešednou. Vybarvené pole vyskočí jako tmavá kostka, křížek se do kostky vyryje. Po vyřešení dostane obrázek své barvy, zvedne se do barevného reliéfu, kamera ho obletí a obrázek i s názvem přibude do vaší sbírky. Na výběr je Klasické (10 × 10 až 20 × 20 podle obtížnosti), Denní výzva (v daný den stejná křížovka pro všechny), Pro děti (5 × 5 až 8 × 8) a Velké obrázky (20 × 20 a 25 × 25 pro vytrvalé). Obtížnost 1 až 5 odpovídá technikám z průvodce: 1 překryv a hotová řada z kapitoly 2, 2 navíc nedosažitelná pole a okraj z kapitoly 3, 3 všechna umístění z kapitoly 5, 4 a 5 zkouška sporem z kapitoly 6 na větších mřížkách. Ovládání v kostce: klepnutí vybarví nebo vymaže pole, přepínač ■ / ✕ určí, co se kreslí, tažením prstu vyplníte úsek řady; myší levé tlačítko vybarví, pravé udělá křížek; na klávesnici šipky, mezerník vybarví, X udělá křížek, T zavolá nápovědu, Z a Y vrací a opakují tahy. Lupa dvěma prsty nebo kolečkem myši.
Pravidla, pojmy a historiezáklady
Mřížka je zpočátku prázdná. U každého řádku a nad každým sloupcem stojí čísla – legenda. Každé číslo udává délku jednoho souvislého úseku vybarvených polí, bloku. Bloky jsou v řadě ve stejném pořadí jako čísla v legendě a mezi dvěma bloky je vždy aspoň jedno prázdné pole. Úkolem je vybarvit pole tak, aby legendě odpovídal každý řádek i každý sloupec. Když se to podaří, z vybarvených polí vznikne obrázek. To je celé pravidlo; všechno ostatní v průvodci jsou jeho důsledky.
Malovaná křížovka je jako dálkové vybarvování podle čísel: nevíte, co kreslíte, dokud to nenakreslíte. A přece se nemusí nic hádat. Každá řada sama o sobě něco prozradí a co se dozvíte v řádku, pomůže ve sloupci, který ho kříží. Dobrá křížovka se dá vyřešit od prvního do posledního pole čistou úvahou.
+Teorie: pravidla přesně, pojmy a volnost, jak začít, historie a názvy
1.1Pravidla přesně
Mřížka má W sloupců a H řádků; každé pole je buď vybarvené, nebo prázdné. Řádek nebo sloupec se v průvodci jednotně nazývá řada. Ke každé řadě patří legenda – posloupnost kladných čísel b₁, b₂, …, bk. Řada odpovídá legendě, když její vybarvená pole tvoří právě k souvislých bloků, první dlouhý b₁, druhý b₂ atd., počítáno zleva doprava (u sloupce shora dolů). Protože bloky jsou souvislé a maximální, odděluje každé dva sousední bloky aspoň jedno prázdné pole – kdyby se dotýkaly, splynuly by v jeden delší blok. Prázdná řada má legendu 0.
Řešení je obrázek, ve kterém odpovídá legendě všech W + H řad zároveň. Dobře postavená křížovka má jediné řešení a dá se k němu dojít úvahou bez hádání. Obojí ověřuje počítač (kapitoly 11 a 12); ve všech křížovkách průvodce i 3D hry je to splněno.
Legenda neříká, kde bloky leží, jen jak jsou dlouhé a v jakém pořadí. Legenda 3 1 u řádku 10 polí tedy nedovoluje 1 3 (pořadí je dané) ani 4 (bloky musí být oddělené), ale připouští mnoho poloh: 3 vlevo a 1 vpravo, obojí uprostřed, a tak dále.
1.2Pojmy a volnost
Na papíře i v laboratořích se používají tři stavy pole: vybarvené (tmavé), křížek (víme, že je prázdné) a neznámé (bílé). Křížky jsou stejně důležité jako vybarvená pole: říkají, kam bloky nesmějí, a mnoho technik z nich vychází.
Nejdůležitější číslo každé řady je volnost. Bloky legendy s povinnými mezerami mezi nimi potřebují s + k − 1 polí, kde s = b₁ + … + bk je součet bloků a k jejich počet. Zbývající pole jsou volná:
Volnost říká, o kolik polí se může celá skupina bloků posunout. Při v = 0 je řada určená úplně; čím menší volnost, tím víc toho řada sama prozradí (kapitola 2). Řadu s legendou 0 lze rovnou celou zakřížkovat.
Legenda 3 1 2: s = 6, k = 3, volnost 10 − (6 + 2) = 2. Legenda 4 5: volnost 10 − (9 + 1) = 0, řada je hotová už ze zadání: čtyři vybarvená, křížek, pět vybarvených. Legenda 1: volnost 10 − 1 = 9, sama nic neprozradí.
1.3Jak začít
Začíná se řadami, které mají malou volnost – typicky s velkými čísly nebo s mnoha bloky. Z nich plyne první jisté vybarvení (kapitola 2). Každé nové pole patří zároveň řádku i sloupci, a tak se informace přelévá: co vybarvíte v řádku, je nová stopa pro sloupec. Luštitelé proto střídají řádky a sloupce a vracejí se k řadám, kde přibylo pole. Kdo si zvykne psát i křížky, postupuje rychleji a dělá méně chyb.
Mřížky od 10 × 10 výš mají silnější čáru po každých pěti polích. Pomáhá rychle počítat pozice: pole 13 je třetí pole za druhou silnou čarou. Na papíře si čísla legendy, která už v řadě stojí, škrtejte – laboratoř i 3D hra je šedí samy.
1.4Historie
Podle anglické Wikipedie vyhrála v roce 1987 japonská grafička Non Ishida v Tokiu soutěž v navrhování obrázků z oken: obrázky skládala z rozsvícených a zhasnutých oken mrakodrapu. To ji přivedlo k hádance, ve které se obrázek z mřížky odvozuje z čísel. Nezávisle na ní přišel s podobnou hádankou japonský autor hádanek Tetsuya Nishio, který ji uveřejnil v jiném časopise. Japonská Wikipedie uvádí, že první úlohy obou autorů vyšly v roce 1988. Ishida v roce 1988 vydala tři úlohy pod názvem „Window Art Puzzles“. Britský sběratel hlavolamů James Dalgety jí nabídl pomoc s vydáváním v zahraničí a z jejího jména a přípony -gram (jako v diagramu) složil název nonogram. Od roku 1990 je každý týden otiskovaly britské noviny The Sunday Telegraph; v roce 1993 vyšla v Japonsku první kniha nonogramů od Non Ishidy. Prameny se v drobnostech rozcházejí, například v tom, kdy přesně název nonogram vznikl.
Do Česka se hádanka podle české Wikipedie (heslo Zakódovaný obrázek) dostala v první polovině 90. let, kdy ji otiskoval časopis Panorama křížovek; v dalším desetiletí přibyly specializované tituly, mnohé ze Slovenska, odkud podle téhož zdroje pochází i název malované křížovky. Tyto údaje se nám nepodařilo ověřit v nezávislém prameni, proto je uvádíme jen s odkazem na zdroj. Užívají se i názvy japonská křížovka, kódovaný nebo zakódovaný obrázek. V Británii vyhlásily The Sunday Telegraph v roce 1998 soutěž o nový název a vybrán byl griddlers; v angličtině se setkáte i s paint by numbers nebo picture logic.
1.5Podoby hádanky
Klasická křížovka je černobílá a obdélníková, od 5 × 5 pro děti přes časopisecké 15 × 15 a 20 × 20 až po plakáty s tisíci poli. Barevné křížovky mají bloky několika barev a legendu s barevnými čísly; mezi bloky různých barev mezera být nemusí (kapitola 7). Existují i varianty na šestiúhelníkové mřížce nebo s trojúhelníkovými poli; průvodce se drží klasické čtvercové.
1.6Proč jediné řešení
Legenda je stručný popis obrázku, ale ne vždy jednoznačný. Nejjednodušší protipříklad: mřížka 2 × 2 s legendou 1 u všech řad. Vyhovuje jí vybarvení hlavní diagonály i vedlejší diagonály – dvě řešení. Takovou křížovku nejde dořešit úvahou, jen tipnout. Proto autoři jednoznačnost kontrolují (kapitoly 8 a 12) a jen asi tři čtvrtiny náhodných obrázků 5 × 5 ji splňují (kapitola 9).
- Legenda = délky bloků v pořadí; mezi bloky je vždy aspoň jedno prázdné pole; legenda 0 = prázdná řada.
- Volnost v = n − (s + k − 1) říká, o kolik polí se mohou bloky posunout. Malá volnost = hodně jistých polí.
- Hádanku vymysleli koncem 80. let v Japonsku Non Ishida a nezávisle Tetsuya Nishio; jméno nonogram vzniklo v Británii.
Překryv a hotová řadazáklady
Představte si bloky řady jako korálky na niti, které jdou posouvat jen tak, aby zůstaly v pořadí a mezi sousedy byla mezera. Natlačte je všechny doleva, pak všechny doprava. Pole, které blok pokrývá v obou krajních polohách, pokrývá v každé poloze – je jistě vybarvené. To je Překryv, technika, kterou začíná skoro každá křížovka. Druhá technika je ještě jednodušší: když už v řadě stojí všechny bloky, zbytek jsou křížky. To je Hotová řada. Obě patří do úrovně 1.
Řada 10 polí s legendou 7: blok může začínat na polích 1 až 4. Ať začne kdekoli, pole 4 až 7 pokryje vždy. Čtyři pole vybarvená bez jediného dalšího údaje – jen z legendy a délky řady.
+Teorie: krajní polohy, délka překryvu, překryv s křížky, hotová řada
2.1Krajní polohy
Řada má n polí a legendu b₁, …, bk. Nejlevější poloha klade první blok na začátek řady a každý další hned za předchozí s jednou mezerou: blok j začíná na poli
Nejpravější poloha je zrcadlová: poslední blok končí na poli n, předchozí o mezeru dřív. V prázdné řadě se nejpravější poloha od nejlevější liší přesně o volnost: Rj = Lj + v pro každý blok. Klíčové pozorování: v každém umístění bloků začíná blok j někde mezi Lj a Rj. Kdyby začínal dřív než Lj, nevešly by se před něj předchozí bloky s mezerami; kdyby začínal později než Rj, nevešly by se za něj následující.
2.2Délka překryvu
Blok j začínající na poli Lj končí na Lj + bj − 1; blok začínající na Rj = Lj + v zabírá pole od Lj + v. Společná pole jsou od Lj + v do Lj + bj − 1, a ta pokrývá blok v každé poloze mezi tím. Překryv má tedy
Překryv má jen blok delší než volnost. Odtud rychlé pravidlo: spočítejte volnost a porovnejte ji s každým číslem legendy. Řada 15 polí s legendou 6 5 má volnost 15 − 12 = 3, blok 6 dá 3 pole, blok 5 dá 2 pole.
| Legenda | Součet s | Volnost v | Překryv vybarví | Umístění |
|---|---|---|---|---|
| 10 | 10 | 0 | 10 | 1 |
| 9 | 9 | 1 | 8 | 2 |
| 8 | 8 | 2 | 6 | 3 |
| 7 | 7 | 3 | 4 | 4 |
| 6 | 6 | 4 | 2 | 5 |
| 5 | 5 | 5 | 0 | 6 |
| 4 4 | 8 | 1 | 6 | 3 |
| 5 3 | 8 | 1 | 6 | 3 |
| 3 4 | 7 | 2 | 3 | 6 |
| 3 3 2 | 8 | 0 | 8 | 1 |
| 2 2 2 | 6 | 2 | 0 | 10 |
| 1 1 1 1 1 | 5 | 1 | 0 | 6 |
Legenda 1 1 1 1 1 má volnost jen 1, a přesto překryv nevybarví nic: každý blok je kratší nebo stejně dlouhý jako volnost. Malá volnost pomáhá jen dlouhým blokům. Naopak u volnosti 0 (legenda 3 3 2 v 10 polích) je řada určená celá: překryv vybarví všechny bloky a mezery doplní hotová řada.
2.3Překryv s křížky
Uprostřed řešení už řady obsahují křížky z křížících se řad. Blok nesmí ležet na křížku, takže krajní polohy se posunou: nejlevější poloha natlačí blok doleva jen tam, kam se mezi křížky vejde. Překryv se počítá stejně, jen z takto posunutých poloh. Křížek tak funguje jako okraj řady.
Mezi křížky je úsek 4–7 dlouhý přesně 4 pole, kratší úseky 1–2 a 9–10 blok nepojmou. Nejlevější i nejpravější poloha je tedy 4–7 a překryv vybarví všechna čtyři pole. Co se stane s poli 1, 2, 9 a 10, řeší technika Nedosažitelná pole v kapitole 3.
V tomto průvodci i ve 3D hře se pro Překryv berou v úvahu jen křížky; krajní polohy, které respektují i už vybarvená pole, jsou technikou Okraj z kapitoly 3. Rozdělení odpovídá tomu, jak lidé techniky obvykle objevují: nejdřív „kam se blok vejde“, potom „co ho drží na místě“.
2.4Hotová řada
Když je v řadě vybarveno tolik polí, kolik je součet legendy, jsou všechna zbylá neznámá pole prázdná. Nezáleží ani na tom, jestli vybarvená pole už tvoří správné bloky – víc vybarvených polí řada mít nemůže. Zvláštní případ je legenda 0: celá řada se zakřížkuje hned na začátku. Hotová řada je nejlevnější technika a ve 3D hře ji můžete nechat dělat automaticky.
Po každém zápisu se podívejte na obě řady, které pole kříží: nestala se některá z nich hotovou? Zkušení luštitelé to dělají automaticky a ušetří tím spoustu hledání. Na papíře pomáhá škrtat čísla legendy, jakmile blok stojí.
2.5Kolik toho úroveň 1 zvládne
Překryv a Hotová řada stačí na překvapivě mnoho křížovek. Z 24 vlastních motivů průvodce jich 15 vyřeší řešitel jen těmito dvěma technikami, od Srdce 5 × 5 (10 kroků) po Maják 20 × 20 (56 kroků). Křížovky pro děti a lehké časopisecké křížovky bývají právě takové. Na náhodných obrázcích je to jinak: u náhodných obrázků 10 × 10 s jediným řešením stačila úroveň 1 jen asi na 6 % (kapitola 9) – dobré obrázky mají dlouhé bloky a malé volnosti.
- Každý blok leží v každém umístění mezi svou nejlevější a nejpravější polohou.
- Překryv bloku má délku max(0, b − v): vybarvuje jen blok delší než volnost.
- Hotová řada: vybarveno = součet legendy → zbytek křížky; legenda 0 → celá řada křížky.
Okraj a nedosažitelná polezáklady
Překryv počítá jen s délkou řady a křížky. Jakmile ale v řadě stojí vybarvené pole, blok, kterému patří, se nemůže vzdálit: musí ho pokrýt. Vybarvené pole u kraje tak „přitlačí“ blok ke kraji a z krajních poloh plynou nová vybarvená pole i křížky – to je Okraj. Druhá technika úrovně 2 se dívá opačně: pole, do kterých nedosáhne žádný blok, a mezery mezi křížky, do kterých se žádný blok nevejde, jsou prázdné. To jsou Nedosažitelná pole.
Řada 12 polí, legenda 4 2, vybarvené je pole 2. Čtyřka musí pole 2 pokrýt, a začíná proto na poli 1, nebo 2. V obou případech pokrývá pole 2, 3 a 4. Jedno vybarvené pole u kraje dalo dvě nová.
+Teorie: okraj u kraje i uprostřed, krajní polohy se známými poli, dosah bloku, krátké mezery
3.1Okraj u kraje řady
Nejčastější situace: vybarvené pole leží blízko začátku řady, ve vzdálenosti menší než délka prvního bloku. Pak mu může patřit jen první blok (každý další by před sebou potřeboval místo pro první blok a mezeru) a první blok ho musí pokrýt. Začíná tedy nejdřív na poli 1 a nejpozději na tomto vybarveném poli. Všechna pole mezi vybarveným polem a koncem bloku v nejlevější poloze jsou vybarvená.
Navíc: když je vybarvené přímo pole 1, je první blok celý určený (pole 1 až b₁) a pole b₁ + 1 je křížek. Úplně stejně funguje okraj u křížku: křížek je pro blok „začátek řady“.
3.2Krajní polohy se známými poli
Obecně Okraj počítá nejlevější a nejpravější polohu bloků, které sedí se všemi známými poli: žádný blok neleží na křížku a každé vybarvené pole je pokryté nějakým blokem. Nejlevější polohu najdete takto: natlačte bloky doleva; zůstane-li některé vybarvené pole nepokryté, posuňte doprava poslední blok, který ho může pokrýt, a ostatní za ním podle potřeby. Z obou krajních poloh pak platí totéž co u překryvu – pole pokrytá blokem v obou polohách jsou vybarvená – a navíc: pole, které nepokrývá žádný blok v žádné poloze mezi krajními, je křížek.
Blok 3 musí pokrýt pole 5: začíná na poli 3, 4, nebo 5 a dosáhne nejvýš na pole 3 až 7. Pole 1, 8, 9 a 10 jsou křížky – to je Okraj. Samotná Nedosažitelná pole (bez vybarveného pole) by našla jen pole 1, protože úsek před křížkem je na trojku krátký. Vyzkoušejte předvolbu „3“ v laboratoři.
Nejčastější chyba: přiřadit vybarvené pole špatnému bloku. Pole 5 v řadě s legendou 1 3 nemusí patřit trojce – může to být jednička, a trojka pak leží vpravo od něj. Okraj z krajních poloh tohle hlídá sám; kdo počítá z hlavy, musí si vždy položit otázku „kterému bloku to pole může patřit?“ (kapitola 4).
3.3Dosah bloku a nedosažitelná pole
Dosah bloku j jsou pole od začátku jeho nejlevější polohy po konec nejpravější. Pole mimo dosah všech bloků vybarvené být nemůže. Technika Nedosažitelná pole k tomu přidává ještě jedno pravidlo: úsek neznámých polí mezi dvěma křížky (nebo křížkem a krajem), který je kratší než každý blok, jenž do něj dosáhne, je celý prázdný. Typicky jde o krátké mezery mezi křížky u řad s dlouhými bloky.
Když se v řadě objeví nový křížek, podívejte se na úseky po obou stranách: vejde se do nich ještě nějaký blok? V pozdní fázi řešení tak padá mnoho křížků najednou a rychle se otevírají křížící se řady.
3.4Pořadí technik v jedné řadě
| Technika | Úroveň | Bere v úvahu | Dává | Kapitola |
|---|---|---|---|---|
| Hotová řada | 1 | počet vybarvených polí | křížky | 2 |
| Překryv | 1 | křížky | vybarvená pole | 2 |
| Nedosažitelná pole | 2 | křížky | křížky | 3 |
| Okraj | 2 | křížky i vybarvená pole | vybarvená pole i křížky | 3 |
| Všechna umístění | 3 | všechno, každé umístění zvlášť | všechno, co z řady plyne | 5 |
Každá technika v tabulce je speciálním případem té poslední: cokoli najde Překryv, Okraj nebo Nedosažitelná pole, najde i úplný rozbor všech umístění. Smysl odstupňování je lidský – jednodušší techniky jdou dělat z hlavy a rychle, Všechna umístění vyžadují systematické vypsání.
- Vybarvené pole drží svůj blok: krajní polohy, které ho musí pokrýt, dají nová vybarvená pole i křížky (Okraj).
- Pole mimo dosah všech bloků a mezery kratší než bloky, které do nich dosáhnou, jsou křížky (Nedosažitelná pole).
- Obě techniky jsou úroveň 2; jsou to speciální případy úplného rozboru řady z kapitoly 5.
Komu patří vybarvený úsekzáklady
Uprostřed řešení bývá v řadě několik vybarvených úseků a otázka zní: který z nich je který blok legendy? Kdo umí úseky přiřadit, ví, kde bloky začínají a končí, kde je musí uzavřít křížkem a kde je spojit. Přiřazování není samostatná technika řešitele – je to způsob uvažování, kterým člověk provádí Okraj z kapitoly 3 a v těžších případech Všechna umístění z kapitoly 5. Tady se ho naučíte krok za krokem.
Legenda 1 3 1, vybarvený úsek tří polí uprostřed. Jediný blok, který je tak dlouhý, je trojka – a protože už je celá, pole před ní i za ní jsou křížky. Dva křížky z jedné otázky: „komu ten úsek patří?“
+Teorie: úseky a bloky, tři testy přiřazení, uzavírání a spojování, spolupráce řádku a sloupce
4.1Úseky a bloky
Úsek je souvislá skupina vybarvených polí, kterou v řadě vidíme; blok je úsek z řešení, jehož délku zná legenda. Každý úsek je částí právě jednoho bloku, ale jeden blok může zatím tvořit několik úseků oddělených neznámými poli. Přiřadit úsek znamená zjistit, kterému číslu legendy patří.
4.2Tři testy
Blok j může pokrýt úsek od pole a do pole e, jen když projde třemi testy:
- Délka: bj ≥ e − a + 1. Krátký blok dlouhý úsek nepokryje.
- Místo vlevo: bloky 1 až j − 1 se s mezerami vejdou před začátek bloku j, a to mimo křížky a tak, aby pokryly všechna vybarvená pole vlevo.
- Místo vpravo: totéž pro bloky j + 1 až k za koncem bloku j.
Testy vlevo a vpravo se dají zjednodušit pomocí krajních poloh z kapitoly 3: blok j může pokrýt úsek jen tehdy, když úsek leží v jeho dosahu, tedy mezi začátkem nejlevější a koncem nejpravější polohy bloku j. Úplnou odpověď dává laboratoř; z hlavy obvykle stačí délka a hrubý odhad místa.
Délka: úsek 2 může být dvojka nebo pětka. Místo: kdyby to byla dvojka, musely by se pětka a jednička vejít do polí 9–12, ale potřebují 5 + 1 + 1 = 7 polí. Úsek tedy patří pětce. Ta začíná nejdřív na poli 4 (před ní dvojka a mezera) a nejpozději na poli 6, takže pole 8 je vybarvené vždy.
4.3Uzavírání a prodlužování
Když úsek patří jedinému bloku délky b, blok začíná nejdřív na poli e − b + 1 a nejpozději na poli a. Odtud dvě rutinní pravidla:
- Uzavření: je-li úsek stejně dlouhý jako každý blok, který ho může pokrýt, je blok hotový a pole hned před ním a za ním jsou křížky.
- Prodloužení od křížku: leží-li úsek u křížku nebo kraje, blok pokračuje na druhou stranu až do své délky.
Uzavřít úsek jde jen tehdy, když jsou stejně dlouhé všechny bloky, které ho mohou pokrýt. Úsek délky 2 v řadě s legendou 2 3 nejde uzavřít, dokud nevíte, že nepatří trojce – mohl by to být její začátek.
4.4Spojit, nebo oddělit?
Dva úseky oddělené jedním neznámým polem mohou patřit jednomu bloku (pak je pole mezi nimi vybarvené), nebo dvěma různým (pak je to mezera). Když by spojením vznikl úsek delší než nejdelší blok, který může oba úseky pokrýt, je pole mezi nimi křížek. Naopak když úseky musí patřit stejnému bloku – například proto, že na dva bloky není mezi nimi a kraji místo – pole mezi nimi se vybarví.
Přiřazujte zvenku dovnitř. Krajní úseky mívají nejméně kandidátů: úplně vlevo může stát jen některý z prvních bloků, úplně vpravo některý z posledních. Jakmile víte, komu patří krajní úseky, kandidáti vnitřních úseků se zúží sami.
4.5Řádek a sloupec spolupracují
Úvahy o jedné řadě by nestačily, kdyby se řady nekřížily. Každé pole zapsané v řádku je zároveň stopou pro sloupec, ve kterém leží, a naopak. Řešení křížovky je proto střídání pohledů: řádek dá pole sloupci, sloupec dá pole dalším řádkům. Lidský řešitel v laboratořích i ve 3D hře v každém kroku prohlédne všechny řady a vybere tu, kde stačí nejjednodušší technika.
- Úsek patří bloku jen tehdy, když blok je dost dlouhý a ostatní bloky se vejdou před něj i za něj.
- Úsek stejně dlouhý jako všechny jeho možné bloky se uzavře křížky; spojení delší než možný blok znamená křížek mezi úseky.
- Přiřazování je lidský způsob, jak dělat Okraj a Všechna umístění; řádky a sloupce si stopy předávají.
Všechna umístěnípokročilí
Překryv, Okraj a Nedosažitelná pole se dívají jen na dvě krajní polohy bloků. Někdy to nestačí: pole leží v dosahu bloku, a přesto je ve skutečnosti vždy prázdné. Technika Všechna umístění projde každé rozmístění bloků, které sedí se známými poli, a zapíše pole, která vycházejí ve všech stejně. Je to nejsilnější úvaha o jedné řadě: co nenajde ona, z řady samotné odvodit nejde. Patří do úrovně 3.
Řada 8 polí, legenda 1 2, vybarvené pole 3. Krajní polohy nic neřeknou. Ale vypište možnosti: pole 3 je buď jednička, nebo začátek dvojky (a jednička pak stojí na poli 1). Ve všech čtyřech umístěních je pole 2 prázdné.
+Teorie: průnik umístění, úplnost, počet umístění, ruční postup, kdy je technika potřeba
5.1Průnik všech umístění
Umístění je volba začátků všech bloků, která dodržuje pořadí a mezery. Říkáme, že sedí se známými poli, když žádný blok neleží na křížku a každé vybarvené pole leží v některém bloku. Správné řešení řady je jedno z nich, nevíme které. Pole, které je vybarvené ve všech takových umístěních, je proto vybarvené i v řešení; pole prázdné ve všech je křížek.
Platí i opak, a to dělá techniku výjimečnou: když je pole v jednom umístění vybarvené a v jiném prázdné, nedá se o něm z této řady samotné nic říct – obě možnosti jsou s řadou v souladu. Všechna umístění tedy najdou úplně všechno, co z jedné řady plyne. Proto se jí v informatice říká úplný řešič řady a Překryv, Okraj, Nedosažitelná pole i Hotová řada jsou její zvláštní případy.
5.2Kolik umístění je
V prázdné řadě délky n s k bloky a součtem s je umístění
| Délka n | Legenda | Volnost v | Umístění |
|---|---|---|---|
| 10 | 3 2 | 4 | 15 |
| 15 | 3 2 4 | 4 | 35 |
| 20 | 5 3 4 2 | 3 | 35 |
| 25 | 3 3 3 3 | 10 | 1 001 |
| 20 | 1 1 1 1 1 | 11 | 4 368 |
| 30 | 4 6 2 5 | 10 | 1 001 |
Ruční vypsání má smysl jen tam, kde je umístění málo – a uprostřed řešení, kdy známá pole většinu možností vyřadí, tomu tak bývá. Řada 10 polí s legendou 1 1 3 má v prázdném stavu C(6, 3) = 20 umístění; s jediným vybarveným polem 3 už jen 7.
5.3Ruční postup
- Rozdělte podle hypotéz. Místo vypisování všech umístění se zeptejte: kterému bloku patří vybarvené pole? Každá odpověď je jedna skupina umístění. V příkladu z úvodu jsou to dvě hypotézy: „pole 3 je jednička“ a „pole 3 je začátek dvojky“.
- V každé hypotéze použijte jednodušší techniky. Uvnitř hypotézy bývá řada skoro určená. Zapište si, co vychází.
- Zapište společné. Co platí ve všech hypotézách, platí vždy. Co se liší, nechte otevřené.
Pole 7 může být první, druhá i třetí jednička – Okraj z krajních poloh nic neurčí, protože druhá jednička může ležet na polích 4 až 7 a třetí na 7 až 9. Ať je ale pole 7 kterákoli jednička, je to celý blok a jeho sousedé 6 a 8 jsou prázdní. Všechna umístění (je jich 7) to potvrdí. Člověk to vidí přes přiřazení z kapitoly 4: všechny bloky, které pole mohou pokrýt, mají délku 1.
5.4Kdy je technika potřeba
Typické situace, kdy jednodušší techniky selžou a Všechna umístění uspějí:
- Krátké bloky stejné délky: vybarvené pole může patřit několika blokům, ale všechny mají stejnou délku – blok je hotový a uzavře se.
- Dvě skupiny umístění: pole je buď začátkem dlouhého bloku, nebo samostatným krátkým blokem; v obou případech je stejné pole vedle něj prázdné.
- Mezery mezi úseky: dva úseky nemohou patřit jednomu bloku, ani dvěma blokům s jinou mezerou, než je jedno konkrétní pole.
Než se pustíte do vypisování, zkuste všechny úseky přiřadit (kapitola 4). V praxi se většina kroků úrovně 3 dá najít otázkou „jsou všechny bloky, které tohle pole mohou pokrýt, stejně dlouhé?“
Všechna umístění pracují s jedinou řadou. Když ani ona nic nenajde ve žádné řadě, křížovka se zasekla a na řadu přichází zkouška sporem z kapitoly 6 – úvaha přes několik řad najednou.
- Pole stejné ve všech umístěních, která sedí se známými poli, je jisté; jinak ho z řady samotné určit nejde.
- Všechna umístění = úplný řešič řady; ostatní techniky řady jsou jeho speciální případy.
- Ručně: rozdělte podle hypotéz „kterému bloku pole patří“ a zapište, co platí ve všech.
Zkouška sporempokročilí
Někdy žádná řada sama nic neprozradí – ani úplným rozborem všech umístění. Křížovka se zasekla. Pak přichází Zkouška sporem: vyberte jedno neznámé pole, předpokládejte, že je vybarvené (nebo prázdné), a řešte dál s tímto předpokladem. Když se dojde ke sporu – v některé řadě se bloky už nedají umístit –, byl předpoklad chybný a platí opak. To není hádání, ale důkaz. Technika patří do úrovně 4.
Deštník: v rozích stříšky zbývá osm neznámých polí a každá řada, která jimi prochází, má dvě možnosti. Předpoklad „pole ř3s1 je vybarvené“ ale za pět řad vede k řádku, kde by se dvě jedničky dotýkaly. Pole ř3s1 je tedy prázdné – a zbytek už dořeší obyčejné techniky.
+Teorie: zaseknutí, zkouška krok za krokem, proč to není hádání, kde zkoušet, dvojí zkouška, hranice
6.1Kdy se řady zaseknou
Křížovka je zaseknutá, když žádná řada – ani úplným rozborem všech umístění – nedává nové pole. Každá řada má pak aspoň dvě umístění, která sedí se známými poli, a teprve jejich vzájemná kombinace rozhoduje. V Deštníku je to dobře vidět: 3. řádek (legenda 8) má vybarvená pole 3–8 a osmička může ležet na 1–8, 2–9, nebo 3–10; 5. řádek (legenda 1 1 1 1) má jedničky na polích 4 a 7 a dvě další buď na poli 1, nebo 2, a buď na 9, nebo 10; sloupce 1, 2, 9 a 10 mají legendu 2 a dvojka v nich může ležet o pole výš, nebo níž. Každá řada zvlášť „má pravdu“ v obou možnostech.
6.2Zkouška krok za krokem
- Vyberte pole a předpoklad. Na papíře si předpoklad i všechno, co z něj odvodíte, pište jinou barvou nebo tečkou místo plného vybarvení.
- Šiřte. Řešte řady, ve kterých přibylo pole – běžnými technikami, dokud něco přibývá.
- Spor? Když některá řada nemá žádné umístění (bloky se nevejdou, dotýkají se, chybí nebo přebývají), předpoklad byl chybný. Smažte všechno odvozené a zapište opak předpokladu – ten je dokázaný.
- Bez sporu? Pak jste se nedozvěděli nic. Smažte zkoušku a zkuste opačnou hodnotu nebo jiné pole.
3. řádek: osmička začíná na poli 1, takže ř3s2 je vybarvené a ř3s9, ř3s10 jsou křížky. 1. sloupec (legenda 2): dvojka je ř3s1–ř4s1, takže ř5s1 je křížek; stejně 2. sloupec dá křížek ř5s2. 9. sloupec (legenda 2): pole ř3s9 je prázdné, dvojka musí být ř4s9–ř5s9; stejně 10. sloupec dá ř5s10. 5. řádek teď má vybarvená pole 4, 7, 9 a 10 – devítka a desítka se dotýkají, ale legenda je 1 1 1 1. Spor. Pole ř3s1 je prázdné; pak 7 kroků technik řad dořeší celý obrázek.
6.3Proč to není hádání
Zkouška sporem je důkaz sporem, jaký znáte z matematiky (viz průvodce Logika a kritické myšlení): z předpokladu P plyne nemožnost, tedy P neplatí. Každý krok šíření je přitom stejně jistý jako běžné techniky – jen platí „za předpokladu P“. Hádání je něco jiného: zapsat hodnotu, protože se zdá pravděpodobná, nebo proto, že z ní zatím žádný spor neplyne.
„Zkoušel jsem vybarvené a nic se nestalo, tak to nechám vybarvené“ je nejčastější chyba. Bez sporu se nedokázalo nic: předpoklad může být správný, ale také může spor čekat o deset řad dál. A po sporu nezapomeňte smazat všechno odvozené z chybného předpokladu – zapisuje se jen opak předpokladu (a to, co z něj potom plyne).
6.4Kde zkoušet
Dobrá pole pro zkoušku leží v řadách, kde je už hodně známých polí: předpoklad v nich rychle „chytne“ a šíření je krátké. Řešitel průvodce řadí kandidáty právě podle počtu známých polí v řádku a sloupci daného pole. Lidé se navíc dívají na místa, kde se rozhodují dvě možnosti: konec bloku, který se může posunout o jedno pole, roh, kde se setkávají dvě nejisté řady. Zkoušet pole uprostřed prázdné oblasti se nevyplatí – šíření nic nepřinese.
6.5Dvojí zkouška
Někdy nevede ke sporu ani jedna hodnota pole, ale obě větve shodně určí jiné pole. Pak je to pole jisté: v řešení má zkoumané pole jednu z obou hodnot, a ať je to kterákoli, druhé pole vychází stejně. Je to stejný princip jako Všechna umístění, jen o úroveň výš – „průnik“ dvou větví místo průniku umístění. Řešitel průvodce dvojí zkoušku nepoužívá; na papíře je ale užitečná.
6.6Hranice techniky
Úroveň 4 v průvodci znamená zkoušku s jedním polem a se šířením úplným řešičem řad. Kdyby ani to nestačilo, musely by se předpoklady vnořovat (předpoklad uvnitř předpokladu) – to už je systematické prohledávání, jaké dělá počítač (kapitola 11), a pro člověka spíš trápení než zábava. Takové křížovky jsou podle průvodce „mimo škálu“. V simulacích z kapitoly 9 (náhodné obrázky až do 20 × 20) se mezi obrázky s jediným řešením nenašel žádný, na který by zkouška s jedním polem nestačila; dobře postavené křížovky do 4. úrovně vejdou.
Začínejte předpokladem, který má víc důsledků. V řadě s dlouhým blokem dá „vybarvené“ často celý blok najednou, kdežto „prázdné“ jen posune hranici. Spor se pak objeví dřív.
- Zaseknutí: žádná řada sama nic nedá. Zkouška: předpoklad → šíření → spor → platí opak.
- Bez sporu se nedokázalo nic; po sporu se odvozená pole mažou.
- Zkoušejte pole v řadách s mnoha známými poli; obě větve se shodným závěrem také dávají jisté pole.
Velké a barevné křížovkypokročilí
Na mřížce 20 × 20 je 40 řad a 400 polí. Techniky jsou stejné jako na malé křížovce, ale přibývá otázka pořadí: kterou řadu prohlédnout teď, aby se práce neztrácela v řadách, kde se nic nezměnilo? A jak najít chybu, která se schovala před sto kroky? Druhá polovina kapitoly patří barevným křížovkám, ve kterých mají bloky barvy a mezi bloky různých barev mezera být nemusí.
Maják 20 × 20 vyřeší řešitel jen překryvem a hotovou řadou za 56 kroků. Kolik řad přitom musí prohlédnout, záleží na strategii: nejhorší ze tří strategií v laboratoři prohlédne asi o čtvrtinu víc řad než nejlepší.
+Teorie: kde začít, strategie výběru řad, hledání chyb, pravidla a techniky barevných křížovek
7.1Kde začít na velké mřížce
Volnost řad se na velké mřížce liší víc než na malé. Maják 20 × 20 má 40 řad; jen 7 z nich má volnost nejvýš 2 (tři dokonce 0) a většina má volnost 13 až 17. Řady s malou volností dají překryvem hodně polí hned, ostatní čekají, až jim křížící řady dodají stopy. Prvním krokem na velké křížovce je proto projít legendy a spočítat volnost – stačí odhad „součet čísel + počet mezer ve srovnání s délkou“.
| Křížovka | Řad | Fronta změněných řad | Procházení dokola | Nejméně umístění |
|---|---|---|---|---|
| Maják 20 × 20 | 40 | 73 | 69 | 58 |
| Hrad 15 × 15 | 30 | 41 | 41 | 29 |
| Kohout 15 × 15 | 30 | 112 | 103 | 99 |
| Hvězda 10 × 10 | 20 | 58 | 87 | 80 |
7.2Strategie výběru řad
Fronta změněných řad je přirozená pro počítač: nejdřív každá řada jednou, pak jen ty, kde přibylo pole (kapitola 11). Procházení dokola je to, co lidé dělají, když nemají plán: řádky shora dolů, sloupce zleva doprava, znovu. Nejméně umístění napodobuje zkušeného luštitele, který se dívá tam, kde je řada „skoro hotová“. Tabulka ukazuje, že žádná strategie není nejlepší vždy: na Majáku, Hradu i Kohoutovi vede výběr nejsnazší řady, na Hvězdě fronta. Pro člověka platí jednoduché pravidlo: po každém zápisu se podívejte na řadu, která nové pole kříží.
7.3Hledání chyb
Chyba na velké křížovce se obvykle projeví až pozdě – v řadě, kde se bloky najednou nevejdou nebo kde je vybarveno víc polí, než je součet legendy. Pomáhá:
- Kontrola po každé hotové řadě: sedí počet bloků i jejich délky? Laboratoře i 3D hra šedí legendu, jakmile bloky sedí.
- Tužka a guma, nebo tahy zpět: ve 3D hře jdou tahy vracet a kontrolu chyb lze zapnout hned, nebo až na konci.
- Hledat poslední jistý stav: chyba je skoro vždy v kroku, který „vypadal jasně“, ale byl udělaný z hlavy bez kontroly přiřazení bloků (kapitola 4).
Na papíře si u dlouhých řad dělejte drobné tečky po pěti polích i uvnitř mřížky, nebo počítejte pozice od silné čáry. Většina chyb na velkých křížovkách je o jedno pole – blok posunutý vedle.
7.4Barevné křížovky: pravidla
V barevné křížovce má každé číslo legendy barvu a každé pole je buď prázdné, nebo má jednu z barev. Blok je souvislý úsek polí stejné barvy. Mezi dvěma sousedními bloky stejné barvy musí být aspoň jedno prázdné pole, mezi bloky různých barev mezera být nemusí. Anglická Wikipedie to formuluje tak, že dva různobarevné bloky mezi sebou mezeru mít mohou, ale nemusí. Volnost se proto počítá s menším počtem povinných mezer:
7.5Techniky v barevných křížovkách
Překryv, Okraj i Všechna umístění fungují stejně, jen s barevnými mezerami a s tím, že pole má víc možných hodnot. Silná nová úvaha je barevný průnik: když řádek dovoluje v poli jen oranžovou nebo prázdné a sloupec jen modrou nebo prázdné, je pole prázdné. Proto se na papíře vyplatí psát do polí drobné značky možných barev. Barevné křížovky bývají při stejné velikosti snazší, protože barva sama nese informaci; obtížnost se dohání větší mřížkou.
Musí mít mezeru dva oranžové bloky, mezi kterými v legendě stojí modrý? Ne – povinná mezera se týká jen sousedních bloků v legendě. Legenda 2 oranžová, 1 modrá, 2 oranžová dovoluje řadu „oranž, oranž, modrá, oranž, oranž“ bez jediné mezery.
- Na velké mřížce nejdřív spočítejte volnost; začněte řadami s nejmenší.
- Po zápisu se dívejte na řady, které nové pole kříží; žádná strategie není nejlepší vždy.
- Barevné křížovky: mezera jen mezi sousedními bloky stejné barvy, v = n − (s + g); barva pole se dá vyloučit průnikem řádku a sloupce.
Dobrý obrázekpokročilí
Malovaná křížovka je zároveň hádanka i obrázek. Dobrý obrázek je po vyřešení na první pohled poznat, a přitom má legendu, ze které jde vyřešit jednoznačně a bez hádání. Obě přání si občas odporují: jemné detaily, tenké čáry a osamělá pole dělají obrázek hezčím, ale legendu nejednoznačnou. Kapitola ukazuje, jak převést tvar do mřížky, proč vznikají obrázky s více řešeními a jak je opravit.
Obličej 12 × 12 z laboratoře vypadá nevinně – kruh, dvě oči, úsměv. Jeho legendě ale odpovídají dva různé obrázky, které se liší v šesti polích. Stačí přidat jediné pole, ř3s2, a křížovka má jediné řešení.
+Teorie: čitelnost, rastrování, proč vzniká víc řešení, oprava, hustota, vlastní motivy
8.1Co dělá obrázek čitelným
- Silueta. Plný tvar s výrazným obrysem (konvička, kotva, kočka) je poznat i v malém rozlišení. Kresba z tenkých čar se v mřížce rozpadá.
- Jeden motiv a kontrast. Obrázek by měl zabírat většinu mřížky a jasně se odlišovat od pozadí.
- Rozlišení podle publika. Pro děti 5 × 5 až 8 × 8 s jednoduchým tvarem, pro běžné luštitele 10 × 10 až 20 × 20, pro vytrvalce 25 × 25 a víc.
- Charakteristický detail. Ucho, komín, plachta: jedno dvě pole, podle kterých obrázek člověk pozná. Detaily ale bývají místem, kde vzniká nejednoznačnost.
8.2Rastrování
Převod spojitého tvaru do mřížky se jmenuje rastrování. Nejjednodušší pravidlo – vybarvit pole, které tvar pokrývá aspoň z poloviny – dá rozumný základ, ale autor ho skoro vždy ručně upraví: zarovná obrys, zesílí tenké části, odstraní osamělá pole. Při malém rozlišení se tvar nevyhnutelně zkresluje; kruh 5 × 5 je kosočtverec a hvězda 5 × 5 má jen 7 polí.
8.3Proč vzniká víc řešení
Nejednoznačnost bývá místní: malá skupina polí, kterou jde „přepnout“ tak, že se žádná legenda nezmění. Nejčastěji jsou to čtyři pole v rozích obdélníku, kde jsou vybarvená dvě protilehlá a dvě protilehlá prázdná, a v řádcích i sloupcích jde o samostatné krátké bloky – záměna je pak nepozorovatelná. Nebezpečné jsou:
- osamělá pole a úhlopříčky – řady s legendou 1 mají mnoho umístění a jdou snadno prohazovat; extrémem je obrázek se samými jedničkami, kterému odpovídá n! obrázků;
- šachovnicové textury – srst, listí, vlny z jednotlivých polí;
- souměrné detaily – oči, okna, knoflíky ve dvojicích, kde jde zaměnit levý a pravý.
8.4Oprava nejednoznačnosti
Když kontrola najde dvě řešení, rozdílová pole ukazují, kde zasáhnout. Většinou stačí jedno pole přidat nebo ubrat tak, aby se záměna rozbila: spojit osamělé pole s blokem, rozšířit čáru, posunout detail. Po každé úpravě je nutné ověřit znovu – oprava může vytvořit jinou nejednoznačnost jinde, nebo udělat z lehké křížovky těžkou. Laboratoř to dělá při každém klepnutí.
Jediné řešení neznamená snadné řešení. Deštník i Kotva mají jediné řešení, ale potřebují zkoušku sporem (úroveň 4). A obráceně: negativ obrázku (vybarvené a prázdné prohozené) má jinou legendu a nemusí být jednoznačný. Z 24 motivů průvodce mají aspoň dvě řešení negativy tří: Plachetnice, Kočky a Zajíce; negativ Deštníku je naopak jen úroveň 1.
8.5Hustota a jednoznačnost
| Hustota p | Jediné řešení | 95% interval | Úroveň 1 | Úroveň 2 | Úroveň 3 | Úroveň 4 |
|---|---|---|---|---|---|---|
| 0,3 | 2,0 % | 1,6–2,5 % | 0 | 26 | 11 | 43 |
| 0,4 | 16,9 % | 15,8–18,1 % | 6 | 432 | 70 | 168 |
| 0,5 | 53,6 % | 52,1–55,2 % | 131 | 1 812 | 71 | 132 |
| 0,6 | 83,7 % | 82,5–84,8 % | 1 333 | 1 992 | 8 | 14 |
| 0,7 | 97,1 % | 96,5–97,6 % | 3 349 | 531 | 0 | 3 |
| 0,8 | 99,3 % | 99,0–99,5 % | 3 950 | 23 | 0 | 0 |
Čím hustší obrázek, tím delší bloky, menší volnosti a víc jistých polí – podíl jednoznačných obrázků rychle roste a úroveň klesá. Řídké obrázky jsou plné krátkých bloků a jednoznačné jsou jen výjimečně. Dobré křížovky proto mívají plné siluety a zhruba polovinu až dvě třetiny polí vybarvených; motivy průvodce mají hustotu od 26 % (Klíč) do 70 % (Jablko).
8.6Vlastní motivy
Všechny obrázky v průvodci jsou vlastní jednoduché motivy. Kdo kreslí křížovky pro druhé, měl by kreslit sám: obrázky z cizích sbírek, postavy z pohádek a filmů, loga a značky mají autory a vlastníky. Jednoduché předměty, zvířata a krajiny se dají nakreslit po svém.
Autor křížovek kreslí obrázek, kontroluje a upravuje v kruhu, dokud nemá jediné řešení i požadovanou úroveň. Dobrý zvyk: nejdřív obrys, pak výplň, nakonec detail – a po každém detailu kontrola.
- Plné siluety, kontrast a jeden výrazný detail; rozlišení podle publika.
- Víc řešení vzniká místně – osamělá pole, úhlopříčky, šachovnice. Oprava: změnit rozdílové pole a znovu ověřit.
- Hustší obrázky jsou častěji jednoznačné a lehčí; jediné řešení ale neznamená snadné řešení.
Počítáme umístění, legendy a řešenímistr a věda
Kolik je možných poloh bloků v řadě? Kolik různých legend vůbec může mít řada délky 10? A jaká část všech obrázků má jediné řešení? Na první dvě otázky odpovídají krásné vzorce s kombinačními a Fibonacciho čísly, na třetí úplný výčet pro malé mřížky a simulace pro velké. Kapitola je pro ty, kdo mají rádi kombinatoriku – a vysvětluje, proč jsou dobré křížovky vzácnější, než by se zdálo.
Řádků délky 10 je 2¹⁰ = 1 024, ale různých legend jen 144. Legenda tedy v průměru zahazuje informaci o sedmi řádcích. Že se z legend dá přesto složit jediný obrázek, je zásluha křížení: co nerozliší řádky, rozliší sloupce.
+Teorie: hvězdičky a přepážky, Fibonacciho čísla v legendách, úplný výčet, simulace, úrovně náhodných obrázků
9.1Počet umístění
Řada délky n, legenda s k bloky a součtem s, volnost v = n − s − k + 1. Každé umístění popíšeme posloupností symbolů zleva doprava: každý blok i s povinnou mezerou za ním (u posledního bez mezery) je jeden symbol ■, každé další prázdné pole symbol ○. Volných polí je v, bloků k, a každé pořadí v + k symbolů dává právě jedno umístění a naopak. Umístění je tedy tolik, kolika způsoby lze z v + k míst vybrat k míst pro bloky:
Je to klasická úvaha „hvězdičky a přepážky“ (stars and bars): rozdělujeme v volných polí do k + 1 přihrádek – před první blok, mezi bloky a za poslední. Pro k = 0 vychází 1 (prázdná řada), pro v = 0 také 1 (řada je určená).
9.2Kolik je legend
Legenda, jejíž bloky s povinnými mezerami vyplní přesně m polí, odpovídá řetězci délky m z vybarvených polí a jednotlivých mezer, který začíná i končí vybarveným polem a nemá dvě mezery vedle sebe. Takových řetězců je Fibonacciho číslo F(m) (F(1) = F(2) = 1, F(m) = F(m − 1) + F(m − 2)): řetězec končí buď „vybarvené, vybarvené“, nebo „mezera, vybarvené“, a ubráním konce dostaneme kratší řetězec stejného druhu. Řada délky n má každou legendu, která se do ní vejde, a k tomu legendu 0:
| Délka n | Různých legend F(n + 2) | Různých řad 2ⁿ | Řad na jednu legendu |
|---|---|---|---|
| 5 | 13 | 32 | 2,5 |
| 10 | 144 | 1 024 | 7,1 |
| 15 | 1 597 | 32 768 | 20,5 |
| 20 | 17 711 | 1 048 576 | 59,2 |
| 25 | 196 418 | 33 554 432 | 170,8 |
| 30 | 2 178 309 | 1 073 741 824 | 492,9 |
Poměr 2ⁿ / F(n + 2) roste přibližně jako (2/φ)ⁿ ≈ 1,236ⁿ, kde φ ≈ 1,618 je zlatý řez. Jedna řada sama tedy s délkou ztrácí čím dál víc informace. Přesto hrubý odhad počtem nestačí k závěru, že velké obrázky musí být nejednoznačné: všech legend celé mřížky n × n může být až F(n + 2)2n, což je zhruba 21,39 n² – víc než 2n² obrázků. Pokles jednoznačnosti je proto věc struktury, ne počítání.
9.3Úplný výčet malých mřížek
| n | Obrázků 2n² | Různých zadání | S jediným řešením | Podíl | Nejvíc obrázků na jedno zadání |
|---|---|---|---|---|---|
| 1 | 2 | 2 | 2 | 100 % | 1 |
| 2 | 16 | 15 | 14 | 87,50 % | 2 |
| 3 | 512 | 445 | 384 | 75,00 % | 6 |
| 4 | 65 536 | 58 196 | 52 362 | 79,90 % | 24 |
| 5 | 33 554 432 | 28 781 820 | 25 309 575 | 75,43 % | 120 |
| 6 | 68 719 476 736 | – | 49 745 060 669 | 72,39 % | – |
Zajímavý je poslední sloupec. Nejvíc obrázků se stejnou legendou mají pro n ≤ 5 přesně ty se samými jedničkami – permutační matice – a těch je n!. Podíl jednoznačných obrázků zprvu kolísá (pro 4 × 4 je vyšší než pro 3 × 3), pak už klesá.
9.4Simulace větších mřížek
| n | Jediné řešení | 95% interval | Úroveň 1 | Úroveň 2 | Úroveň 3 | Úroveň 4 |
|---|---|---|---|---|---|---|
| 6 | 72,8 % | 71,4–74,2 % | 1 824 | 1 003 | 25 | 61 |
| 7 | 67,8 % | 66,3–69,2 % | 1 204 | 1 403 | 26 | 78 |
| 8 | 62,8 % | 61,3–64,3 % | 689 | 1 689 | 40 | 95 |
| 10 | 53,6 % | 52,1–55,2 % | 131 | 1 812 | 71 | 132 |
| 12 | 44,1 % | 42,6–45,7 % | 10 | 1 501 | 93 | 161 |
| 15 | 31,6 % | 30,2–33,1 % | 0 | 957 | 129 | 178 |
| 20 | 15,7 % | 14,6–16,9 % | 0 | 282 | 156 | 190 |
9.5Úrovně náhodných obrázků
Náhodné obrázky jsou jiné než kreslené: mají krátké bloky a velké volnosti. U 6 × 6 stačí úroveň 1 na 63 % jednoznačných obrázků, u 10 × 10 na 6 % a u 15 × 15 a 20 × 20 už na žádný. U 20 × 20 potřebuje 30 % jednoznačných obrázků zkoušku sporem. Kreslené motivy průvodce jsou naopak většinou úrovně 1 a 2 – plné siluety s dlouhými bloky (kapitola 8). Kdo chce těžkou křížovku, nemusí kreslit náhodný šum; stačí detaily, které vytvoří místa se dvěma možnostmi, rozhodnutelná jen přes několik řad.
Simulace odpovídá na otázku o náhodných obrázcích s nezávislými poli, ne o obrázcích, které kreslí lidé. Čísla jsou proto orientační: kreslené obrázky jsou jednoznačné častěji, protože mají souvislé tvary.
- Umístění v prázdné řadě: C(n − s + 1, k) – hvězdičky a přepážky.
- Legend řady délky n je F(n + 2): 144 pro n = 10 proti 1 024 řadám.
- Jediné řešení má 75,43 % obrázků 5 × 5, v simulaci asi 54 % obrázků 10 × 10 a asi 16 % obrázků 20 × 20.
Složitost a tomografiemistr a věda
Malovaná křížovka je příbuzná vážné vědecké úloze: rekonstrukci obrázku z jeho „rentgenových snímků“. Kdybychom u každé řady znali jen počet vybarvených polí, řešili bychom úlohu diskrétní tomografie, kterou matematici zkoumají od 50. let. Legenda prozrazuje víc – nejen kolik polí, ale i jak jsou seskupená. A přesto je obecná malovaná křížovka výpočetně těžká: rozhodnout, zda má řešení, je NP-úplné. Kapitola vysvětluje obojí.
Srdce 5 × 5 má součty řádků 2, 5, 5, 3, 1 a sloupců 2, 4, 4, 4, 2. Stejné součty mají tři různé obrázky. Legenda ale připouští jen jeden – srdce. O kolik je legenda „chytřejší“ než součty, si ověříte v laboratoři.
+Teorie: diskrétní tomografie, Galeova–Ryserova věta, záměny, legenda proti součtům, NP-úplnost, co je snadné
10.1Rentgen obrázku
Obrázek v mřížce je 0–1 matice. Součty jejích řádků a sloupců jsou jako dva rentgenové snímky – vodorovný a svislý: každý paprsek změří, kolik vybarvených polí prošel. Diskrétní tomografie se ptá, kdy a jak jde obrázek ze snímků zrekonstruovat. Motivace je praktická: Gardner, Gritzmann a Prangenberg (1999) uvádějí rekonstrukci krystalů z elektronové mikroskopie s vysokým rozlišením, kde se počty atomů v řadách měří podél několika směrů.
10.2Kdy obrázek se zadanými součty existuje
Odpověď dali v roce 1957 nezávisle David Gale (přes toky v sítích) a Herbert J. Ryser. Označme součty řádků r₁, …, rm a součty sloupců seřazené sestupně c₁ ≥ … ≥ cn. Obrázek existuje právě tehdy, když součty sedí dohromady (Σ ri = Σ cj) a pro každé k platí
Levá strana je počet vybarvených polí v k nejplnějších sloupcích, pravá strana je nejvíc, kolik do k sloupců mohou řádky dodat (řádek dá do každého sloupce nejvýš jedno pole). Úloha jde navíc vyřešit rychle hladovým postupem: každý řádek dá svá pole do sloupců s největším zbývajícím součtem.
10.3Záměny a jednoznačnost
Ryser dokázal i druhou větu: dva obrázky se stejnými součty jdou vždy převést jeden na druhý řadou záměn. Důsledek: obrázek je součty určený jednoznačně právě tehdy, když v něm žádná záměna není. Takových obrázků je málo – mají „schodovitý“ tvar, kde se vybarvená pole drží v levém horním rohu po přeskládání řádků a sloupců. Plný čtverec uprostřed mřížky je jedním z nich.
| Obrázek | Stejné součty | Stejná legenda |
|---|---|---|
| Srdce 5 × 5 | 3 | 1 |
| Domek 5 × 5 | 5 | 1 |
| Kytka 5 × 5 | 15 | 1 |
| Hříbek 5 × 5 | 1 | 1 |
| vzor se záměnou 5 × 5 (laboratoř) | 906 | 10 |
| vzor se záměnou 6 × 6 (laboratoř) | 71 100 | 288 |
| úhlopříčka 6 × 6 | 720 | 720 |
Legenda určuje součty (součet řady je součet čísel legendy), takže obrázků se stejnou legendou nikdy není víc než obrázků se stejnými součty. Navíc nese informaci o seskupení polí, a proto bývá obrázků se stejnou legendou mnohem méně. Záměna v obrázku je pro křížovku nebezpečná jen tehdy, když ji legendy neodhalí – tedy když jsou čtyři pole záměny samostatnými krátkými bloky nebo jejich prohození bloky nezmění (obr. 8.2 v kapitole 8).
10.4Tři a více směrů
Se dvěma směry (řádky a sloupce) je rekonstrukce ze součtů snadná. Gardner, Gritzmann a Prangenberg (1999) ukázali, že pro tři a více směrů (například i úhlopříčky) se úloha rozhodnout, zda nějaký obrázek se zadanými součty existuje, stává NP-úplnou. Malá změna zadání tak oddělí snadnou úlohu od těžké.
10.5NP-úplnost malovaných křížovek
N. Ueda a T. Nagao z Tokijského technologického institutu v technické zprávě z roku 1996 ukázali, že rozhodnout, zda malovaná křížovka má řešení, je NP-úplné. Použili převody, které zachovávají počet řešení (parsimonious reductions), a z nich plyne i těžkost otázky „má křížovka jiné řešení než toto?“ – zavedli pro ni pojem ASP-úplnost. Zprávu samotnou se nám nepodařilo získat; údaje přebíráme z prací, které ji citují (viz příloha C).
NP-úplnost znamená dvě věci. Za prvé: když vám někdo dá vyplněnou mřížku, ověříte ji rychle – stačí spočítat legendy. Za druhé: pro hledání řešení libovolně velkých křížovek není znám algoritmus, který by vždy stačil polynomiální čas, a kdyby existoval, uměli bychom rychle řešit tisíce dalších těžkých úloh (SAT, rozvrhování, …). Je to výrok o nejhorším případě pro rostoucí velikost, ne o konkrétní křížovce v časopise.
10.6Co je přesto snadné
Úrovně 1 až 4 z tohoto průvodce jsou všechny polynomiální. Úplný rozbor řady trvá zhruba n · k kroků (kapitola 11), a protože každý úspěšný krok rozhodne aspoň jedno pole, je kroků nejvýš tolik, kolik je polí. Zkouška sporem s jedním polem je jen šíření, opakované pro nejvýš dvakrát tolik předpokladů, kolik je neznámých polí. Těžké jsou tedy jen křížovky „mimo škálu“, kde je potřeba skutečné prohledávání. Proto autoři křížovek ověřují řešitelnost logikou – a proto počítačové řešiče v soutěžích soupeří hlavně na velkých náhodných mřížkách.
„NP-úplné“ neznamená „každá velká křížovka je neřešitelná“. Znamená jen, že neexistuje (pokud P ≠ NP) zaručeně rychlý postup pro všechny křížovky. Křížovky, které skládají lidé pro lidi, jsou obvykle řešitelné úvahou o řadách – a ty jsou rychlé i pro počítač.
- Součty řádků a sloupců = tomografie: existenci rozhoduje Galeova–Ryserova podmínka, nejednoznačnost způsobují záměny 2 × 2.
- Legenda nese víc informace než součty; obrázků se stejnou legendou je nejvýš tolik jako se stejnými součty.
- Obecná křížovka je NP-úplná (Ueda a Nagao 1996), ale úrovně 1–4 jsou polynomiální.
Jak křížovky řeší počítačmistr a věda
Počítač nepotřebuje techniky s lidskými jmény. Stačí mu jeden nástroj – úplný řešič řady, který dynamickým programováním za zlomek milisekundy zjistí, co z řady plyne – a fronta řad, ve kterých se něco změnilo. Když to nestačí, přijde zkouška sporem a nakonec prohledávání s návratem. Kapitola ukazuje, jak tyto části fungují a jak se z nich skládá řešič, který zároveň počítá řešení a hodnotí obtížnost.
Řada 20 polí s legendou 1 1 1 1 1 má v prázdném stavu 4 368 umístění. Řešič řady je ale nevypisuje: vyplní tabulku 6 × 21 hodnot „jde / nejde“ a z ní přečte, které pole může být vybarvené a které prázdné. Práce roste s délkou řady krát počet bloků, ne s počtem umístění.
+Teorie: řešič řady dynamickým programováním, fronta a pevný bod, zkouška sporem, prohledávání, jiné přístupy, soutěže
11.1Řešič řady dynamickým programováním
Řada má pole 1 až n se stavy (neznámé, vybarvené, křížek) a legendu b₁, …, bk. Definujeme logickou tabulku
Platí F[0][x] = „v polích 1 až x není žádné vybarvené pole“ a pro i ≥ 1 je F[i][x] pravda, když nastane jedna ze dvou možností: pole x je prázdné (není vybarvené) a F[i][x − 1]; nebo blok i končí na poli x – jeho pole nejsou křížky, pole těsně před ním není vybarvené a F[i − 1][x − bi − 1]. Stejně se zprava doleva spočítá G[i][x] pro bloky i až k v polích x až n. Z obou tabulek se pak přečte:
- pole může být prázdné, když pro nějaké i jde prvních i bloků umístit vlevo od něj a zbytek vpravo;
- pole může být vybarvené, když ho pokrývá nějaký přípustný začátek některého bloku;
- může-li být jen jedno z toho, je pole určené; nemůže-li být ani jedno, je řada ve sporu.
| i \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 bloků | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| blok 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| bloky 2 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Tabulka má (k + 1)(n + 1) hodnot a každá se spočítá v konstantním čase, když si předem sečteme křížky a vybarvená pole od začátku řady. Úplný rozbor řady tedy stojí řádově n · k operací. Právě tohle počítá technika Všechna umístění v laboratořích a nápovědě 3D hry.
11.2Fronta a pevný bod
Šíření (obr. 11.1) končí, když je fronta prázdná – žádná řada už nic nového nedá. Tomuto stavu se říká pevný bod. Nezáleží na pořadí, v jakém se řady z fronty berou: každá úvaha jen přidává jistá pole, a proto skončí všechna pořadí ve stejném pevném bodě. Pořadí ovlivní jen to, kolik práce to stojí (kapitola 7). Křížovky, které šíření vyřeší celé, se nazývají řešitelné po řadách; v řeči průvodce jsou to úrovně 1 až 3.
11.3Zkouška sporem v programu
Když šíření skončí v pevném bodě a mřížka není hotová, program zkouší pole (anglicky probing): dočasně nastaví hodnotu, spustí šíření a při sporu zapíše opak. Jan Wolter ve svém přehledu řešičů nonogramů (Survey of Paint-by-Number Puzzle Solvers, aktualizovaném naposledy kolem roku 2012) srovnává přes dvacet programů a popisuje mimo jiné i zkoušení polí. Podle něj většinu křížovek z běžných sbírek vyřeší už samotné šíření, kdežto náhodné mřížky 30 × 30 jen zřídka.
11.4Prohledávání s návratem a počítání řešení
Úplný řešič musí zvládnout i křížovky mimo škálu. Vybere neznámé pole – například v řadě s nejméně neznámými poli –, rozvětví se na „vybarvené“ a „prázdné“ a v každé větvi šíří. Větev se sporem zahodí, hotovou mřížku započítá. Takhle laboratoře průvodce počítají řešení: hledání se zastaví po druhém nalezeném řešení, protože pro kontrolu jednoznačnosti stačí vědět, zda je řešení jedno, nebo víc. Prohledávání je v nejhorším případě exponenciální (kapitola 10), u běžných křížovek ale šíření ořeže většinu větví.
Všech 24 motivů průvodce má podle tohoto prohledávání jediné řešení. U simulace v kapitole 9 byl limit 100 000 uzlů prohledávání na obrázek; 37 ze 4 000 náhodných obrázků ho překročilo a zůstalo nerozhodnutých. Laboratoře v prohlížeči používají nižší limit (20 000 uzlů) a případné přerušení hlásí.
11.5Jiné přístupy
- Celočíselné programování. R. A. Bosch (2001) zapsal malovanou křížovku jako celočíselný (0–1) lineární program, který jde předat obecnému řešiči optimalizačních úloh; podmínky hlídají pořadí bloků, mezery a shodu řádků se sloupci. Pro barevné křížovky podobný model popsali Mingote a Azevedo (2009).
- Relaxace. Batenburg a Kosters (2009) kombinují zjednodušené úlohy, které jdou řešit rychle – mimo jiné převod na 2-SAT (splnitelnost formulí s dvojicemi proměnných) – a jejich závěry spojují.
- SAT. Křížovku lze přepsat na výrokovou formuli a předat obecnému řešiči splnitelnosti; to je přirozený most k NP-úplnosti z kapitoly 10.
- Specializované řešiče pro soutěže. I-Chen Wu a kolektiv (2013) publikovali v časopise IEEE o počítačových hrách článek An Efficient Approach to Solving Nonograms o rychlém řešiči.
Podle wiki o počítačových hrách chessprogramming.org se nonogramy od roku 2010 objevují v soutěžích počítačových programů, například na Computer Olympiad a na tchajwanských turnajích TAAI a TCGA. Programy v nich řeší sady velkých náhodných křížovek na čas.
- Úplný řešič řady = dynamické programování F, G za zhruba n · k operací.
- Fronta změněných řad vede k pevnému bodu nezávisle na pořadí; pak zkouška sporem, nakonec prohledávání.
- Jednoznačnost se ověřuje prohledáváním do druhého řešení; další přístupy: celočíselné programování, relaxace, SAT.
Tvorba úloh a zdravé hranímistr a věda
Malovaná křížovka vzniká v pěti krocích: nápad, mřížka, kontrola jednoznačnosti, hodnocení obtížnosti a zkouška řešením. Kreslení a rastrování popisuje kapitola 8. Tato kapitola skládá celý postup dohromady: jak se z obrázku spočítá legenda, jak počítač ověří jediné řešení, jak se opravuje a jak průvodce i 3D hra měří obtížnost. Na konci je pár zásad zdravého hraní.
Nakreslete do mřížky 10 × 10 šikmý pás široký dvě pole. Legenda vypadá nevinně, samé dvojky. Odpovídá jí ale 34 různých obrázků. Stačí přidat jedno pole a řešení je jediné. Takových oprav jednoho pole je ze 100 možných jen 10 a všechny dávají těžkou křížovku.
+Teorie: z obrázku legenda, kontrola jednoznačnosti, oprava, hodnocení obtížnosti, velikost, zdravé hraní, křížovky ve výuce
12.1Z obrázku legenda
Nápad a rastrování popisuje kapitola 8: plná silueta, jeden motiv, rozlišení podle publika. Hotový obrázek je tabulka polí vybarvených (1) a prázdných (0). Legenda se z ní spočítá mechanicky. V každé řadě se zleva doprava (ve sloupci shora dolů) zapíše délka každého souvislého úseku jedniček.clues from a picture
Řádek 0011101100 má úseky 111 a 11, legenda je 3 2. Prázdný řádek má legendu 0. Plný řádek deseti polí má legendu 10.
Legenda je vlastně délkové kódování řady (anglicky run-length encoding): ukládá délky úseků jedniček, ale ne délky mezer mezi nimi. Právě tahle chybějící informace dělá z obrázku hádanku. Mezery si řešitel musí odvodit z křížících se řad.
12.2Kontrola jednoznačnosti a oprava
Ke každé legendě vytvořené z obrázku existuje aspoň jedno řešení, totiž sám obrázek. Otázka zní, jestli je jediné. Počítač ji rozhodne prohledáváním s návratem z kapitoly 11, které se zastaví po nalezení druhého řešení. Pokud prohledá všechny větve a najde jen jedno řešení, je křížovka v pořádku. Pokud najde dvě, pole, ve kterých se liší, ukazují, kde zasáhnout.uniqueness check
Tenké šikmé čáry jsou pro autora nejhorší. Úhlopříčka široká jedno pole v mřížce n × n má v každé řadě legendu 1 a odpovídá jí n! obrázků, pro 10 × 10 tedy 3 628 800 (kapitola 10). Pás široký dvě pole má 34 řešení, pás široký tři pole ještě 8. Oprava se proto zkouší tam, kde se řešení liší: přidá se nebo ubere pole tak, aby se změnila legenda některé řady, ve které se řešení rozcházejí. Nejjednodušší takový rozdíl jsou čtyři rohy obdélníku, tedy záměna z kapitoly 10 (Obr. 8.2). Jistotu, že oprava pomohla, dá ale jen nové ověření.
| Šířka pásu | Řešení před opravou | Změn s jediným řešením (ze 100) | z toho úroveň 4 | z toho mimo škálu |
|---|---|---|---|---|
| 2 pole | 34 | 10 (vždy přidání pole) | 6 | 4 |
| 3 pole | 8 | 16 (10 přidání, 6 ubrání) | 16 | 0 |
Oprava jednoznačnosti často zvedne obtížnost. U obou pásů z Tab. 12.1 nevedla žádná změna jednoho pole k jedinému řešení s úrovní nižší než 4. Proto se po každé úpravě znovu hodnotí (krok 4 v Obr. 12.1). Když obtížnost nesedí, hledá autor jinou opravu nebo obrázek zesílí, například z tenké čáry udělá plnou plochu.
12.3Hodnocení obtížnosti
Průvodce i 3D hra hodnotí křížovku stejně. Lidský řešitel v každém kroku použije nejjednodušší techniku, která něco zapíše (kapitola 11). Úroveň křížovky je nejtěžší technika, kterou za celé řešení použil. Počet kroků měří spíš délku řešení než jeho obtížnost.difficulty rating
| Úroveň | Techniky | Kapitola |
|---|---|---|
| 1 | Překryv, Hotová řada | 2 |
| 2 | + Nedosažitelná pole, Okraj | 3, 4 |
| 3 | + Všechna umístění | 5 |
| 4 | + Zkouška sporem | 6 |
| mimo škálu | jediné řešení, ale řešitel nevystačí ani se zkouškou sporem jednoho pole | 11 |
| Obrázek | Mřížka | Vybarveno | Úroveň | Kroků | Techniky (počet kroků) |
|---|---|---|---|---|---|
| Srdce | 5 × 5 | 16 | 1 | 10 | Překryv 5, Hotová řada 5 |
| Domek | 5 × 5 | 13 | 1 | 11 | Překryv 5, Hotová řada 6 |
| Hříbek | 5 × 5 | 13 | 1 | 8 | Překryv 4, Hotová řada 4 |
| Kytka | 5 × 5 | 9 | 1 | 10 | Překryv 4, Hotová řada 6 |
| Šipka | 5 × 5 | 9 | 1 | 10 | Překryv 4, Hotová řada 6 |
| Hrnek | 8 × 8 | 37 | 1 | 14 | Překryv 7, Hotová řada 7 |
| Rybka | 8 × 8 | 33 | 1 | 17 | Překryv 9, Hotová řada 8 |
| Plachetnice | 10 × 10 | 45 | 1 | 21 | Překryv 10, Hotová řada 11 |
| Smrček | 10 × 10 | 46 | 1 | 18 | Překryv 9, Hotová řada 9 |
| Sova | 10 × 10 | 58 | 1 | 41 | Překryv 26, Hotová řada 15 |
| Kočka | 10 × 10 | 62 | 1 | 33 | Překryv 19, Hotová řada 14 |
| Jablko | 10 × 10 | 70 | 1 | 26 | Překryv 17, Hotová řada 9 |
| Zajíc | 10 × 10 | 68 | 1 | 26 | Překryv 14, Hotová řada 12 |
| Klíč | 10 × 10 | 26 | 2 | 28 | Překryv 11, Hotová řada 16, Okraj 1 |
| Tulipán | 10 × 10 | 46 | 2 | 26 | Překryv 12, Hotová řada 12, Okraj 2 |
| Noty | 10 × 10 | 43 | 2 | 32 | Překryv 18, Hotová řada 12, Okraj 2 |
| Ptáček | 10 × 10 | 43 | 2 | 36 | Překryv 17, Hotová řada 13, Okraj 6 |
| Hvězda | 10 × 10 | 50 | 3 | 47 | Překryv 24, Hotová řada 12, Okraj 8, Všechna umístění 3 |
| Deštník | 10 × 10 | 39 | 4 | 33 | Překryv 16, Hotová řada 11, Okraj 5, Zkouška sporem 1 |
| Kotva | 10 × 10 | 40 | 4 | 38 | Překryv 16, Hotová řada 15, Nedosažitelná pole 2, Okraj 4, Zkouška sporem 1 |
| Hrad | 15 × 15 | 156 | 2 | 52 | Překryv 32, Hotová řada 19, Okraj 1 |
| Kohout | 15 × 15 | 79 | 2 | 63 | Překryv 30, Hotová řada 22, Nedosažitelná pole 1, Okraj 10 |
| Slon | 15 × 15 | 119 | 1 | 46 | Překryv 23, Hotová řada 23 |
| Maják | 20 × 20 | 144 | 1 | 56 | Překryv 26, Hotová řada 30 |
Z tabulky jsou vidět dvě věci. Velikost a úroveň spolu souvisí jen volně: Maják 20 × 20 vystačí s překryvem a hotovou řadou, zatímco Kotva 10 × 10 potřebuje zkoušku sporem. Velká mřížka prodlužuje řešení, malá těžká mřížka ho zpomaluje. A techniky z úrovně 1 tvoří většinu kroků i u těžkých křížovek. Zkouška sporem má v Deštníku a Kotvě jen jeden krok z 33 a 38, ale bez něj se řešení zastaví. Negativy obrázků (kapitola 8) se hodnotí zvlášť a úroveň se může změnit oběma směry. Negativ Kotvy i Deštníku je úroveň 1, negativ Sovy úroveň 2.
12.4Velikost a čas
Mřížka 5 × 5 má 25 polí, 10 × 10 má 100, 15 × 15 má 225, 20 × 20 má 400 a 25 × 25 má 625. Počet kroků roste pomaleji než počet polí, protože jeden krok často zapíše celou skupinu polí. Srdce 5 × 5 má 10 kroků, Smrček 10 × 10 má 18 a Maják 20 × 20 má 56. Čas člověka ale roste i s tím, kolik čísel musí přečíst a udržet v hlavě. Velká křížovka je proto spíš na víc sezení. Hra má režimy podle velikosti: Pro děti 5 × 5 až 8 × 8, Klasické 10 × 10 až 20 × 20 podle obtížnosti a Velké 25 × 25.
Když tvoříte křížovky pro druhé, ověřte každou i sami tužkou nebo v laboratoři krok za krokem (kapitola 11). Počítač řekne, jestli je řešení jediné a jak je těžké. Nepozná ale, jestli je obrázek na konci hezký a jestli řešení člověka bavilo.
12.5Zdravé hraní
Malované křížovky jsou klidná hra bez časového tlaku. Přesto dokážou vtáhnout: ještě jedna řada, ještě jeden obrázek. Pár zásad:healthy play
- Přestávky. Po delším luštění vstaňte a protáhněte se. Když se zaseknete, odejděte na pár minut. Čerstvý pohled často najde překryv, který jste přehlédli.
- Oči. Drobná čísla v hustých mřížkách oči unaví. Občas zaostřete do dálky, dopřejte si dobré světlo a jas obrazovky přizpůsobte okolí. Lupou (roztažením dvěma prsty nebo kolečkem myši) si mřížku ve hře zvětšíte, takže nemusíte mžourat.
- Nehádejte. Křížovka ve hře jde vyřešit logikou. Hádání vede k chybám, které se těžko hledají. Raději použijte nápovědu trenéra, která pojmenuje techniku a odkáže na kapitolu.
- Děti. Začínají na mřížkách 5 × 5 a krátkých chvilkách, ideálně s dospělým. Dobrou náhradou obrazovky jsou papír, tužka a čtverečkovaný sešit.
- Spánek. Večer odložte obrazovku včas. Rozluštěná křížovka počká do rána.
- Hrajte pro radost. Hvězdičky, rekordy a série denních výzev mají motivovat, nejsou povinnost. Žádné sázky ani peníze.
12.6Křížovky ve výuce
Malované křížovky se hodí i do školy a domácího procvičování, a to nejen jako logická hra:
- Souřadnice. Pole se označují řádkem a sloupcem (ř3s2), stejně jako body v tabulce nebo na mapě.
- Pixely a rastr. Obrázek z polí je totéž co obrázek z pixelů na obrazovce. Kapitola 8 ukazuje, jak rozlišení mění tvar: kruh 5 × 5 je kosočtverec.
- Kódování. Řádek obrázku jako nuly a jedničky je dvojkový zápis. Legenda je jeho délkové kódování, které ukládá úseky místo jednotlivých polí.
- Logika. Úvahy „kdyby, pak spor“ (kapitola 6) jsou důkaz sporem v malém.
12.7Procvičení
- Legenda je délkové kódování řad obrázku. Mezery mezi úseky si řešitel odvozuje.
- Jednoznačnost se ověřuje prohledáváním do druhého řešení a opravuje se změnou polí, ve kterých se řešení liší. Pak se vždy ověřuje znovu.
- Úroveň je nejtěžší potřebná technika, ne velikost. Hrajte s přestávkami, pro radost a bez peněz.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky podle úrovní
| Technika | Co dělá | Úroveň | Kapitola |
|---|---|---|---|
| Překryv | vybarví pole, která blok pokrývá v nejlevější i nejpravější poloze | 1 | 2 |
| Hotová řada | když v řadě stojí všechny bloky legendy, zakřížkuje zbytek | 1 | 2 |
| Nedosažitelná pole | zakřížkuje pole, kam žádný blok nedosáhne, a mezery kratší než blok, který by do nich patřil | 2 | 3 |
| Okraj | vybarvené pole u kraje nebo u křížku přitlačí blok a dovybarví ho | 2 | 3 |
| Všechna umístění | vypíše všechna umístění bloků, která sedí se známými poli, a zapíše jejich průnik | 3 | 5 |
| Zkouška sporem | předpoklad v jednom poli vede přes křížící se řady ke sporu, platí tedy opak | 4 | 6 |
Vzorce na jednom místě
Počty na jednom místě
| Údaj | Hodnota | Kde |
|---|---|---|
| legenda 1 1 1 1 1 v prázdné řadě 20 polí: umístění | 4 368 | kap. 5, 11 |
| řada 10 polí: různých legend / různých řad | 144 / 1 024 | kap. 9 |
| obrázky s jediným řešením: 5 × 5 přesně / 6 × 6 přesně | 75,43 % / 72,39 % | kap. 9 |
| obrázky s jediným řešením (simulace, hustota 0,5): 10 × 10 / 20 × 20 | 53,6 % / 15,7 % | kap. 9 |
| obrázky 10 × 10 s jediným řešením při hustotě 0,3 / 0,7 | 2,0 % / 97,1 % | kap. 8 |
| vzor 6 × 6 se záměnou: obrázků se stejnými součty / se stejnou legendou | 71 100 / 288 | kap. 10 |
| úhlopříčka 10 × 10 / pás široký 2 pole / pás široký 3 pole: řešení | 3 628 800 / 34 / 8 | kap. 10, 12 |
| Maják 20 × 20: prohlédnuté řady při frontě / procházení dokola / nejméně umístění | 73 / 69 / 58 | kap. 7 |
| 24 obrázků průvodce: úroveň 1 / 2 / 3 / 4 | 15 / 6 / 1 / 2 | kap. 12 |
| negativy 24 obrázků průvodce s jediným řešením | 21 | kap. 8, 12 |
Zdroje a předpoklady
Historické údaje a výsledky výzkumu byly ověřeny na uvedených zdrojích. Ověřeno 8. 11. 2026.
Historie hry
- Encyklopedické heslo Nonogram (Wikipedie, anglická verze) a prameny v něm citované. Soutěž Non Ishidy v roce 1987, nezávislý autor Tetsuya Nishio, tři úlohy „Window Art Puzzles“ v roce 1988, James Dalgety a název nonogram, týdenní otiskování v The Sunday Telegraph od roku 1990, kniha nonogramů v roce 1993, soutěž o název griddlers v roce 1998, pravidla barevných křížovek a citace prací o NP-úplnosti. Ověřeno 8. 11. 2026.
- Encyklopedické heslo o nonogramech (Wikipedie, japonská verze): první úlohy obou autorů a pojmenování v roce 1988. Ověřeno 8. 11. 2026.
- Encyklopedické heslo Zakódovaný obrázek (Wikipedie, česká verze): časopis Panorama křížovek v první polovině 90. let, specializované tituly ze Slovenska, původ názvu malované křížovky. Ověřeno 8. 11. 2026.
Složitost a tomografie
- Ueda, N.; Nagao, T. (1996): NP-completeness Results for NONOGRAM via Parsimonious Reductions. Technická zpráva TR96-0008, Department of Computer Science, Tokyo Institute of Technology. Zprávu samotnou se nepodařilo získat. Údaje (autoři, rok, číslo zprávy, převody zachovávající počet řešení) jsou ověřeny z prací, které ji citují: anglické Wikipedie, posloupnosti OEIS A242876 a preprintu arXiv:2507.07283. Ověřeno 8. 11. 2026.
- Ryser, H. J. (1957): Combinatorial properties of matrices of zeros and ones. Canadian Journal of Mathematics 9, 371–377. Ověřeno 8. 11. 2026 (bibliografické údaje).
- Gale, D. (1957): A theorem on flows in networks. Pacific Journal of Mathematics 7(2), 1073–1082. Ověřeno 8. 11. 2026 (bibliografické údaje).
- Gardner, R. J.; Gritzmann, P.; Prangenberg, D. (1999): On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Mathematics 202, 45–71. Ověřeno 8. 11. 2026 (bibliografické údaje a abstrakt).
- OEIS A242876: počet obrázků n × n, jejichž legenda má jediné řešení. Hodnoty pro n ≤ 6 (výpočty mimo jiné B. Felgenhauera) a odkaz na práci Batenburg, K. J.; Kosters, W. A. (2012): On the difficulty of Nonograms. ICGA Journal 35(4), 195–205. Ověřeno 8. 11. 2026.
Algoritmy a soutěže
- Batenburg, K. J.; Kosters, W. A. (2009): Solving Nonograms by combining relaxations. Pattern Recognition 42(8), 1672–1683. Ověřeno 8. 11. 2026 (bibliografické údaje a abstrakt).
- Bosch, R. A. (2001): Painting by numbers. Optima 65, 16–17. Ověřeno 8. 11. 2026 (bibliografické údaje a citace).
- Mingote, L.; Azevedo, F. (2009): Colored Nonograms: An Integer Linear Programming Approach. Sborník konference EPIA 2009 (Progress in Artificial Intelligence), Springer. Ověřeno 8. 11. 2026 (bibliografické údaje).
- Wu, I-C. a kol. (2013): An Efficient Approach to Solving Nonograms. IEEE Transactions on Computational Intelligence and AI in Games 5(3). Ověřeno 8. 11. 2026 (bibliografické údaje a abstrakt).
- Wolter, J.: Survey of Paint-by-Number Puzzle Solvers (webpbn.com), srovnání řešičů, naposledy aktualizované kolem roku 2012. Ověřeno 8. 11. 2026.
- Chessprogramming wiki, heslo Nonogram: soutěže počítačových řešičů od roku 2010 (Computer Olympiad, TAAI, TCGA). Ověřeno 8. 11. 2026.
Modelové předpoklady laboratoří
Všechny legendy, tabulky, simulace a hodnocení počítá kód průvodce. Každá křížovka v textu, laboratořích a minihrách má ověřeně jediné řešení. Ověřuje ho prohledávání se šířením řad (kapitola 11), které hledá druhé řešení. Lidský řešitel postupuje podle Tab. B.1 a úroveň je nejvyšší úroveň použité techniky. Jiný řešitel s jiným pořadím nebo jinými technikami může stejné křížovce přidělit jinou úroveň. „Mimo škálu“ proto znamená „nad rámec technik průvodce“, ne „nejtěžší“. Počet kroků závisí na tom, jak řešitel kroky vybírá. Měří délku řešení, ne obtížnost.
Úplné výčty v kapitole 9 projdou všechny obrázky do 5 × 5; hodnota pro 6 × 6 je převzatá z OEIS A242876. Simulace v kapitolách 8 a 9 mají 4 000 náhodných obrázků na každou hodnotu, pole jsou vybarvená nezávisle se zadanou hustotou a intervaly jsou Wilsonovy 95% intervaly. Limit prohledávání je 100 000 uzlů na obrázek. Obrázky nad limitem nejsou započítané mezi jednoznačné. Laboratoře v prohlížeči mají nižší limit a případné přerušení hlásí. Pole se v textu označují ř (řádek) a s (sloupec), horní levé pole je ř1s1, pole v řadě se číslují od 1 zleva, ve sloupci shora.
Co zůstává nejisté
Rok, kdy vznikl název nonogram, prameny uvádějí různě. Anglická Wikipedie rok neuvádí, japonská ho klade do roku 1988. Českou historii (Panorama křížovek, slovenské tituly, původ názvu malované křížovky) známe jen z české Wikipedie a nezávislý pramen se nám najít nepodařilo. Technickou zprávu Uedy a Nagaa (1996) jsme neměli v ruce. Její obsah popisujeme podle prací, které ji citují. U prací Batenburga a Kosterse, Gardnera a kol. a Wua a kol. jsme ověřili bibliografické údaje a abstrakty, ne celé texty. Přehled Jana Woltera je webová stránka bez pevného data vydání. Podíly jednoznačných obrázků pro n ≥ 7 jsou odhady ze simulace s uvedeným intervalem. U 20 × 20 skončilo 37 ze 4 000 obrázků nerozhodnuto, takže skutečný podíl může být nejvýš asi o 0,9 procentního bodu vyšší.