Mitől lesz egy nonogram könnyű vagy nehéz
Egy nonogram „nehézsége” nem csak azon múlik, mekkora a rács. Egy 20×20-as szinte magától megoldódhat, míg egy 10×10-es minden négyzetért megdolgoztathat. Amit a nehézséget valójában meghatározza, az az, hogy milyen mélyen kell gondolkodnod, hogy megtaláld a következő kényszerű lépést. Ez az útmutató lebontja, mi hajtja valójában — és megoszt egy meglepő felfedezést a kutatásból arról, milyen ritkán van szükség egy tisztességes rejtvényben bármi ravaszra.
A méret csak a része ennek
Egy nagyobb rács valóban több nyomon követendő sort és több keresztellenőrzést jelent, így a nagy rejtvények tovább tartanak. De önmagában a hossz nem tesz nehézzé egy sort — egy 20 széles sor egyetlen nagy tömbbel triviális, míg egy rövid sor, tele apró tömbökkel és szűk résekkel, valódi gondolkodást igényelhet. A méret sokkal inkább arra hat, mennyi ideig tart egy rejtvény, mint arra, milyen nehéz az egyes lépések.
Valójában arról szól, milyen mélyre nyúlnak a következtetések
A nehézség leghűbb mértéke az, milyen fajta gondolkodást követel a rejtvény. A legkönnyebb rejtvények „soronként megoldhatók”: egyszerre egy sort vagy oszlopot nézve befejezheted őket, kitöltve, amit az az egyetlen vonal kikényszerít, és soha nem kell két vonalat egyszerre a fejedben tartanod. A legtöbb szelíd rejtvény pontosan ilyen.
A nehezebb rejtvények megkövetelik, hogy információt kombinálj — hogy észrevedd: egy négyzet állapota csak akkor válik kényszerűvé, amikor egy sort és egy oszlopot együtt, vagy vonalak kis csoportját egyszerre veszed figyelembe. Minél mélyebbre kell nyúlnia ennek a kombinációnak, mielőtt a következő négyzet kényszerűvé válik, annál nehezebbnek érződik a rejtvény, méretétől függetlenül.
Mit mond a kutatás a találgatásról
Itt jön a megnyugtató rész. A nonogramok megoldásáról szóló tudományos munka (Batenburg and Kosters, 2012) megmérte, mennyi gondolkodást igényelnek valójában az egyértelműen megoldható rejtvények. Az egyszerű soronkénti megoldáson túl a következő lépés egy jól meghatározott, még mindig determinisztikus technika — vonalpárok kombinálása —, és kimerítő felsorolásuk azt találta, hogy a nem egyszerű rejtvények 93.8–95.5%-a pontosan ezzel megoldható, mindenféle találgatás nélkül.
Még megdöbbentőbb: az összes egyértelműen megoldható rejtvénynek csak nagyjából 0.06–0.14%-a igényel bármit is ezen a vonalpár-gondolkodáson túl. Más szóval a jól megszerkesztett nonogramok elsöprő többsége — beleértve minden nehezet, amellyel a szokásos játék során találkozol — tiszta, korlátozott logikával megoldható. A valódi próbálgatás elenyészően ritka egy tisztességes rejtvényben, ezért olyan megbízható tanács a „soha ne találgass”.
A „nehéz” itt formális jelentéssel is bír
Mindezek alatt egy elméleti eredmény húzódik meg. Annak eldöntése, hogy egy tetszőleges sor- és oszlopnyomokból álló halmaznak van-e egyáltalán bármilyen megoldása, bizonyítottan NP-teljes (Ueda and Nagao, 1996) — ugyanaz a bonyolultsági osztály, mint a hírhedten makacs problémáké, például az utazóügynök-problémáé. Egyszerűen fogalmazva: senki sem ismer olyan módszert, amely minden elképzelhető nonogramot gyorsan megold, és a legrosszabb esetekben a szükséges munka robbanásszerűen nő a rács növekedésével.
Ez ijesztően hangzik, amíg észre nem veszed a különbséget „minden elképzelhető nonogram” és „a nonogramok, amelyeket az emberek valóban közreadnak” között. Az NP-teljességi eredmény tetszőleges, ellenséges nyomhalmazokról szól — amelyek közül soknak egyáltalán nincs megoldása, vagy több is van. Egy valódi rejtvényt fordítva építenek fel: egy képből indul ki, és csak akkor kerül közlésre, ha pontosan egy olyan megoldása van, amelyet a logika ténylegesen el tud érni. Ezért állják meg a helyüket az előző szakasz számai a gyakorlatban — és ezért szinte biztosan tisztességes az előtted lévő rejtvény, még ha brutálisnak is érződik.
A sűrűség és az alak is számít
A következtetési mélységen túl néhány felszíni jellemző is billenti a nehézséget. A nagyon ritka képek (többnyire üresek) és a nagyon sűrűk (többnyire kitöltöttek) általában könnyebbek, mert a szélsőségek korán sok kényszerű négyzetet adnak. A legkacifántosabb rejtvények többnyire középen helyezkednek el, kitöltött és üres kiegyensúlyozott keverékével, és rengeteg rövid, széttördelt tömbbel, amelyek ellenállnak a gyors nyitólépéseknek. Egy tiszta, felismerhető motívum is segít a megoldónak tájékozódni, még ha nem is változtatja meg a mögöttes logikát.
Hogyan jelöljük a könnyűt, a közepest és a nehezet
Ezen az oldalon egy rejtvény besorolása abból ered, milyen mélyen nyúlik a megoldásához szükséges gondolkodás, kombinálva olyan alakstatisztikákkal, mint hogy mennyire kitöltött a rács. A soronként megoldható rejtvények a könnyűbe kerülnek; azok, amelyek valódi vonalak közötti kombinációt igényelnek, a nehéz felé mozdulnak; bármit, ami találgatást igényelne, közlés helyett egyenesen elutasítunk. A teljes folyamatot a „hogyan készítjük a nonogramjainkat” oldal írja le — de a rövid változat az, hogy itt a nehézséget mérjük, nem találgatjuk.