Nonogramo
Nonogramoj estas bildaj enigmoj. Oni plenigas ĉelojn en matrico laŭ numeroj flankaj por riveli kaŝitan bildon. En tiaj enigmoj la numeroj indikas kiom da linioj de konektitaj vicoj de plenaj ĉeloj (tradicie nigraj) estu en ĉiu vico horizontala aŭ vertikala. Ekzemple indiko "4 8 3" signifas ke estas tri sekcioj de 4, 8, kaj 3 plenaj ĉeloj, en tiu ordo, kun almenaŭ unu malplena ĉelo inter sekvaj sekcioj.
| nonogramo | ||
|---|---|---|
|
| ||
| NP-kompleta videoludo • logika enigmo | ||
La enigmoj kutime estas nigra kaj blanka, sed eblas havi kolorojn. Tiuokaze, la numeraj indikoj mem estas koloraj por indiki la koloron de ĉeloj en sekcio. Du nombroj kun malsamaj koloroj povus havi aŭ ne havi spacon inter si. Ekzemple nigra 4 apud ruĝa 2 povus signifi 4 nigraj ĉeloj, iom da malplenaj ĉeloj, kaj 2 ruĝaj ĉeloj, aŭ povus signifi 4 nigraj ĉeloj kaj tuj poste 2 ruĝaj.
Ne estas teoria limo pri grandeco, sed en praktiko eldonitaj tiaj enigmoj ne pli grandas ol 100x100. La matrico ne nepre estas kvadrata.
Nomoj redakti
Nonogramoj havas multajn nomojn eĉ ene de unu lingvo. Ekzemple: Paint by Numbers, Griddlers, Pic-a-Pix, Picross, Pixel Puzzles, Crucipixel, Edel, FigurePic, Grafilogika, Hanjie, Illust-Logic, Japanese Crosswords, Japanese Puzzles, Kare Karala!, Logic Art, Logic Square, Logicolor, Logik-Puzzles, Logimage, Obrazki logiczne, Zakódované obrázky, Maľované krížovky, Oekaki Logic, Oekaki-Mate, Paint Logic, Shchor Uftor, Gobelini and Tsunami. Alia popular nomo estas "Paint by Sudoku" (Pentrado laŭ Sudoko), kvankam tio sensencas ĉar ili ne rilatas al Sudoko.
Historio redakti
En 1987, Non Ishida (Non Iŝida), japana grafika redaktoro, gajnis konkurson en Tokio per kreo de kradaj bildoj per lumoj en ĉielskrapaj konstruaĵoj. Samtempe koincide profesia japana enigmisto Tetsuya Nishio (Tetsuja Niŝio) inventis tiajn enigmojn.
En 1988 Non Ishida eldonis 3 tiajn enigmojn en Japanujo laŭ la nomo "fenestraj artaj enigmoj".
En 1990, James Dalgety de Britujo inventis la nomon "Nonograms" laŭ la nomo de kreinto Non Ishida, kaj The Sunday Telegraph ekeldonis ilin ĉiusemajne.
En 1993, Non Ishida eldonis la unuan libron de nonogramoj en Japanujo. La Sunday Telegraph eldonis libron "Book of Nonograms". Nonogramoj ekeldoniĝis ankaŭ en Svedujo, Usono, Sud-Afriko, ktp.
En 1995, programoj pri la enigmoj ekaperis en ludaj komputiloj kiel Game Boy kaj en aliaj plastaj ludiloj. La enigmoj plipopulariĝadis en Japanujo kaj aperis pliaj eldonejoj kaj monataj revuoj, kiuj enhavis ĝis 100 enigmoj monate.
En 1998, la Sunday Telegraph faris konkurson por elekti novan nomon por siaj enigmoj. "Griddlers" gajnis.
En 1999, "Paint by numbers" eldoniĝis de Sanoma Uitgevers en Nederlando, Puzzler Media en Britujo, kaj Nikui Rosh Puzzles en Israelo.
Nuntempe revuoj kun nonogramoj eldoniĝis en Usono, Britujo, Germanujo, Nederlando, Italujo, Hungarujo, Finnlando, Pollando, kaj multaj aliaj landoj. Krome estas diversaj retpaĝaroj kun kaj pri la enigmoj.
Solvaj teĥnikoj redakti
Por solvi enigmon, oni devas eltrovi kiuj ĉeloj estos plenaj kaj ĉiuj estos malplenaj. Trovi malplenajn ĉelojn same gravas kiel trovi plenajn dum la solvado, ĉar la spacoj helpas decidi kie sekcioj de plenaj ĉeloj povas esti. Solvantoj kutime uzas punkton aŭ ikson or marki sciite malplenajn ĉelojn.
Gravas neniam diveni laŭ intuicio. Oni nur marku ĉelojn pri kies staton logiko pruvas, ĉar eĉ unu eraro disvastiĝos tra la matrico kaj ruinigos la solvon, kaj ofte ne evidentiĝas ĝis poste, kiam malfacilas lokalizi la eraron kaj korekti ĝin. Nur spertuloj kutime povas ripari tiajn ruinigitajn enigmojn.
La kaŝita bildo mem ne rolas en la solvado. Eĉ se ŝajnas evidenta laŭ la aperanta bildo de iu ĉelo estos plena (aŭ malplena), estas riske fidi tion. Tamen la bildo fojfoje utilas por rimarki evidentan fuŝon.
Simplaj enigmoj ofte solveblas per simpla rezonado bazita nur sur unu vico post la alia sendepende, trovante kiel eble plej multajn sciatajn ĉelojn en unu vico, poste en alia vico. Traki unu vicon post alia sendepende povas sufiĉe solvi tiajn simplajn enigmojn.
Pli malfacilaj enigmoj povas postuli diversajn pli komplikajn teĥnikojn kiuj uzas pli ol unu vicon samtempe. Tia rezonado ofte dependas de nekonsekvenco: "Se tiu ĉelo estus plena, estus nekonsekvenco en ia alia ĉelo kiu povus esti nek plena nek malplena, do tiu unua ĉelo devas esti malplena." Pli spertaj solvantoj povas vidi pli distancajn konsekvancojn.
Simplaj ĉeloj redakti
En la komenco de solvado simpla metodo sufiĉas por decidi kiel eble plej multajn ĉelojn. La metodo analizas ĉiujn eblajn lokojn por sekcioj de plenaj ĉeloj. Ekzemple, en horizontalo de 10 ĉeloj kun nur unu numero 8, la sekcio de 8 plenaj ĉeloj povus esti:
- ĉe la dekstra rando, lasante 2 malplenajn ĉelojn maldekstre;
- ĉe la maldekstra rando, lasante 2 malplenajn ĉelojn dekstre;
- ie inter la du ekstremoj.
Rezulte la plena sekcio certe inkluzivas la mezajn 6 ĉelojn.
La sama logiko aplikeblas kiam estas pli ol unu numero en vico. Ekzemple en horizontalo de 10 ĉeloj kun numeroj 4 kaj 3, la sekcioj de plenaj ĉeloj povus esti:
- kiel eble plej maldekstre, lasante 2 spacojn dekstre;
- kiel eble plej dekstre, lasante 2 spacojn maldekstre;
- ie interne.
Rezulte la 1a sekcio de 4 ĉeloj certe inkluzivas la 3an kaj 4an ĉelojn, kaj la 2a sekcio de 3 ĉeloj certe inkluzivas la 8an ĉelon. Do oni povas plenigi la 3an, 4an kaj 8an ĉelojn. Notu ke tiu teĥniko rajtigas plenigi ĉelon nur se la sama sekcio ĉiam kovras ĝin. En tiu ekzemplo la 2 sekcioj ambaŭ povas kovri la 6an ĉelo, kaj ne estas sciate ĉu tiu ĉelo estos plena aŭ ne.
Simplaj spacoj redakti
Tiu metodo serĉas spacojn kiuj ne atingeblas de iu ajn sekcioj de plenaj ĉeloj. Ekzemple se horizontalo de 10 ĉeloj havas plenajn 4an kaj 8an ĉelojn kaj numerojn 3 kaj 1, la 3-sekcio inkluzivas la 4an ĉelon kaj la 1-sekcio estas la 9a ĉelo.
Unue la 1-sekcio jam estas kompleta, do devas esti malplenaj ĉeloj tuŝantaj ĝin ambaŭflanke, t.e. la 8a kaj 10a ĉeloj estas certe malplenaj.
Due la 3a sekcio povas esti nur ie inter la 2a kaj 6a ĉeloj, ĉar ĝi ĉiuokaze devas inkluzivi la 4an ĉelon. Tial la 1a kaj 7a ĉeloj certe estas malplenaj.
Notu ke se estas aliaj numeroj kun nesciataj lokoj, oni estu zorga ne tro supozi aferojn!
Devigado redakti
Per tiu teĥniko malplenaj ĉeloj povas devigi sekciojn aperi en certaj subvicoj. Malplena ĉelo en la mezo de vico povas devigi longan sekcion esti en unu flanko aŭ la alia. Krome subvico de malsciataj ĉeloj ĉirkaŭitaj de du malplenaj ĉeloj povas esti tro malgranda por iu ajn sekcio, do markeblas kiel malplena.
Ekzemple, horizontalo de 10 ĉeloj kun malplenaj 5a kaj 7a ĉeloj, kaj numeroj 3 kaj 2:
- La 3-a sekcio devas esti maldekstre, ĉar ne povas sidi inter ie alia.
- La truo de la 6a ĉelo estas tro malgranda por sidigi la 2- aŭ 3-sekcion, do povas esti markita malplena.
- Finfine la 2-sekcio devas inkluzivi la 8an ĉelo laŭ la teĥniko Simplaj ĉeloj.
Gluo redakti
Fojfoje estas ĉelo apud la rando kiu ne estas pli distance de la rando ol la longo de la unua nombro-indiko. Tiuokaze, la rando etendas la unuan sekcion tra tiu ĉelo kaj dekstren.
Ekzemple, kun horizontalo de 10 ĉeloj kun plena 3a ĉelo kaj numero 5, la 5 iras tra la 3a ĉelo al la 4a kaj 5a ĉeloj pro la rando.
Notu: tiu teĥniko povas utili en la mezo de vico for de la enigmaj randoj.
- Malplena ĉelo povus roli kiel rando tiusence, se la unua sekcio estas devigita dekstre de tiu malplena ĉelo.
- Tiu "unua" sekcio povas fakte esti posta sekcio, se ĉiuj antaŭaj sekcioj estas certe maldekstre de la deviga malplena ĉelo.
Kunigado kaj Disigado redakti
Proksimaj plenaj ĉeloj fojfoje povas esti kunigitaj (per plenaj ĉeloj inter ili) aŭ disigita per iu malplena ĉelo inter ili. Kiam 2 plenaj ĉeloj havas nemarkitan ĉelon inter ili, tiu ĉelo:
- estu malplena, se kunigo de la ĉeloj produktus tro longan sekcion;
- estu plena, se disigo de la ĉeloj produktus to malgrandan sekcion kiu ne havas sufiĉe da liberaj ĉeloj ĉirkaŭ si por etendiĝi.
Ekzemple, en horizontalo de 15 ĉeloj kun plenaj 3a, 4a, 6a, 7a, 11a, 13a ĉeloj kaj numeroj 5, 2, 2:
- la indiko 5 kunigas la unuajn 2 sekciojn en unu pli longan sekcion, ĉar malplena 5a ĉelo kreus subvicon kun nur 4 ĉeloj, kiu ne sufiĉe longus por la 5-sekcio;
- la 2-indikoj disigas la dekstrajn du sekciojn per malplena 12a ĉelo, ĉar plena 12a ĉelo produktus sekcion de almenaŭ 3 plenaj ĉeloj, kiu ne eblas tie.
- Notu: La bildo ankaŭ montras kiel la 2-indikoj povas esti plu kompletigitaj. Tio ne estas per la teĥniko Kunigado kaj Disigado, sed Gluo.
Interpunkcio redakti
Gravas marki malplenajn ĉelojn je ambaŭ ekstromoj de certe finitaj plenaj sekcioj. Tia interpunkciado kutime kondukas al pli da Devigado kaj kutime necesas por fini la enigmon. Notu: Antaŭaj ekzemploj ne faras tion nur por resti simplaj.
Hidrargo redakti
Hidrargo estas specifa kazo de la teĥniko Simplaj spacoj. (La nomo aludas kiel hidrargo iras for de flankoj de ujo.)
Se estas ĉelo en horizontalo kiu havas saman kvanton de ĉeloj maldekstre de si kiel la nombro de la unua sekcio, la unua ĉelo estu malplena. Alie la unua sekcio ne sidus maldekstre de la plena ĉelo; ĝi devas inkluzivi tiun ĉelon, lasanta la unuan ĉelon malplena. Krome kiam tiu plena ĉelo estas efektive la maldekstra ekstremo de plena sekcio, estos pli da spacoj je la komenco de la horizontalo.
Nekonsekvencoj redakti
Iuj pli malfacilaj enigmoj povas postuli pli altnivelan rezonadon. Kiam ĉiuj jam menciitaj teĥnikoj ne plu helpas, serĉado de nekonsekvencoj povas helpi. Nespertaj solvantoj eble uzu forviŝeblan krajonon (aŭ alian koloron) por malfari notojn. La procezo inkluzivas:
- Supozu ke iu nemarkita ĉelo estas plena.
- Uzu la simplajn metodojn por solvi kiel eble plej multe.
- Se vi trovos eraron, la provita ĉelo certe estu malplena. (Se vi no trovo eraron, vi tute solvos la enigmon baze de tiu supozo!)
Kompreneble vi povas ankaŭ supozi ke iu nemarkita ĉelo estas malplena.
En tiu ekzemplo oni provas ĉelon en la 1a horizontalo, kiu kondukas al malplena ĉelo je la komenco de tiu vico. Tiu malpleno tiam devigas plenan ĉelon en la 1a vertikalo, kiu gluas al sekcio de 3 ĉeloj en la 4a horizontalo. Sed tio ne eblas ĉar la 3a vertikalo ne permesas plenan ĉelon tie, do tiu nekonsekvenco pruvas ke la provita ĉelo ne povas esti plena, do devas esti malplena.
Malfacilaĵo de tiu metodo estas kutime ne evidentas kiu nemarkita ĉelo provindas. Kutime nur kelkaj ĉeloj donas fruan frukton, dum la aliaj kondukas al longa vojo kun neklara rezulto. La plej provindaj ĉeloj ofte:
- havas multajn markitajn najbarojn;
- proksimas al randoj aŭ sekcioj de malplenaj ĉeloj;
- estas en vicoj kun multaj markitaj ĉeloj.
Pli profunda rekurso redakti
Iuj enigmoj (ekzemple konata kiel Old tree (Malnova arbo)) povas postuli pli profundan serĉadon por trovi nekonsekvencojn. Tiu kutime ne eblas simple per krajono kaj papero pro la tro multaj branĉaj ebloj serĉendaj.
Pluraj vicoj redakti
Fojfoje rezonado pri kelkaj vicoj povas konduki al solva paŝo sen nekonsekvenco kaj sen pli profunda rekurso. Sed trovi tiajn vicgrupojn ofte tiom malfacilas kiom trovi nekonsekvencon.
Pluraj solvoj redakti
Ekzistas enigmoj kun pli ol unu solvo. Simpla ekzemplo estas ŝaktabulo. En tiaj enigmoj, ĉiu solvo estas "ĝusta" laŭ difino, sed eblas ke iuj ne donas sencan rezultan bildon.
Nonogramoj ka komputado redakti
Solvado de nonogramoj estas problemo NP-kompleta. [1] Tio implicas ke ne ekzistas algoritmo kiu povas efike (en polinoma tempo) solvi ĉiujn nonogramajn enigmojn krom se P = NP.
Tiu teoria komplekseco kutime ne gravas por eldonitaj enigmoj. Tiuj estas konstruitaj kaj kontrolitaj, do ili solveblas de homoj. Ĉiu enigmo solvebla de homo en mallonga tempo ankaŭ solveblas rapide de komputilo.
Krome iuj subspecoj de nonogramoj solveblas en polinoma tempo, ekzemplo tiuj en kiu ĉiu vico havas nur unu sekcion de plenaj ĉeloj. [2]
Eksteraj fontoj redakti
- ↑ http://www.phil.uu.nl/~oostrom/oudonderwijs/cki20/02-03/japansepuzzles/complexity.ps[rompita ligilo]
- ↑ Brunetti, Sara; Daurat, Alain (2003), "An algorithm reconstructing convex lattice sets", Theoretical computer science 304 (1–3): 35–57, doi:10.1016/S0304-3975(03)00050-1; Chrobak, Marek; Dürr, Christoph (1999), "Reconstructing hv-convex polyominoes from orthogonal projections", Information Processing Letters 69 (6): 283–289, doi:10.1016/S0020-0190(99)00025-3; Kuba, Attila; Balogh, Emese (2002), "Reconstruction of convex 2D discrete sets in polynomial time", Theoretical Computer Science 283 (1): 223–242, doi:10.1016/S0304-3975(01)00080-9.
Eksteraj ligiloj redakti
http://www.comp.lancs.ac.uk/~ss/nonogram/faq Arkivigite je 2009-02-27 per la retarkivo Wayback Machine estas en Esperanto kaj la angla, kun programoj por solvi nonogramojn.