← Herna
Malované křížovky ve 3D
📖 Průvodce
📖 Průvodce: Malované křížovky12 kapitol hned pod hrou ↓
Malované křížovky🧭 Další průvodci a hry
INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

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.

krok řešení–
technika–
rozhodnuto polí–
nejtěžší úroveň–
Úvodem

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

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Pravidla, pojmy a historiezá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á řadazákladynejlevě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á polezákladyjak vybarvené pole a křížek přitlačí bloky, dosah bloku, krátké mezery mezi křížky
4 Komu patří vybarvený úsekzákladypř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 sporempokročilíco dělat, když se řady zaseknou; předpoklad, šíření, spor; proč to není hádání
7 Velké a barevné křížovkypokročilípořadí řad na mřížce 20 × 20, kontrola chyb, barevné křížovky a jejich mezery
8 Dobrý obrázekpokroč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ědavzorec 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 tomografiemistr a vědaNP-ú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ědaod 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šší.

Tab. 0.2Úrovně obtížnosti v průvodci a ve 3D hře
ÚroveňNejtěžší potřebná technikaKapitola
1Překryv, Hotová řada2
2Nedosažitelná pole, Okraj3 (přiřazování úseků v 4)
3Všechna umístění5
4Zkouška sporem6
mimo škálunestačí ani zkouška sporem s jedním polem11
Ve 3D hře mají obtížnosti 4 a 5 stejnou nejtěžší techniku, zkoušku sporem; pětka ji vyžaduje na větších mřížkách. Všech 24 ukázkových křížovek průvodce jsou vlastní motivy a každá má jediné řešení, ověřené prohledáváním.

Čtyři druhy rámečků

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

Konkrétní řada nebo mřížka, kterou si můžete ověřit v laboratoři.

Z historie

Jak hádanka vznikla, kdo ji pojmenoval a co o ní dokázali matematici a informatici.

Mistrovská pomůcka

Rychlé pravidlo, zkratka nebo návyk, který používají zkušení luštitelé.

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

Hrajte

Malované křížovky ve 3D

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.

Jak to funguje: každá křížovka má jediné řešení a jde vyřešit logikou bez hádání – ověřuje to stejný druh řešitele, jaký popisují kapitoly 11 a 12. Nápověda trenéra má tři stupně: první klepnutí ukáže řadu, kam se dívat, druhé pojmenuje techniku a ukáže pole, třetí krok provede; vždy s odkazem na kapitolu, kde se technika vykládá. V nastavení přepnete Pohled 3D / 2D shora, kontrolu chyb hned nebo až na konci a automatické křížky v hotové řadě (kapitola 2). Tahy jde vracet i opakovat. Za rychlé vyřešení bez nápovědy a bez chyby jsou tři hvězdy. Rekordy, hvězdy, sbírka obrázků a série denních výzev se ukládají jen ve vašem prohlížeči.
Část IZáklady
1

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.

zadání1351 11 114341řešení1351 11 114341
Obr. 1.1Křížovka Domek 5 × 5. Vlevo zadání: legenda řádků vlevo, legenda sloupců nahoře. Vpravo řešení: vybarvená pole tvoří domek, křížky označují prázdná pole. Například 2. řádek má legendu 3 – jeden blok tří polí – a 4. řádek legendu 1 1 – dva bloky po jednom poli s mezerou mezi nimi.
První malovaná křížovka
Vyberte křížovku a klepejte na pole. Přepínač určuje, jestli klepnutí pole vybarví, nebo do něj udělá křížek (prázdné pole); opakované klepnutí pole vymaže. Čísla legendy zešednou, jakmile vybarvená pole v řadě tvoří přesně její bloky. Tlačítko „Zkontrolovat“ označí chyby červeně. Za první vyřešenou křížovku získáte 15 XP.
LABORATOŘ
Model: všechny tři křížovky jsou vlastní motivy průvodce a každá má jediné řešení (ověřeno prohledáním všech možností). Srdce a Hrnek jdou vyřešit jen dvěma nejjednoduššími technikami z kapitoly 2, Plachetnice také; liší se délkou. Tip: začněte řadami s velkými čísly.
+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.

Pozor

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

3 1 2legenda12345678910blok 3mezerablok 1křížkyblok 2křížek
Obr. 1.2Řádek 10 polí s legendou 3 1 2 v jedné z možných poloh. Bloky 3, 1 a 2 jsou vybarvené, mezi nimi jsou prázdná pole označená křížkem. Pole 4 a 6 jsou povinné mezery; další prázdná pole jsou „volná“.

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 řady délky n\[ v = n - (s + k - 1) \]

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.

Příklad Volnost tří řad o 10 polích

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.

Mistrovská pomůcka

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

Z historie

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

1
Jaká je volnost řady 15 polí s legendou 2 3 4?
s = 9, k = 3, bloky s mezerami potřebují 9 + 2 = 11 polí. Volnost je 15 − 11 = 4.
2
Může mít řádek 8 polí legendu 3 3 2?
Nemůže: potřeboval by 8 + 2 = 10 polí. Taková legenda by znamenala chybu v zadání.
3
Řádek 6 polí má legendu 1 1 1. Kolik vybarvených polí obsahuje a kolik prázdných?
Vybarvená jsou 3, prázdná 3; dvě z prázdných jsou povinné mezery a jedno je volné (volnost 6 − 5 = 1).
4
Proč se v řadě nemohou dva bloky dotýkat?
Dotýkající se bloky by tvořily jeden souvislý úsek, tedy jeden delší blok. Legenda 2 2 by se změnila na 4. Mezera mezi bloky je proto součástí pravidla, ne zvláštní podmínka.
5
Kdo a kdy vymyslel slovo nonogram?
Britský sběratel hlavolamů James Dalgety; složil ho ze jména Non Ishidy a přípony -gram (jako v diagramu). Anglická Wikipedie rok vzniku názvu neuvádí, jen že týdenní otiskování v The Sunday Telegraph začalo v roce 1990; japonská Wikipedie klade pojmenování do roku 1988. Viz příloha C.
Co si odnést
  • 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.
Část IZáklady
2

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.

12345678910nejvíc vlevo34nejvíc vpravo34překryv
Obr. 2.1Legenda 3 4 v řadě 10 polí, volnost 10 − (7 + 1) = 2. Blok 3 leží v nejlevější poloze na polích 1–3, v nejpravější na 3–5: společné je pole 3. Blok 4 zabírá 5–8, nebo 7–10: společná jsou pole 7 a 8. Překryv vybarví tři pole.
Posuvné krajní polohy
Nastavte délku řady a napište legendu (čísla oddělená mezerou). Posuvníkem posouváte celou skupinu bloků od nejlevější polohy k nejpravější; posunout jde nejvýš o volnost. Spodní pruh ukazuje pole, která jsou vybarvená ve všech polohách – překryv. Předvolby nahoře ukazují typické případy.
LABORATOŘ
Model: nejlevější poloha klade bloky co nejvíc doleva s jednou mezerou mezi nimi, nejpravější co nejvíc doprava. Prostřední pruh posouvá všechny bloky najednou; skutečné umístění může posouvat bloky i každý zvlášť, ale každý blok vždy leží mezi svou nejlevější a nejpravější polohou. Proto překryv platí pro všechna umístění.
Minihra: Kolik vybarví překryv?
Laboratoř ukáže délku řady a legendu. Spočítejte z hlavy, kolik polí vybarví samotný překryv, a zvolte odpověď. Krajní polohy a správný výsledek se ukážou až po volbě. Kolo má osm řad; za aspoň šest správných odpovědí získáte 15 XP.
MINIHRA
0 / 8
+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

Začátek bloku j v nejlevější poloze (pole číslujeme od 1)\[ L_j = 1 + (b_1 + 1) + (b_2 + 1) + \dots + (b_{j-1} + 1) \]

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

Počet polí, která překryv vybarví v bloku j\[ \max(0,\; b_j - v) \]

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.

Tab. 2.1Volnost, překryv a počet umístění pro legendy v prázdné řadě 10 polí
LegendaSoučet sVolnost vPřekryv vybarvíUmístění
10100101
99182
88263
77344
66425
55506
4 48163
5 38163
3 47236
3 3 28081
2 2 262010
1 1 1 1 15106
Spočítáno řešičem průvodce. Sloupec Umístění je počet všech poloh bloků; vzorec pro něj odvodí kapitola 9.
Pozor

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.

Příklad Legenda 4, křížky na polích 3 a 8

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

12345678910předpo
Obr. 2.2Hotová řada: legenda 2 3, vybarvená pole 1, 2, 4, 5 a 6. Vybarvených polí je 5 = 2 + 3, takže všechny bloky stojí a zbylá neznámá pole (oranžově) jsou křížky.

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.

Mistrovská pomůcka

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.

1
Řada 12 polí, legenda 4 3 2. Kolik polí vybarví překryv?
Volnost 12 − (9 + 2) = 1. Bloky dají 4 − 1 = 3, 3 − 1 = 2 a 2 − 1 = 1 pole, celkem 6.
2
Řada 15 polí má legendu 8. Která pole vybarví překryv?
Volnost 7, blok začíná na polích 1 až 8. Společná pole jsou 8 (konec nejlevější polohy je 8, začátek nejpravější 8): jen pole 8.
3
Řada 10 polí s legendou 1 1 má vybarvená pole 3 a 7. Co platí?
Vybarvená jsou 2 pole = součet legendy. Je to hotová řada: všech osm zbylých polí jsou křížky.
4
Proč překryv nikdy nevybarví pole, které ve skutečnosti prázdné je?
Každé umístění bloků, i to správné, má blok j mezi jeho krajními polohami a pokrývá tedy jejich společná pole. Pole z překryvu je vybarvené v každém umístění, tedy i v řešení. Technika je důkaz, ne odhad.
5
Řada 10 polí, legenda 2 5 (volnost 2). Kde překryv vybarví a kde ne?
Blok 2 je stejně dlouhý jako volnost, nedá nic. Blok 5 leží nejvíc vlevo na polích 4–8, nejvíc vpravo na 6–10; společná jsou pole 6, 7 a 8.
Co si odnést
  • 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.
Část IZáklady
3

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

123456789101112stavnejvíc vlevo42nejvíc vpravo42závěr
Obr. 3.1Okraj: legenda 4 2, vybarvené pole 2. Nejlevější poloha, která sedí se známými poli, klade čtyřku na pole 1–4, nejpravější na 2–5 (dál vpravo by pole 2 zůstalo nepokryté). Společná pole 2–4 jsou vybarvená, nová jsou pole 3 a 4.
Techniky na jedné řadě
Vyberte předvolbu nebo napište legendu a klepáním na pole řady nastavte stav: neznámé → vybarvené → křížek → neznámé. Pod řadou vidíte, co by z ní vyvodila každá technika zvlášť (oranžově nová pole). „Provést krok“ použije nejjednodušší techniku, která něco přinese – stejně jako řešitel ve 3D hře.
LABORATOŘ
Model: techniky mají přesně stejný význam jako v nápovědě 3D hry. Hotová řada a Překryv (úroveň 1) a Nedosažitelná pole (úroveň 2) počítají krajní polohy jen s křížky; Okraj (úroveň 2) i s vybarvenými poli; Všechna umístění (úroveň 3, kapitola 5) projde každé umístění. Délka řady se mění s předvolbou.
Minihra: Které pole jde vybarvit, nebo zakřížkovat?
Laboratoř ukáže řadu s legendou a několika známými poli a oranžově označí jedno neznámé pole. Rozhodněte, jestli ho jde podle této řady vybarvit, zakřížkovat, nebo zatím rozhodnout nejde. Vyhodnocení s technikou a krajními polohami přijde až po volbě. Kolo má osm řad; za aspoň šest správných odpovědí získáte 15 XP.
MINIHRA
0 / 8
+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á.

První blok délky b₁, vybarvené pole p ≤ b₁ (vše od kraje): vybarvená jsou pole\[ p,\; p+1,\; \dots,\; b_1 \]

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.

Příklad Legenda 3, křížek na poli 2, vybarvené pole 5 (10 polí)

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.

Pozor

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

12345678910stavdosah bloku4nedosažitelná
Obr. 3.2Nedosažitelná pole: legenda 4, křížky na polích 3 a 8. Blok 4 se vejde jen do úseku 4–7; pole 1, 2, 9 a 10 leží mimo jeho dosah a jsou to křížky (oranžově). Vybarvení polí 4–7 je Překryv z kapitoly 2.

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.

Mistrovská pomůcka

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ě

Tab. 3.1Techniky jedné řady, co používají a co dávají
TechnikaÚroveňBere v úvahuDáváKapitola
Hotová řada1počet vybarvených políkřížky2
Překryv1křížkyvybarvená pole2
Nedosažitelná pole2křížkykřížky3
Okraj2křížky i vybarvená polevybarvená pole i křížky3
Všechna umístění3všechno, každé umístění zvlášťvšechno, co z řady plyne5
Lidský řešitel průvodce i 3D hry zkouší v každé řadě techniky v tomto pořadí a použije první, která něco přinese. Ze všech řad vybere tu s nejnižší úrovní techniky, při shodě tu, která zapíše nejvíc polí.

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

1
Řada 10 polí, legenda 5, vybarvené je pole 1. Co plyne?
Blok 5 začíná na poli 1: pole 1–5 jsou vybarvená a pole 6 je křížek; protože jiný blok není, jsou křížky i pole 7–10 (hotová řada).
2
Řada 10 polí, legenda 5, vybarvená pole 4 a 5. Která pole jsou křížky?
Blok pokryje pole 4 a 5, začíná tedy na poli 1 až 4 a sahá nejvýš do pole 8. Pole 9 a 10 jsou křížky. Nová vybarvená pole nepřibudou: krajní polohy 1–5 a 4–8 mají společná jen pole 4 a 5, která už známe.
3
Řada 12 polí, legenda 2 3, křížky na polích 1, 3 a 11, vybarvené pole 6. Co dává Okraj?
Pole 2 je samo mezi křížky, dvojka tedy začíná nejdřív na poli 4. Kdyby pole 6 patřilo trojce, dvojka by se před ni mimo křížky nevešla. Patří proto dvojce, která leží na polích 5–6 (na 6–7 by za ní trojce nezbylo místo před křížkem 11), a trojka leží na 8–10. Okraj vybarví pole 5, 8, 9 a 10 a zakřížkuje 2, 4, 7 a 12 – řada je hotová. Ověřte v laboratoři, předvolba „2 3“.
4
Řada 10 polí, legenda 1 4, vybarvené pole 2 a křížek na poli 4. Co plyne?
Čtyřka se do polí 1–3 nevejde, leží tedy za křížkem v polích 5–10 a pole 2 patří jedničce. Okraj vybarví pole 7 a 8 (překryv čtyřky v úseku 5–10) a zakřížkuje 1 a 3, sousedy hotové jedničky.
5
Proč Okraj nemůže vybarvit pole, které v řešení prázdné je?
Řešení je jedno z umístění, která sedí se známými poli. Každý blok v něm leží mezi svými krajními polohami, takže pokrývá jejich společná pole a nepokrývá nic mimo jejich dosah. Závěry Okraje platí pro všechna taková umístění, tedy i pro řešení.
Co si odnést
  • 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.
Část IZáklady
4

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ří?“

Komu patří úsek
Klepáním na pole nastavte stav řady (neznámé → vybarvené → křížek), nebo vyberte předvolbu. Laboratoř u každého vybarveného úseku vypíše, které bloky ho mohou pokrýt, a nakreslí nejlevější a nejpravější polohu bloků, které sedí se známými poli. Řádek „závěr“ ukazuje, co z řady plyne úplným rozborem; tlačítko ho zapíše.
LABORATOŘ
Model: blok může úsek pokrýt, když existuje aspoň jedno úplné umístění všech bloků, které sedí se známými poli a ve kterém tento blok úsek pokrývá. Počítá se to stejným řešičem řady jako technika Všechna umístění (dynamické programování z kapitoly 11).
Minihra: Platí, nebo neplatí?
U každého tvrzení o přiřazování úseků zvolte, jestli platí vždy, nebo ne. Vysvětlení se ukáže po volbě. Za aspoň šest správných odpovědí ze sedmi získáte 15 XP.
MINIHRA
0 / 7
+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ří.

123456789101112stavpole 3 = 1. blok113pole 3 = 2. blok113závěr
Obr. 4.1Legenda 1 1 3, vybarvená pole 3 a 8. Pole 3 může být první, nebo druhá jednička (trojka by před sebou neměla místo pro dvě jedničky). Ať je to kterákoli, je to celý blok délky 1 – a pole 2 a 4 jsou v obou případech prázdná. Řešitel to najde jako Všechna umístění.

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.

Příklad Legenda 2 5 1, vybarvená pole 6 a 7 (12 polí)

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

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

Mistrovská pomůcka

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í

224108662 22 22 211226677662211
Obr. 4.2Hvězda po prvních pěti krocích řešitele. Řádky 4 až 7 (oranžově) dostaly pole překryvem; pátý krok, Překryv ve 3. sloupci (modře), vybarví ř6s3. Další tři sloupce doplní 6. řádek, ten se stane hotovou řadou a jeho křížky spolu s vybarvenými poli začnou sloupcům posouvat bloky: desátý krok je Okraj ve 3. sloupci.

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

1
Řada 10 polí, legenda 1 3 1, vybarvená pole 5, 6 a 7. Co plyne?
Úsek tří polí může pokrýt jen trojka a je stejně dlouhý: blok je hotový. Pole 4 a 8 jsou křížky.
2
Řada 10 polí, legenda 2 2, vybarvená pole 2 a 4. Co plyne?
Spojením přes pole 3 by vznikl úsek 3 > 2, takže pole 3 je křížek a úseky patří různým dvojkám. První dvojka musí pokrýt pole 2 a nesmí na pole 3: leží na 1–2. Druhá musí pokrýt pole 4: leží na 4–5. Řada je celá určená, zbytek jsou křížky.
3
Řada 15 polí, legenda 3 2 4, vybarvená pole 3–4, 7 a 11–12. Kterým blokům patří úseky a co z toho plyne?
Postupně trojce, dvojce a čtyřce (každý úsek má jediného kandidáta). Trojka musí pokrýt pole 3–4, začíná tedy na poli 2 nebo 3 a pole 1 nepokryje; čtyřka pokrývá 11–12 a končí nejpozději na poli 14. Pole 1 a 15 jsou křížky. Víc z řady samotné nevyplývá – poloha dvojky (6–7, nebo 7–8) se rozhodne v křížících se sloupcích.
4
Řada 12 polí, legenda 4 1, vybarvená pole 4 a 6. Patří pole 6 čtyřce?
Nevíme. Může patřit čtyřce (ta pak zabírá 3–6, nebo 4–7), nebo jedničce (čtyřka je pak 1–4 a pole 5 je mezera). Obě možnosti sedí, řada sama nic dalšího nedá. To je typická chvíle, kdy je potřeba podívat se do sloupců.
5
Proč se při přiřazování vyplatí začít krajními úseky?
Úsek nejvíc vlevo nemůže patřit bloku, před kterým by se nevešly všechny předchozí bloky – a před krajním úsekem je místa málo. Kandidátů je proto nejméně; jakmile je krajní úsek přiřazený, ubere místo vnitřním.
Co si odnést
  • Ú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í.
Část IIPokročilí
5

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

12345678stavumístění 112umístění 212umístění 312umístění 412společné
Obr. 5.1Všechna umístění legendy 1 2 v řadě 8 polí s vybarveným polem 3. První tři umístění mají jedničku na poli 3 a dvojku vpravo, čtvrté jedničku na poli 1 a dvojku na polích 3–4. Pole 2 je prázdné ve všech čtyřech – je to křížek.
Výpis všech umístění
Vyberte předvolbu nebo napište legendu a klepáním nastavte známá pole řady. Laboratoř vypíše všechna umístění bloků, která se známými poli sedí (nejvýš 40), spočítá je a ukáže pole společná všem. U předvoleb nenajdou jednodušší techniky nic, Všechna umístění ano – kromě poslední, která ukazuje prázdnou řadu.
LABORATOŘ
Model: počet umístění počítá dynamické programování (kapitola 11), výpis prochází umístění zleva doprava a vynechává ta, která odporují křížkům nebo nechávají vybarvené pole nepokryté. Společná pole jsou stejná, jaká najde úplný řešič řady v nápovědě 3D hry.
+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í

Počet umístění v prázdné řadě (odvození v kapitole 9)\[ \binom{n - s + 1}{k} = \binom{v + k}{k} \]
Tab. 5.1Počet umístění v prázdné řadě
Délka nLegendaVolnost vUmístění
103 2415
153 2 4435
205 3 4 2335
253 3 3 3101 001
201 1 1 1 1114 368
304 6 2 5101 001
Spočítáno vzorcem i dynamickým programováním, obojí dává stejná čísla.

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é.
Příklad Legenda 1 1 1, křížky na polích 1 a 10, vybarvené pole 7

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.

224108662 22 22 211226677662211
Obr. 5.2Hvězda, 14. krok řešitele: v 1. sloupci (legenda 1 1) je vybarvené pole ř4s1 a křížek ř6s1. Pole ř4s1 může být první i druhá jednička, ale v obou případech je to celý blok, takže ř3s1 a ř5s1 jsou křížky (oranžově). Žádná technika úrovně 1 ani 2 v tu chvíli v celé mřížce nic nenajde – proto má Hvězda úroveň 3.

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.
Mistrovská pomůcka

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é?“

Pozor

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.

1
Řada 11 polí, legenda 2 2, vybarvená pole 5 a 6, křížky 7 a 8. Které pole je jistě prázdné?
Úsek 5–6 je celá dvojka (první, nebo druhá). Je-li to první dvojka, druhá leží v polích 9–11; je-li druhá, první leží v polích 1–3. V obou případech je pole 4 prázdné (soused hotového bloku). Umístění jsou čtyři.
2
Řada 12 polí, legenda 1 1 1, křížky 2, 3 a 11, vybarvená pole 7 a 10. Co plyne?
Pole 7 a 10 jsou dvě z jedniček; sousedé obou jsou prázdní: 6, 8 a 9 jsou křížky. Třetí jednička je buď na poli 1, nebo v polích 4–5, nebo na poli 12 – umístění jsou čtyři.
3
Kolik umístění má legenda 2 2 2 v prázdné řadě o 12 polích?
s = 6, k = 3, C(12 − 6 + 1, 3) = C(7, 3) = 35.
4
Proč stačí vědět, že je pole v jednom umístění vybarvené a v jiném prázdné, abychom ho nechali neznámé?
Obě umístění jsou s řadou v souladu. Kdybychom pole zapsali, mohli bychom vyloučit právě to umístění, které je správné. Rozhodnout musí jiná řada, která pole kříží.
5
Je pravda, že Všechna umístění najdou vždy aspoň tolik jako Okraj?
Ano. Okraj vychází z krajních poloh, které jsou samy umístěními sedícími se známými poli; každé pole, které Okraj zapíše, vychází stejně ve všech umístěních. Opak neplatí – příklady jsou v laboratoři.
Co si odnést
  • 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.
Část IIPokročilí
6

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.

zaseknutí po úrovních 1–3268101 1 1 11111 1422324141454322předpoklad ř3s1 = vybarvené268101 1 1 11111 1422324141454322
Obr. 6.1Deštník. Vlevo stav po 25 krocích technik úrovní 1–3: neznámá zůstávají pole ř3s1, ř3s2, ř3s9, ř3s10, ř5s1, ř5s2, ř5s9 a ř5s10. Vpravo zkouška s předpokladem „ř3s1 je vybarvené“ (oranžový rámeček): šíření přidá sedm polí (oranžově) a v 5. řádku (červeně) vzniknou dvě sousední vybarvená pole ř5s9 a ř5s10, což legenda 1 1 1 1 nedovoluje.
Zkouška sporem na zaseknuté křížovce
Laboratoř nejdřív vyřeší, co jde technikami úrovně 1–3, a zastaví se. Klepněte na neznámé pole, zvolte předpoklad a stiskněte „Vyzkoušet“. Šíření doplní pole, která z předpokladu plynou (oranžově); vznikne-li spor, řada se sporem zčervená. „Zapsat závěr“ zapíše opak předpokladu, smaže zkoušku a nechá techniky řad pokračovat. „Najít pole“ ukáže, kde zkoušku najde řešitel.
LABORATOŘ
Model: šíření řeší úplným řešičem (Všechna umístění) jen řady, ve kterých přibylo pole, dokud něco přibývá nebo dokud některá řada nemá žádné umístění (spor). Řešitel zkouší pole od těch, v jejichž řádku a sloupci je nejvíc známých polí, a u každého nejdřív „vybarvené“, pak „prázdné“ – stejně jako nápověda 3D hry. Deštník i Kotva potřebují zkoušku sporem jen jednou.
Minihra: Důkaz, nebo hádání?
Rozhodněte u každého postupu, jestli je to správný logický krok, nebo chyba či hádání. Vysvětlení se ukáže po volbě. Za aspoň šest správných odpovědí ze sedmi získáte 15 XP.
MINIHRA
0 / 7
+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.
Příklad Deštník, předpoklad „ř3s1 je vybarvené“

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.

Pozor

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

Mistrovská pomůcka

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.

1
Kotva se po 30 krocích zasekne s osmi neznámými poli. Řešitel zkusí, že ř7s1 je prázdné. Šíření: 7. řádek (legenda 1 2 1) dá ř7s2, 1. sloupec dá ř9s1, 2. sloupec křížek ř9s2. Proč je to spor?
9. řádek má legendu 8, tedy jeden souvislý blok osmi polí. Je v něm ale vybarvené pole 1, křížek na poli 2 a vybarvená pole 3 až 8 – dva oddělené úseky. Žádné umístění osmičky to nesplní. Pole ř7s1 je vybarvené.
2
Předpoklad „pole je prázdné“ vedl ke sporu. Smím si nechat pole, která jsem při zkoušce odvodil?
Ne. Byla odvozená z předpokladu, o kterém teď víte, že neplatí. Zapište jen „pole je vybarvené“ a pokračujte znovu běžnými technikami – mnohá pole vyjdou jinak.
3
Obě hodnoty pole vedly bez sporu k zaseknutí, ale v obou vyšlo pole ř2s5 vybarvené. Co smím zapsat?
Pole ř2s5 je vybarvené (dvojí zkouška): jedna z obou hodnot zkoumaného pole platí a obě vedou ke stejnému závěru. O zkoumaném poli samotném nevíte nic.
4
Proč řešitel zkouší pole s nejvíc známými poli v řádku a sloupci?
V takových řadách je méně umístění, a předpoklad je proto zúží výrazněji. Šíření je kratší a spor, pokud existuje, se objeví dřív. Je to heuristika – nezaručuje nejkratší cestu, ale v praxi funguje.
5
Je zkouška sporem povolená v „čistých“ křížovkách, které se mají dát vyřešit bez hádání?
Ano, je to logický důkaz. Rozdíl mezi úrovněmi je v pohodlí: zkouška sporem vyžaduje držet v hlavě (nebo na papíře jinou barvou) celou větev úvah. Proto ji průvodce i 3D hra řadí až do úrovně 4.
Co si odnést
  • 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.
Část IIPokročilí
7

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

463 1 2 1 36461 141 161 161 2 181 1101418201 1 1 1 1 1 1 1 1 1111312435631552711461135611342711531547443131212
Obr. 7.1Maják 20 × 20 – vyřešená křížovka s legendou (vlastní motiv průvodce, jediné řešení, úroveň 1). Silnější čáry po pěti polích usnadňují počítání pozic. Nejmenší volnost mají spodní řádky a sloupce věže uprostřed – tam řešení začíná.
Tři strategie na velké mřížce
Vyberte křížovku a strategii výběru řad. Posuvníkem procházíte zápisy jeden po druhém (modrý pruh je řada, ze které zápis vzešel), „Přehrát“ je ukáže jako animaci. Pohled „pořadí“ obarví pole podle toho, kdy byla rozhodnuta. Graf dole porovná, jak rychle roste podíl rozhodnutých polí s počtem prohlédnutých řad u všech tří strategií.
LABORATOŘ
Model: každá prohlédnutá řada je jeden úplný rozbor řady (Všechna umístění). Fronta zkoumá na začátku všechny řady a pak jen ty, ve kterých přibylo pole. Procházení dokola zkoumá řádky a sloupce stále dokola. Strategie „nejméně umístění“ vybírá řadu, která má se známými poli nejméně umístění (počítá se dynamickým programováním). Všechny tři dojdou ke stejnému obrázku.
Barevná řada
Zadejte bloky jako „3a 2b 3a“: číslo je délka, písmeno barva (a oranžová, b modrá, c zelená). Laboratoř nakreslí krajní polohy a překryv, kde má každé pole barvu svého bloku. Zaškrtnutím přepnete na černobílé pravidlo (mezera mezi každými dvěma bloky) a uvidíte, jak se změní volnost.
LABORATOŘ
Model: povinná mezera je jen mezi sousedními bloky stejné barvy. Krajní polohy se počítají stejně jako v černobílé řadě, jen s těmito mezerami; překryv bloku vybarví pole jeho barvou.
+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“.

Tab. 7.1Strategie výběru řad: kolik řad se prohlédne do vyřešení
KřížovkaŘadFronta změněných řadProcházení dokolaNejméně umístění
Maják 20 × 2040736958
Hrad 15 × 1530414129
Kohout 15 × 153011210399
Hvězda 10 × 1020588780
Spočítáno laboratorní implementací strategií; prohlédnutá řada = jeden úplný rozbor řady, která ještě není vyřešená.

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).
Mistrovská pomůcka

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:

Volnost barevné řady (g = počet sousedních dvojic bloků stejné barvy)\[ v = n - (s + g) \]
12345678910nejvíc vlevo323nejvíc vpravo323překryv
Obr. 7.2Barevná řada 10 polí: oranžová 3, modrá 2, oranžová 3. Povinná mezera tu není žádná, volnost je 10 − 8 = 2. Překryv vybarví oranžově pole 3 a 8; modrá dvojka není delší než volnost a nedá nic. V černobílé křížovce by tytéž délky měly volnost 0 a řada by byla určená celá.

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.

Pozor

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.

1
Barevná řada 12 polí: 2 oranžová, 3 modrá, 3 modrá, 2 zelená. Jaká je volnost?
Stejnou barvu mají jen dvě modré trojky: g = 1. Volnost 12 − (10 + 1) = 1; překryv vybarví 1 + 2 + 2 + 1 = 6 polí.
2
Barevná řada 15 polí: 5 oranžová, 4 modrá, 5 zelená. Kolik polí vybarví překryv?
Povinná mezera žádná, volnost 15 − 14 = 1. Bloky dají 4 + 3 + 4 = 11 polí. V černobílé verzi (volnost −1) by se bloky do řady ani nevešly.
3
Proč strategie „nejméně umístění“ vede na Majáku, i když je dražší na přemýšlení?
Prohlíží jen řady, které s velkou pravděpodobností něco dají, a nezkoumá zbytečně řady s velkou volností. Výběr řady ale něco stojí – počítač musí pro každou řadu spočítat umístění, člověk musí odhadnout volnost. V tabulce se počítají jen úplné rozbory řad.
4
Na velké křížovce vám v jedné řadě nevychází součet: vybarveno je o jedno pole víc, než říká legenda. Co dělat?
Chyba je v některém poli této řady nebo v řadě, která ho kříží. Projděte pole řady a u každého si ověřte, ze které úvahy vzniklo. Ve 3D hře pomůže vrácení tahů nebo kontrola chyb.
Co si odnést
  • 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.
Část IIPokročilí
8

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

10 × 105 × 5
Obr. 8.1Kruh převedený do mřížky. Pole se vybarví, když tvar pokrývá aspoň polovinu jeho plochy (měřeno 16 body uvnitř pole). V rozlišení 10 × 10 je kruh poznat, v 5 × 5 z něj zbude kosočtverec. Obě mřížky mají jediné řešení a úroveň 1.
Z tvaru do mřížky
Vyberte tvar a velikost mřížky. Laboratoř tvar převede do polí a hned ověří, kolik řešení legenda má, a když jedno, jakou úroveň technik potřebuje. Pole, ve kterých se dvě řešení liší, orámuje červeně. Klepnutím na pole obrázek upravíte a kontrola proběhne znovu.
LABORATOŘ
Model: tvar je zadaný rovnicí v jednotkovém čtverci, každé pole se měří 4 × 4 body a vybarví se při pokrytí aspoň 50 %. Počet řešení zjišťuje prohledávání se šířením řad (kapitola 11) s limitem uzlů; úroveň určuje lidský řešitel z kapitol 2–6. Za zmínku stojí obličej 12 × 12 (dvě řešení), hvězda 8 × 8 a měsíc 12 × 12 (jediné řešení, ale úroveň 4).
+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í

řešení A1 11 11 121 22401121řešení B1 11 11 121 22401121
Obr. 8.2Dva obrázky 5 × 5 se stejnou legendou. Liší se ve čtyřech červeně orámovaných polích v rozích obdélníku (řádky 1 a 3, sloupce 4 a 5): v řešení A jsou vybarvená ř1s4 a ř3s5, v řešení B ř1s5 a ř3s4. Všechny řádky i sloupce mají v obou stejné bloky. Jiné řešení legenda nemá.

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

Pozor

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

Tab. 8.1Náhodné obrázky 10 × 10: podíl s jediným řešením podle hustoty
Hustota pJediné řešení95% intervalÚroveň 1Úroveň 2Úroveň 3Úroveň 4
0,32,0 %1,6–2,5 %0261143
0,416,9 %15,8–18,1 %643270168
0,553,6 %52,1–55,2 %1311 81271132
0,683,7 %82,5–84,8 %1 3331 992814
0,797,1 %96,5–97,6 %3 34953103
0,899,3 %99,0–99,5 %3 9502300
Simulace: pro každou hustotu 4 000 náhodných obrázků, každé pole vybarvené nezávisle s pravděpodobností p; jednoznačnost ověřena prohledáváním, úrovně řešitelem průvodce (počty obrázků s jediným řešením). Interval je Wilsonův.

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

Mistrovská pomůcka

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.

1
Proč je úhlopříčná čára přes celou mřížku špatný motiv?
Každý řádek i sloupec má legendu 1. Takové legendě odpovídá každá permutace – u mřížky 10 × 10 je to 10! = 3 628 800 obrázků.
2
Obličej 12 × 12 má dvě řešení lišící se v polích ř3s2, ř3s10, ř9s2, ř9s4, ř11s4 a ř11s10. Co uděláte?
Změním jedno z rozdílových polí a ověřím znovu. Přidat ř3s2 nebo ubrat ř3s10 či ř11s4 pomůže hned; po změně ř9s2 nebo ř9s4 má obrázek zase dvě řešení. Proto se ověřuje po každé úpravě. Vyzkoušejte v laboratoři: tvar obličej, velikost 12.
3
Při jaké hustotě má náhodný obrázek 10 × 10 jediné řešení zhruba v polovině případů?
Kolem p = 0,5 (53,6 % v simulaci). Při 0,7 už je to 97,1 %, při 0,3 jen 2,0 %.
4
Proč je hvězda 8 × 8 úrovně 4, ale hvězda 10 × 10 úrovně 1?
Rastrování v menším rozlišení vytvoří jiné bloky – kratší, s rohy, které tvoří těžko rozhodnutelné dvojice. Obtížnost není vlastnost tvaru, ale konkrétní mřížky; proto se hodnotí až hotová křížovka.
5
Je negativ obrázku s jediným řešením také jednoznačný?
Ne vždy. Negativ má úplně jinou legendu. Z motivů průvodce vedou k více řešením negativy Plachetnice, Kočky a Zajíce.
Co si odnést
  • 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í.
Část IIIMistr a věda
9

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.

12345678■■○○32■○■○32■○○■32○■■○32○■○■32○○■■32
Obr. 9.1Hvězdičky a přepážky: šest umístění legendy 3 2 v osmi polích. Vlevo je každé umístění zapsané jako pořadí dvou bloků ■ (každý i se svou povinnou mezerou za sebou, kromě posledního) a dvou volných polí ○. Umístění odpovídá výběru míst pro bloky mezi čtyřmi symboly: C(4, 2) = 6.
Kalkulačka umístění a legend
Nastavte délku řady a napište legendu. Laboratoř spočítá umístění vzorcem i dynamickým programováním, počet všech legend řady dané délky a počet všech řad. Graf v logaritmickém měřítku ukazuje, jak tato čísla rostou s délkou (svislá čára je zvolená délka). Do 12 umístění je vypíše.
LABORATOŘ
Model: C(n − s + 1, k) je kombinační číslo; dynamické programování počítá umístění nezávisle (kapitola 11), shoda je kontrolou vzorce. Počet legend F(n + 2) zahrnuje i legendu 0. Čísla v grafu jsou přesná, jen osa je logaritmická.
Simulace: kolik obrázků má jediné řešení
Laboratoř vyrobí zvolený počet náhodných obrázků n × n, v nichž je každé pole vybarvené s danou pravděpodobností, a u každého zjistí, jestli má jeho legenda jediné řešení. U jednoznačných určí i úroveň technik. Výsledek ukáže podíl s 95% intervalem a graf úrovní.
LABORATOŘ
Model: obrázky jsou nezávislé, generátor je deterministický s náhodným semínkem; jednoznačnost se ověřuje prohledáváním se šířením řad s limitem 20 000 uzlů (obrázky nad limitem se počítají zvlášť jako přerušené). Interval je Wilsonův. Výsledky v tabulkách teorie jsou z větší simulace se 4 000 obrázky na velikost.
+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:

Počet umístění v prázdné řadě\[ \binom{v + k}{k} = \binom{n - s + 1}{k} \]

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:

Počet různých legend řady délky n\[ 1 + F(1) + F(2) + \dots + F(n) = F(n + 2) \]
Tab. 9.1Legendy a řady
Délka nRůzných legend F(n + 2)Různých řad 2ⁿŘad na jednu legendu
513322,5
101441 0247,1
151 59732 76820,5
2017 7111 048 57659,2
25196 41833 554 432170,8
302 178 3091 073 741 824492,9
Spočítáno skriptem; pro n ≤ 12 ověřeno i výčtem všech řad.
Mistrovská pomůcka

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

Tab. 9.2Všechny obrázky n × n: kolik má jediné řešení
nObrázků 2n²Různých zadáníS jediným řešenímPodílNejvíc obrázků na jedno zadání
1222100 %1
216151487,50 %2
351244538475,00 %6
465 53658 19652 36279,90 %24
533 554 43228 781 82025 309 57575,43 %120
668 719 476 736–49 745 060 66972,39 %–
n ≤ 5: úplný výčet skriptem průvodce (každý obrázek, jeho legenda, počet obrázků se stejnou legendou). Počty jednoznačných obrázků souhlasí s posloupností OEIS A242876; hodnota pro n = 6 je převzatá z ní (výpočet B. Felgenhauera). „Zadání“ = různé dvojice legend řádků a sloupců.

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

0 %25 %50 %75 %100 %15101520velikost mřížky n × núplný výčet (n ≤ 6)simulace, 4 000 obrázků na velikost53,6 %44,1 %31,6 %15,7 %
Obr. 9.2Podíl obrázků n × n s jediným řešením. Modře přesné hodnoty z úplného výčtu (n ≤ 6), oranžově simulace (4 000 náhodných obrázků s hustotou 0,5 na každou velikost, svislé čárky jsou 95% intervaly). Pro n = 6 se simulace (72,8 %) shoduje s přesnou hodnotou (72,39 %) v rámci intervalu.
Tab. 9.3Simulace: náhodné obrázky n × n s hustotou 0,5
nJediné řešení95% intervalÚroveň 1Úroveň 2Úroveň 3Úroveň 4
672,8 %71,4–74,2 %1 8241 0032561
767,8 %66,3–69,2 %1 2041 4032678
862,8 %61,3–64,3 %6891 6894095
1053,6 %52,1–55,2 %1311 81271132
1244,1 %42,6–45,7 %101 50193161
1531,6 %30,2–33,1 %0957129178
2015,7 %14,6–16,9 %0282156190
Pro každou velikost 4 000 obrázků s pevnými semínky; úrovně jsou počty obrázků s jediným řešením. U 37 obrázků 20 × 20 prohledávání překročilo limit; nejsou započítané mezi jednoznačné, takže skutečný podíl pro n = 20 může být nejvýš asi o 0,9 procentního bodu vyšší. Mezi jednoznačnými obrázky nebyl žádný „mimo škálu“.

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.

Pozor

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.

1
Kolik umístění má legenda 2 2 2 v prázdné řadě o 15 polích?
C(15 − 6 + 1, 3) = C(10, 3) = 120.
2
Vypište všechny legendy řady délky 3 a ověřte vzorec F(n + 2).
0, 1, 2, 3, 1 1 – celkem 5 = F(5). Legenda 1 2 ani 2 1 se do tří polí nevejde.
3
Kolik různých legend má řada délky 15?
F(17) = 1 597, zatímco řad je 32 768.
4
Kolik obrázků 4 × 4 má stejné zadání jako obrázek, který má v každém řádku i sloupci právě jedno vybarvené pole?
Všechny permutační matice 4 × 4: 4! = 24. To je zároveň největší skupina obrázků 4 × 4 se společným zadáním.
5
Simulace pro 6 × 6 dala 72,8 % s intervalem 71,4–74,2 %, přesná hodnota je 72,39 %. Co z toho plyne?
Přesná hodnota leží v intervalu, simulace je s ní v souladu. Interval vyjadřuje nejistotu z konečného počtu pokusů; se 4 000 obrázky je široký asi ± 1,4 procentního bodu. Víc o intervalech najdete v průvodci Statistika.
Co si odnést
  • 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.
Část IIIMistr a věda
10

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.

Srdce1 1553124442stejné součty2553124442
Obr. 10.1Vlevo Srdce, vpravo jiný obrázek se stejnými součty řádků (2, 5, 5, 3, 1) i sloupců (2, 4, 4, 4, 2). Legendy se liší jen v horním řádku: 1 1 proti 2. To stačí – součty obrázky nerozliší, legenda ano.
Součty, nebo legenda?
Klepnutím na pole kreslete obrázek nebo vyberte předvolbu. Laboratoř spočítá, kolik obrázků má stejné součty řádků a sloupců a kolik stejnou legendu, a modře orámuje jednu záměnu 2 × 2, pokud v obrázku je. Vyzkoušejte, jak se čísla mění, když záměnu „rozbijete“.
LABORATOŘ
Model: obrázky se stejnými součty počítá rekurze po řádcích s pamětí zbývajících součtů sloupců; obrázky se stejnou legendou prohledávání se šířením řad (do 5 000 řešení). Záměna 2 × 2 je čtveřice polí v rozích obdélníku, kde jsou vybarvená právě dvě protilehlá.
+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í

Galeova–Ryserova podmínka (k = 1, …, n)\[ \sum_{j=1}^{k} c_j \le \sum_{i=1}^{m} \min(r_i, k) \]

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

před záměnoupo záměně
Obr. 10.2Záměna: v rozích obdélníku jsou vybarvená dvě protilehlá pole. Když je prohodíme s prázdnými, v každém řádku i sloupci zůstane stejný počet vybarvených polí.

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.

Tab. 10.1Kolik obrázků má stejné součty a kolik stejnou legendu
ObrázekStejné součtyStejná legenda
Srdce 5 × 531
Domek 5 × 551
Kytka 5 × 5151
Hříbek 5 × 511
vzor se záměnou 5 × 5 (laboratoř)90610
vzor se záměnou 6 × 6 (laboratoř)71 100288
úhlopříčka 6 × 6720720
Spočítáno laboratorními funkcemi. U úhlopříčky nemá legenda (samé jedničky) žádnou informaci navíc, a proto se obě čísla rovnají 6! = 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

Z historie

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.

Pozor

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

1
Existuje obrázek 3 × 3 se součty řádků 2, 2, 0 a součty sloupců 3, 1, 0?
Ne. Součty sedí (4 = 4), ale pro k = 1: nejplnější sloupec chce 3 pole, řádky mu mohou dát nejvýš min(2,1) + min(2,1) + min(0,1) = 2. Sloupec se třemi poli potřebuje tři neprázdné řádky.
2
Existuje obrázek 3 × 3 se součty řádků 3, 1, 1 a sloupců 3, 1, 1?
Ano: k = 1: 3 ≤ 1 + 1 + 1; k = 2: 4 ≤ 2 + 1 + 1; k = 3: 5 ≤ 3 + 1 + 1. Je to „písmeno L“: plný první řádek a plný první sloupec. Záměnu nemá, je tedy jediný.
3
Proč obrázků se stejnou legendou nemůže být víc než obrázků se stejnými součty?
Každý obrázek se stejnou legendou má i stejné součty (součet řady = součet čísel legendy). Skupina „stejná legenda“ je tedy částí skupiny „stejné součty“.
4
Křížovka 50 × 50 má úroveň 4. Je pro počítač těžká?
Není. Úrovně 1–4 jsou polynomiální: úplné rozbory řad a zkoušky sporem s jedním polem proběhnou na takové mřížce ve zlomku sekundy. Těžké jsou jen křížovky, které vyžadují vnořené předpoklady.
5
Co tvrdí výsledek Uedy a Nagaa o křížovce 15 × 15 z novin?
Nic konkrétního. NP-úplnost se týká chování v nejhorším případě, když velikost roste nade všechny meze. Konkrétní křížovka konečné velikosti může být – a obvykle je – snadná.
Co si odnést
  • 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í.
Část IIIMistr a věda
11

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

fronta řadna začátku všechnyřešič řadyvšechna umístění (DP)nová pole?zapsat do mřížkykřížící řadypřidat do frontyfronta prázdnázkouška sporem / větveníanodalší řadanic nezbývá
Obr. 11.1Smyčka šíření. Na začátku jsou ve frontě všechny řady. Řešič řady vezme řadu z fronty, a když zapíše nová pole, přidá do fronty řady, které tato pole kříží. Když je fronta prázdná a mřížka není hotová, nastupuje zkouška sporem nebo větvení.
Řešič krok za krokem
Vyberte křížovku a způsob řešení. „Lidský“ v každém kroku volí nejjednodušší techniku z kapitol 2–6 a pojmenuje ji; „strojový“ bere řady z fronty a každou rozebere úplně. „Krok“ provede jeden zápis, „Do konce“ dořeší. Lupa ukazuje řadu posledního kroku před ním a po něm, deník posledních osm kroků.
LABORATOŘ
    Model: oba způsoby používají stejný řešič řady (dynamické programování z odstavce 11.1). Lidský řešič je stejný jako v hero, laboratořích a nápovědě 3D hry; strojový je klasická fronta řad. Když se fronta vyprázdní, oba použijí zkoušku sporem s jedním polem.
    +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

    Prefixová tabulka\[ F[i][x] = \text{prvních } i \text{ bloků lze umístit do polí } 1, \dots, x \text{ tak, aby sedily se známými poli} \]

    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.
    Tab. 11.1Tabulka F pro legendu 2 1 v prázdné řadě 6 polí (1 = jde)
    i \ x0123456
    0 bloků1111111
    blok 20011111
    bloky 2 10000111
    Vypočteno řešičem průvodce. Například F[2][4] = 1: obě čísla legendy se vejdou do prvních čtyř polí (##.#), do tří už ne.

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

    Příklad Kontrola jednoznačnosti v číslech

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

    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.

    1
    V Tab. 11.1 je F[1][3] = 1. Co to znamená?
    První blok (dvojka) jde umístit do prvních tří polí: jako ##. nebo .##. Hodnota F[1][1] = 0, protože do jednoho pole se dvojka nevejde.
    2
    Proč řešič řady nevypisuje umístění?
    Umístění může být astronomicky mnoho – C(n − s + 1, k). Tabulka F a G má jen (k + 1)(n + 1) hodnot. Odpovídá na otázku „může pole být vybarvené / prázdné?“ přímo, bez výčtu.
    3
    Proč nezáleží na pořadí řad ve frontě pro výsledek šíření?
    Každá úvaha jen přidává jistá pole a víc známých polí nikdy neubere žádnou dřívější úvahu. Všechna pořadí proto skončí ve stejném stavu – největším, kam se dá řadami dojít (pevném bodě). Liší se jen délka cesty.
    4
    Jak počítač zjistí, že křížovka má jediné řešení?
    Prohledáváním s návratem, které se zastaví po nalezení druhého řešení. Najde-li jen jedno a prohledá všechny větve, je řešení jediné.
    5
    Lidský řešitel vyřeší Hvězdu za 47 kroků, strojový za 32 zápisů a prohlédne 58 řad. Proč se čísla liší?
    Strojový řešitel rozebírá každou řadu úplně, takže jeden zápis obsahuje všechno, co z řady plyne. Lidský zapisuje po technikách a jedna řada se mu může vrátit několikrát (nejdřív překryv, později okraj). Počet kroků měří styl řešení, ne jeho obtížnost.
    Co si odnést
    • Ú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.
    Část IIIMistr a věda
    12

    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.

    1 nápadsilueta, kontrast2 mřížkarastr, velikost3 kontrolajediné řešení?4 hodnocenítechniky, krokyúpravazměnit pole v rozdílech5 zkouškavyřeší ji člověk?neznovu ověřitano
    Obr. 12.1Postup tvorby křížovky. Kontrola a úprava se točí v kruhu, dokud legendě neodpovídá jediný obrázek. Hodnocení obtížnosti a zkouška řešením člověkem přicházejí až potom.
    Malíř křížovek
    Vyberte velikost. Začnete předlohou: srdce 5 × 5, smrček 10 × 10, nebo hrad 15 × 15. Klepnutím pole vybarvíte nebo vymažete a legenda se hned přepočítá. „Ověřit“ zjistí, jestli má legenda jediné řešení, a ohodnotí obtížnost stejně jako hra. Pokud má legenda víc řešení, orámuje červeně pole, ve kterých se dvě nalezená řešení liší. „Negativ“ prohodí vybarvená a prázdná pole.
    LABORATOŘ
    Model: legenda se z obrázku počítá přímo, po řadách. Jednoznačnost ověřuje prohledávání s návratem, které skončí po nalezení druhého řešení. Limit je 60 000 uzlů; když ho prohledávání překročí, laboratoř ohlásí „nezjištěno“. Obtížnost určuje lidský řešitel z kapitoly 11 a úroveň je nejtěžší technika, kterou použil (Tab. 12.2). Odměnu dostanete za vlastní nebo upravený obrázek aspoň 10 × 10 s alespoň 20 vybarvenými poli a jediným řešením.
    +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

    Příklad

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

    pás: 34 řešení22222222211222222222+1 pole: jediné řešení22322222211322222222
    Obr. 12.2Vlevo šikmý pás široký dvě pole v mřížce 10 × 10. Jeho legendě (řádky 2 … 2 1, sloupce 1 2 … 2) odpovídá 34 obrázků. Červeně jsou orámována pole, ve kterých se liší první dvě nalezená řešení. Vpravo je stejný pás s jedním přidaným polem ř3s2 (oranžově). Řádek 3 a sloupec 2 mají teď legendu 3 a řešení je jediné. Lidský řešitel ale potřebuje zkoušku sporem: úroveň 4, 39 kroků.

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

    Tab. 12.1Šikmý pás 10 × 10: které změny jednoho pole vedou k jedinému řešení
    Šířka pásuŘešení před opravouZměn s jediným řešením (ze 100)z toho úroveň 4z toho mimo škálu
    2 pole3410 (vždy přidání pole)64
    3 pole816 (10 přidání, 6 ubrání)160
    Spočítáno řešičem průvodce: každé ze 100 polí bylo jednou přepnuto (vybarvené ↔ prázdné), jednoznačnost ověřena prohledáváním do druhého řešení a úroveň lidským řešitelem. „Mimo škálu“ znamená, že řešitel nevystačí ani se zkouškou sporem jednoho pole.
    Pozor

    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

    Tab. 12.2Úrovně podle technik
    ÚroveňTechnikyKapitola
    1Překryv, Hotová řada2
    2+ Nedosažitelná pole, Okraj3, 4
    3+ Všechna umístění5
    4+ Zkouška sporem6
    mimo škálujediné řešení, ale řešitel nevystačí ani se zkouškou sporem jednoho pole11
    3D hra má obtížnosti 1 až 5. Obtížnosti 1 až 3 odpovídají úrovním technik, obtížnosti 4 a 5 přidávají zkoušku sporem na větších mřížkách. Hra nabízí jen křížovky s jediným řešením, které jdou vyřešit logikou.
    Tab. 12.3Obrázky průvodce: velikost, úroveň a použité techniky
    ObrázekMřížkaVybarvenoÚroveňKrokůTechniky (počet kroků)
    Srdce5 × 516110Překryv 5, Hotová řada 5
    Domek5 × 513111Překryv 5, Hotová řada 6
    Hříbek5 × 51318Překryv 4, Hotová řada 4
    Kytka5 × 59110Překryv 4, Hotová řada 6
    Šipka5 × 59110Překryv 4, Hotová řada 6
    Hrnek8 × 837114Překryv 7, Hotová řada 7
    Rybka8 × 833117Překryv 9, Hotová řada 8
    Plachetnice10 × 1045121Překryv 10, Hotová řada 11
    Smrček10 × 1046118Překryv 9, Hotová řada 9
    Sova10 × 1058141Překryv 26, Hotová řada 15
    Kočka10 × 1062133Překryv 19, Hotová řada 14
    Jablko10 × 1070126Překryv 17, Hotová řada 9
    Zajíc10 × 1068126Překryv 14, Hotová řada 12
    Klíč10 × 1026228Překryv 11, Hotová řada 16, Okraj 1
    Tulipán10 × 1046226Překryv 12, Hotová řada 12, Okraj 2
    Noty10 × 1043232Překryv 18, Hotová řada 12, Okraj 2
    Ptáček10 × 1043236Překryv 17, Hotová řada 13, Okraj 6
    Hvězda10 × 1050347Překryv 24, Hotová řada 12, Okraj 8, Všechna umístění 3
    Deštník10 × 1039433Překryv 16, Hotová řada 11, Okraj 5, Zkouška sporem 1
    Kotva10 × 1040438Překryv 16, Hotová řada 15, Nedosažitelná pole 2, Okraj 4, Zkouška sporem 1
    Hrad15 × 15156252Překryv 32, Hotová řada 19, Okraj 1
    Kohout15 × 1579263Překryv 30, Hotová řada 22, Nedosažitelná pole 1, Okraj 10
    Slon15 × 15119146Překryv 23, Hotová řada 23
    Maják20 × 20144156Překryv 26, Hotová řada 30
    Spočítáno lidským řešitelem průvodce. Každý obrázek má ověřeně jediné řešení. Úroveň 1 má 15 z 24 obrázků, úroveň 2 jich má 6, úroveň 3 jeden (Hvězda) a úroveň 4 dva (Deštník a Kotva).

    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.

    Mistrovská pomůcka

    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í

    1
    Napište legendu řádku 110111001011 (1 = vybarvené pole).
    Úseky jedniček mají délky 2, 3, 1 a 2, legenda je 2 3 1 2. Mezery (1, 2 a 1 pole) legenda neukládá.
    2
    Kontrola našla dvě řešení, která se liší ve čtyřech polích v rozích obdélníku. Jak křížovku opravit?
    Přidat nebo ubrat jedno z těchto polí (případně sousední pole ve stejné řadě) tak, aby se změnila legenda řady, ve které záměna leží. Pak znovu ověřit, protože oprava může otevřít jinou nejednoznačnost nebo zvýšit úroveň.
    3
    Maják 20 × 20 má úroveň 1 a 56 kroků, Kotva 10 × 10 má úroveň 4 a 38 kroků. Která křížovka je těžší?
    Podle měřítka průvodce i hry je těžší Kotva, protože bez zkoušky sporem ji nevyřešíte. Maják je delší, ale každý jeho krok je překryv nebo hotová řada.
    4
    Proč nemá smysl kreslit obrázek z tenké úhlopříčky?
    Každá řada má legendu 1. Stejnou legendu má každý obrázek, který má v každém řádku i sloupci právě jedno vybarvené pole (permutační matice). Mřížce n × n tak odpovídá n! obrázků, pro 10 × 10 jich je 3 628 800. Ani pás široký dvě pole nestačí: má 34 řešení.
    5
    Šestiletý luštitel chce hned řešit Velkou křížovku 25 × 25. Co mu poradíte?
    Začít mřížkou 5 × 5 s někým dospělým a krátce. Velká křížovka má 625 polí a dlouhé legendy. Přirozený postup vede přes 8 × 8 a 10 × 10.
    Co si odnést
    • 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.
    PřílohaA

    Slovníček

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

    PřílohaB

    Vzorce a přehledy

    Techniky podle úrovní

    Tab. B.1Techniky průvodce a 3D hry
    TechnikaCo děláÚroveňKapitola
    Překryvvybarví pole, která blok pokrývá v nejlevější i nejpravější poloze12
    Hotová řadakdyž v řadě stojí všechny bloky legendy, zakřížkuje zbytek12
    Nedosažitelná polezakřížkuje pole, kam žádný blok nedosáhne, a mezery kratší než blok, který by do nich patřil23
    Okrajvybarvené pole u kraje nebo u křížku přitlačí blok a dovybarví ho23
    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ůnik35
    Zkouška sporempředpoklad v jednom poli vede přes křížící se řady ke sporu, platí tedy opak46
    Lidský řešitel průvodce v každém kroku použije techniku nejnižší úrovně, která v některé řadě něco zapíše. V rámci jedné úrovně volí řadu, ve které zapíše nejvíc polí. Zkoušku sporem s jedním polem použije, až když žádná technika řady nic nepřinese. Úroveň křížovky je nejvyšší úroveň použité techniky. Když řešitel neuspěje ani se zkouškou sporem, je křížovka „mimo škálu“ (kapitoly 11 a 12).

    Vzorce na jednom místě

    Volnost řady délky n, legenda b₁ … b_k se součtem s (kap. 1)\[ v = n - (s + k - 1) \]
    Nejlevější a nejpravější začátek bloku j (kap. 2)\[ L_j = 1 + \sum_{i
    Překryv bloku j (kap. 2)\[ \text{jistá pole } R_j, \dots, L_j + b_j - 1, \qquad \text{jejich počet } \max(0,\; b_j - v) \]
    Počet umístění v prázdné řadě (kap. 5, 9)\[ \binom{n - s + 1}{k} = \binom{v + k}{k} \]
    Volnost barevné řady, g = počet sousedních dvojic bloků stejné barvy (kap. 7)\[ v = n - (s + g) \]
    Počet legend řady délky n, F = Fibonacciho čísla (kap. 9)\[ 1 + F(1) + F(2) + \dots + F(n) = F(n + 2), \qquad \frac{2^n}{F(n+2)} \approx \frac{\sqrt{5}}{\varphi^2}\Big(\frac{2}{\varphi}\Big)^{n} \approx 0{,}854 \cdot 1{,}236^{\,n} \]
    Galeova–Ryserova podmínka: řádkové součty r_i, sloupcové c_j seřazené sestupně, Σ r = Σ c (kap. 10)\[ \sum_{j=1}^{k} c_j \le \sum_{i=1}^{m} \min(r_i, k), \qquad k = 1, \dots, n \]
    Úhlopříčka v mřížce n × n: všechny řady mají legendu 1 (kap. 10, 12)\[ \text{počet řešení} = n! \]
    Řešič řady, prefixová tabulka (kap. 11)\[ F[i][x] = \big(F[i][x-1] \wedge x \ne \blacksquare\big) \ \vee\ \big(\text{blok } b_i \text{ může končit na } x \ \wedge\ F[i-1][x - b_i - 1]\big) \]

    Počty na jednom místě

    Tab. B.2Čísla z kapitol průvodce
    ÚdajHodnotaKde
    legenda 1 1 1 1 1 v prázdné řadě 20 polí: umístění4 368kap. 5, 11
    řada 10 polí: různých legend / různých řad144 / 1 024kap. 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 × 2053,6 % / 15,7 %kap. 9
    obrázky 10 × 10 s jediným řešením při hustotě 0,3 / 0,72,0 % / 97,1 %kap. 8
    vzor 6 × 6 se záměnou: obrázků se stejnými součty / se stejnou legendou71 100 / 288kap. 10
    úhlopříčka 10 × 10 / pás široký 2 pole / pás široký 3 pole: řešení3 628 800 / 34 / 8kap. 10, 12
    Maják 20 × 20: prohlédnuté řady při frontě / procházení dokola / nejméně umístění73 / 69 / 58kap. 7
    24 obrázků průvodce: úroveň 1 / 2 / 3 / 415 / 6 / 1 / 2kap. 12
    negativy 24 obrázků průvodce s jediným řešením21kap. 8, 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

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

    Interaktivní průvodce Malované křížovky (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.