Japonská křížovka

Japonský hlavolam (též japonská křížovka , japonská kresba , nonogram ) je hlavolam , ve kterém na rozdíl od běžných křížovek nejsou zakódována slova , ale obrázek.

Popis

Obrázky jsou zakódovány čísly umístěnými vlevo od řádků a také nad sloupci. Počet čísel ukazuje, kolik skupin černých (nebo jejich vlastní barvy, u barevných křížovek ) buněk je v odpovídajícím řádku nebo sloupci, a samotná čísla ukazují, kolik sloučených buněk každá z těchto skupin obsahuje (např. tři čísla - 4, 1 a 3 znamenají, že v tomto řádku jsou tři skupiny: první - ze čtyř, druhá - z jedné, třetí - ze tří černých buněk). V černobílé křížovce musí být skupiny odděleny alespoň jednou prázdnou buňkou, barevně toto pravidlo platí pouze pro jednobarevné skupiny a vícebarevné skupiny mohou být umístěny blízko (prázdné buňky mohou být i na okraje řad). Je nutné určit umístění skupin buněk.

Navzdory vysoké prevalenci v tuto chvíli neexistuje obecný názor na požadavky na japonské křížovky . Hlavní názory se scvrkají na různé kombinace následujících tvrzení:

1. Správně složená hádanka by měla mít pouze jedno řešení.
2. Velikost křížovky (na šířku a výšku) musí být násobkem 5 (aby pomocná mřížka mohla pole rozdělit na bloky 5x5).
3. Počet barev použitých v barevné japonské křížovce by měl být omezen a samotné barvy by měly být od sebe snadno rozlišitelné.
4. Barva pozadí (barva prázdných políček hracího pole) japonské křížovky musí být bílá.
5. Křížovka musí mít logicky dosažitelné řešení (přičemž není jasné, která z metod řešení patří do této kategorie). Křížovka , která má jedno řešení, ke kterému se lze dostat pouze hrubou silou , není považována za japonskou křížovku (kvůli astronomickému množství kombinací, které člověk není schopen seřadit).
6. Je nepřijatelné mít řádky a sloupce bez vyplněných buněk (a tedy bez čísel ).
7. Je nepřijatelné mít řádky a sloupce, ve kterých není „co hádat“ (obvykle to znamená absenci jednoduchých prázdných buněk mezi skupinami čísel různých barev a absenci dvojitých prázdných buněk mezi skupinami stejné barvy. v tomto případě mají skupiny čísel jedinou možnost umístění, protože zabírají veškerý dostupný prostor).

Historie

Japonské hlavolamy se objevily v Japonsku na konci 20. století , k jejich autorství se hlásí dva lidé .

Jednou z nich je Non Ishida (石田の ん), ilustrátorka a grafická editorka , která tvrdila, že již v roce 1970 vytvořila nonogramy jako prostředek komunikace mezi lidmi a zvířaty . Non Isis věřili, že zvířata jsou velmi inteligentní stvoření, ale kvůli nedostatku prostředků komunikace mezi lidmi a zvířaty člověk pozemské tvory podceňuje. V důsledku její vědecké práce se podle Isis zrodily nonogramy (angl. Nonogram) (NON + diaGRAM) - pole s černobílými čtverci [ 2 ] .

V roce 1987 se Non Ishida přihlásil do soutěže Window Art . Účastníci museli vytvořit obrázek na mrakodrapu pomocí oken, rozsvítit nebo zhasnout světla v místnostech. V noci byly výsledky sečteny a práce Isis obsadila první místo. The Tale of the Bamboo Cutter je  japonská legenda z 8. století , která byla prvním nonogramem , který viděla široká veřejnost .

V roce 1988 , inspirovaný vítězstvím v soutěži v kreslení oken , Non Ishida publikuje tři hádanky v Japonsku pod názvem " Window Art Puzzles " [2] .

Ve stejné době japonský autor hlavolamů Tetsuya Nishio ( japonsky 西尾徹也) přichází s hlavolamy " Malí podle čísel " a publikuje je v další publikaci [2] .

Zpočátku neogramy nevzbudily mezi milovníky hádanek velký zájem, protože nikdo nechápal, jak tato hádanka je, jak ji vyřešit.

Japonské hlavolamy získaly širokou popularitu v letech 1989-1990 poté, co byly publikovány v britských novinách The Telegraph , James Delgety , známý britský milovník hlavolamů, přesvědčil vedení novin, aby vydávalo japonské hlavolamy týdně. Brzy se také dozvěděli o nonogramech nebo griddlerech (ang. Griddlers ) v Rusku , zde se jim říkalo "japonské křížovky" nebo "japonské hlavolamy".

Technika řešení

Algoritmus pro luštění japonské křížovky pomocí příkladu „srdce“ uvedeného níže je následující. Nejjednodušší je začít s těmi linkami, které budou přemalovány. V našem příkladu jsou pouze tři takové řady po 9 buňkách (obr. 1).

Druhý řádek se skládá ze dvou skupin po 4 buňkách. V tomto případě bude mezera mezi skupinami v 5. sloupci. Poté se vyplní 4 buňky ve sloupcích 1 a 9, což je podle podmínek nutné.

Všechny ostatní buňky v těchto sloupcích jsou rozhodně bez stínování. Jsou označeny křížky (obr. 2). Dále je v řádku s číslem 7 překresleno všech sedm zbývajících buněk. V prostředním sloupci se vytvořil začátek skupiny - 4 ze 7 požadovaných podmínkou. Tato skupina končí.

V řádku s číslem 1 je již buňka a všechny ostatní jsou označeny křížkem. V řadě s číslem 3 zůstane definitivně volná druhá a osmá buňka a v řadě se skupinami 2-2 se definitivně přemaluje třetí a sedmá buňka (obr. 3).

Poté se doplní sloupce 3 a 7, spojí se tři buňky z řádku s číslem 5, přemalují se dvě zbývající buňky v řádku s číslem 3. Zbývá přemalovat první buňky ve druhém a osmé sloupce (obr. 4).

"Srdce" (příklad)

• Rýže. jeden

• Rýže. 2

• Rýže. 3

• Rýže. čtyři

Počítačové řešení

Japonská křížovka je NP-úplná , neexistuje žádné polynomiální časové řešení , pokud P≠NP .

Pokud jsou však jako japonské křížovky klasifikovány pouze křížovky „mající jedno řešení, dosažitelné pouze logickou cestou“, pak takové křížovky nelze přiřadit k NP-dokončeným úkolům, protože kdykoli při luštění křížovky máme informace, které jednoznačně naznačují které buňky lze dále otevřít. Na tom jsou vlastně založeny všechny způsoby luštění křížovek, které člověk používá (s výjimkou metody „pokus-omyl“ [3] ).

Ve své nejjednodušší podobě (čtverec 8 × 8) byla japonská křížovka nabídnuta v roce 1992 účastníkům Mezinárodní olympiády v informatice (IOI) pod názvem „ostrovy v moři“.

Barevné japonské křížovky

Hlavním rozdílem mezi barevnými japonskými hádankami a černobílými hádankami je přítomnost dvou nebo více barev buněk (barva pozadí se nebere v úvahu jako samostatná barva), což zase přináší jeden významný rozdíl při řešení hádanky . Je třeba pamatovat na to, že v barevném puzzle nesmí být bílé buňky mezi skupinami buněk různých barev.

Pokud se tedy v černobílém hlavolamu při řešení předpokládá, že skupina stínovaných buněk je nutně oddělena od druhé alespoň jednou nevystíněnou buňkou a bere to v úvahu při výpočtu, pak to nelze provést v barevné puzzle, protože skupiny buněk mohou být umístěny blízko sebe.

Také ve zvláště složitých barevných křížovkách je navíc nutné vzít v úvahu barvy na průsečíku buněk.

Jinak je řešení založeno na stejných principech jako u černobílých hlavolamů:

• stanovení ploch zaručeně zastíněných buněk;
• určení oblastí, které zaručeně neobsahují zastíněné buňky.

Barevné japonské křížovky jsou obecně mnohem jednodušší na luštění než ty černobílé.

Poznámky

1. ↑ 1 2 „Logickou cestou“ se rozumí jakékoli metody řešení japonských křížovek, s výjimkou metody „pokus-omyl“
2. ↑ 1 2 3 Historie japonských křížovek | Stránky o Japonsku: moderní Japonsko  (ruština)  ? . Staženo: 27. února 2021.  (neurčitý)
3. ↑ Metoda „pokus-omyl“ je určena speciálně pro křížovky, které nepatří do skupiny „mají jedno řešení, dosažitelné pouze logickým způsobem“, a proto nemusí obsahovat informace, které jednoznačně označují buňky, které mají být v další tah

Odkazy

• Metody řešení japonských křížovek

V bibliografických katalozích	LNB : 000321927