Zakódovaný obrázek

(přesměrováno z Nonogram)
Na tento článek je přesměrováno heslo Nonogram. Možná hledáte: Nomogram.

Zakódovaný obrázek (nonogram, kódovaný obrázek či malovaná křížovka) je logický hlavolam, při kterém je okolo mřížky umístěná legenda s čísly a pomocí nich lze získat obrázek. Každé číslo v legendě určuje počet za sebou následujících čtverečků stejné barvy.

Vyluštěný zakódovaný obrázek, kde řešením je písmeno W

V Česku se zakódované obrázky objevují od první půlky 90. let v časopise Panorama křížovek, kde byly otiskovány i nejednoznačně zadané obrázky vyžadující hádání. V dalším desetiletí se objevují specializované tituly, vycházející v periodě čtvrtletní, dvouměsíční i měsíční. Vyšlo i několik jednorázových knižních publikací. V české distribuční síti převažují tituly původem ze Slovenska (odkud pochází označení Malované křížovky) a jejich distribuce probíhá pouze přes některé prodejce tisku.

Princip zakódovaných obrázků

editovat
Každé číslo v legendě určuje počet za sebou následujících čtverečků stejné barvy.  
Mezi jednotlivými čísly je vždy minimálně jeden prázdný čtvereček.  
Čísla v legendě jsou již uspořádána ve správném pořadí.  
Různě-barevná čísla legendy mohou a nemusí být oddělena prázdným čtverečkem.  

Postup krok za krokem

editovat
 

Řada 2: Součet čísel legendy (3,1) s 1 prázdným čtverečkem (barva pozadí) mezi nimi je rovný 5 čtverečkům, které jsou k dispozici.

 

Sloupec 5: Číslo legendy 1 je už v mřížce. Zbylé čtverečky daného sloupce můžeme vyplnit barvou pozadí.

 

Řada 3: V mřížce zůstaly už jen 4 čtverečky, do kterých můžeme umístit číslo legendy 4.

 

Sloupec 4: Číslo legendy 1 je už v mřížce. Zbylé čtverečky daného sloupce můžeme vyplnit barvou pozadí.

 

Řady 4/5: Součet čísel legendy (1,1) s 1 prázdným čtverečkem mezi nimi je rovný 3 čtverečkům, které jsou k dispozici.

 

Sloupec 2: Na doplnění čísla legendy 3 zůstává už jen 1 čtvereček. Křížovka je vyřešená.

 
Postup luštění

Seznam typů zakódovaných obrázků

editovat
  • Klasické (Nonogram, Griddler) – čtvercová mřížka s černobílým obrázkem
  • Trojúhelníkové – na rozdíl od klasického zakódovaného obrázku obsahují 4 typy diagonálně rozpůlených polí, které zlepšují rozpoznání obrázku
    • mezi číslem a trojúhelníkem nemusí být mezera
  • Barevné – barva buněk je zadána barvou číselného zadání, možné je i nebílé pozadí zadané v levém horním rohu
  • Multiobrázky – výsledný obrázek je složen z několika menších částí, které se luští zvlášť
  • Triddler – trojúhelníková mřížka, číselné zadání se vyskytuje ze tří stran
  • Bludiště – obrázek vznikne vybarvením cesty skrz bludiště
  • Mozaika – každé číslo označuje počet vybarvených polí v nejbližším okolí (0–9), princip podobný hře Hledání min
  • ParX (Link-a-Pix) – spojují se dvojice čísel (kromě čísla 1), spojnice tvoří obrázek
  • Cross-a-Pix – mřížka je rozdělena do segmentů, které jsou buď plné nebo prázdné
    • čísla na krajích uvádí počet vybarvených polí v daném sloupci nebo řádku bez ohledu na mezery
    • číselné zadání může být doplněno počtem segmentů v daném sloupci nebo řádku
  • Sym-a-Pix – mřížka je vyplněna body označujícími těžiště bodově symetrických obrazců, barva bodu určuje barvu obrazce

Zakódované obrázky v elektronické podobě

editovat

Zakódované obrázky existují v digitální podobě na internetu od konce devadesátých let 20. století. Existuje několik webových stránek, kde se setkává komunita luštitelů a kromě luštění vytvářejí obrázky pro ostatní. Tyto stránky umožňují hodnotit obtížnost a krásu vyluštěného obrázku nebo porovnávat čas potřebný k řešení.

Zakódované obrázky existují v různých podobách i jako aplikace pro dotykové telefony a tablety. Při luštění zakódovaných obrázků je výhodné mít přehled o celé mřížce a vidět stále legendu, proto je pro luštění větších obrázků vhodnější tablet než mobilní telefon.

Zakódované obrázky v informatice

editovat

Řešení zakódovaných obrázků je NP-úplný problém.[1] To znamená, že existence polynomiálního algoritmu řešícího malovanou křížovku implikuje P = NP. Přesto platí, že existují efektivní algoritmy pro řešení některých typů obrázků.[2]

Reference

editovat
  1. UEDA, Nobuhisa; NAGAO, Tadaaki. NP-completeness results for NONOGRAM via Parsimonious Reductions. Technical Report, Department of Computer Science, Tokyo Institute of Technology: [s.n.], 1996. 
  2. BRUNETTI, Sara; DAURAT, Alain. An algorithm reconstructing convex lattice sets. Theoretical Computer Science. 2003, s. 35–57. Dostupné online. DOI 10.1016/S0304-3975(03)00050-1. 

Externí odkazy

editovat