Japanilainen ristisanatehtävä

Japanilainen palapeli (myös japanilainen ristisanatehtävä , japanilainen piirustus , nonogrammi ) on palapeli , jossa, toisin kuin tavalliset ristisanat , ei koodata sanoja , vaan kuva.

Kuvaus

Kuvat on koodattu numeroilla, jotka sijaitsevat rivien vasemmalla puolella ja myös sarakkeiden yläpuolella. Numeroiden määrä osoittaa, kuinka monta mustaa (tai oman värin, väriristisanatehtävässä ) soluryhmää on vastaavalla rivillä tai sarakkeessa, ja itse luvut osoittavat, kuinka monta yhdistettyä solua kukin näistä ryhmistä sisältää (esimerkiksi joukko kolme numeroa - 4, 1 ja 3 tarkoittaa, että tällä rivillä on kolme ryhmää: ensimmäinen - neljästä, toinen - yhdestä, kolmas - kolmesta mustasta solusta). Mustavalkoisessa ristisanatehtävässä ryhmät on erotettava vähintään yhdellä tyhjällä solulla, värillisesti tämä sääntö koskee vain yksivärisiä ryhmiä ja moniväriset ryhmät voivat sijaita lähekkäin (tyhjät solut voivat olla myös rivien reunat). On tarpeen määrittää soluryhmien sijainti.

Korkeasta yleisyydestä huolimatta japanilaisten ristisanatehtävien vaatimuksista ei tällä hetkellä ole yleistä mielipidettä . Tärkeimmät mielipiteet tiivistyvät seuraavien lausuntojen erilaisiin yhdistelmiin:

1. Oikein laaditussa pulmapelissä tulee olla vain yksi ratkaisu.
2. Ristisanan koon (leveys ja korkeus) on oltava 5:n kerrannainen (jotta apuruudukko voi jakaa kentän 5x5 lohkoon).
3. Japanilaisessa ristisanatehtävässä käytettävien värien määrää tulee rajoittaa ja itse värien tulee olla helposti erotettavissa toisistaan.
4. Japanin ristisanatehtävän taustavärin (pelikentän tyhjien solujen väri) on oltava valkoinen.
5. Ristisanatehtävässä tulee olla loogisesti saavutettavissa oleva ratkaisu (vaikka ei ole selkeää määritelmää sille, mitkä ratkaisutavat kuuluvat tähän luokkaan). Ristisanatehtävää , jolla on yksi ratkaisu, joka voidaan saavuttaa vain raa'alla voimalla , ei pidetä japanilaisena ristisanatehtävänä (johtuen tähtitieteellisestä määrästä yhdistelmiä, joita ihminen ei pysty lajittelemaan).
6. Ei voida hyväksyä rivejä ja sarakkeita ilman täytettyjä soluja (ja vastaavasti ilman numeroita ).
7. Ei voida hyväksyä rivejä ja sarakkeita, joissa ei ole "mitään arvattavaa" (yleensä tämä tarkoittaa yksittäisten tyhjien solujen puuttumista eriväristen lukuryhmien välillä ja kaksinkertaisten tyhjien solujen puuttumista samanväristen ryhmien välillä. tässä tapauksessa numeroryhmillä on ainoa vaihtoehto sijainnin määrittämiseen, koska ne vievät kaiken käytettävissä olevan tilan).

Historia

Japanilaiset palapelit ilmestyivät Japanissa 1900- luvun lopulla , kaksi henkilöä väittää kirjoittajuutensa .

Yksi heistä on Non Ishida (石田の ん), kuvittaja ja graafinen toimittaja , joka väitti jo vuonna 1970 luoneensa nonogrammeja ihmisten ja eläinten välisen kommunikoinnin välineeksi . Non Isis uskoi, että eläimet ovat erittäin älykkäitä olentoja, mutta ihmisten ja eläinten välisten viestintävälineiden puutteen vuoksi ihminen aliarvioi maallisia olentoja. Hänen tieteellisen työnsä tuloksena Isisin mukaan syntyi nonogrammeja (eng. Nonogram) (NON + kaavio) - kenttiä, joissa on mustavalkoinen neliö [ 2 ] .

Vuonna 1987 Non Ishida osallistui Window Art - kilpailuun . Osallistujien piti luoda kuva pilvenpiirtäjälle ikkunoiden avulla, sytyttää tai sammuttaa valot huoneissa. Yöllä tulokset laskettiin yhteen, ja Isisin työ sijoittui ensimmäiseksi. The Tale of the Bamboo Cutter on 800-luvun  japanilainen legenda , joka oli ensimmäinen suuren yleisön näkemä nonogrammi .

Vuonna 1988 Non Ishida julkaisee Japanissa kolme palapeliä " Window Art Puzzles " [2] ikkunan piirustuskilpailun voittamisen innoittamana .

Samaan aikaan japanilainen palapelin kirjoittaja Tetsuya Nishio ( japanilainen西尾徹也) keksii " Paint by Numbers " -pulmia ja julkaisee ne toisessa julkaisussa [2] .

Aluksi nonogrammit eivät herättäneet suurta kiinnostusta palapelien ystävien keskuudessa, koska kukaan ei ymmärtänyt, millainen tämä palapeli oli, kuinka se ratkaistaan.

Japanilaiset palapelit saivat suuren suosion vuosina 1989-1990 sen jälkeen, kun ne julkaistiin brittiläisessä The Telegraph -sanomalehdessä . James Delgety , tunnettu brittiläinen pulmapelien ystävä, sai sanomalehden johdon julkaisemaan japanilaisia ​​arvoituksia viikoittain. Pian he oppivat myös nonogrammeista tai griddlereistä (eng. Griddlers ) Venäjällä , täällä niitä kutsuttiin "japanilaiseksi ristisanaksi" tai "japanilaiseksi palapeliksi".

Ratkaisutekniikka

Algoritmi japanilaisen ristisanatehtävän ratkaisemiseksi alla olevan "sydän" -mallin esimerkillä on seuraava. Helpoin on aloittaa niistä viivoista, jotka maalataan päälle. Esimerkissämme on vain kolme tällaista 9 solun riviä (kuva 1).

Toinen rivi koostuu kahdesta 4 solun ryhmästä. Tässä tapauksessa ryhmien välinen ero on 5. sarakkeessa. Sen jälkeen sarakkeisiin 1 ja 9 täytetään 4 solua, mikä on tarpeen olosuhteiden mukaan.

Kaikki muut solut näissä sarakkeissa ovat ehdottomasti varjostamattomia. Ne on merkitty ristillä (kuva 2). Lisäksi rivillä numero 7 kaikki seitsemän jäljellä olevaa solua on maalattu päälle. Keskisarakkeeseen muodostettiin ryhmän alku - 4 ehdon vaatimasta seitsemästä. Tämä ryhmä on loppumassa.

Rivillä, jolla on numero 1, on jo solu, ja kaikki muut on merkitty ristillä. Rivillä numerolla 3 toinen ja kahdeksas solu jäävät ehdottomasti vapaiksi ja rivillä 2-2 kolmas ja seitsemäs solu maalataan ehdottomasti päälle (kuva 3).

Sitten täytetään sarakkeet 3 ja 7, kolme solua riviltä numerolla 5 yhdistetään toisiinsa, rivin kaksi jäljellä olevaa solua, joiden numero on 3, maalataan päälle. Jäljelle jää maalata toisen solun ensimmäiset ja kahdeksas sarake (kuva 4).

"Sydän" (esimerkki)

• Riisi. yksi

• Riisi. 2

• Riisi. 3

• Riisi. neljä

Tietokoneratkaisu

Japanilainen ristisanatehtävä on NP-täydellinen , polynomiaikaratkaisua ei ole , jos P≠NP .

Kuitenkin, jos vain ristisanat "joilla on yksi ratkaisu, joka on saavutettavissa vain loogista polkua" luokitellaan japanilaiseksi ristisanatehtäväksi, niin tällaisia ​​ristisanatehtäviä ei voida lukea NP-täydellisten tehtävien ansioksi, koska meillä on milloin tahansa ristisanaa ratkaistaessa tietoa, joka osoittaa yksiselitteisesti mitä soluja voidaan avata edelleen. Itse asiassa kaikki henkilön käyttämät ristisanatehtävien ratkaisumenetelmät (lukuun ottamatta "yritys ja erehdys" -menetelmää [3] ) perustuvat tähän.

Yksinkertaisimmassa muodossaan (8 × 8 neliötä) japanilainen ristisanatehtävä tarjottiin vuonna 1992 International Olympiad in Informatics (IOI) osallistujille nimellä "saaret meressä".

Värilliset japanilaiset ristisanatehtävät

Suurin ero värillisten japanilaisten ja mustavalkoisten pulmien välillä on kahden tai useamman soluvärin läsnäolo (taustaväriä ei oteta huomioon erillisenä värinä), mikä puolestaan ​​tuo yhden merkittävän eron pulman ratkaisemisessa . On muistettava, että väripalapelissä ei välttämättä ole valkoisia soluja eriväristen soluryhmien välillä.

Vastaavasti, jos mustavalkoisessa pulmapelissä ratkaistaessa oletetaan, että varjostettujen solujen ryhmä on välttämättä erotettu toisesta vähintään yhdellä varjostamattomalla solulla ja ottaa sen huomioon laskennassa, niin tätä ei voida tehdä väripalapeli, koska soluryhmät voivat sijaita lähellä toisiaan.

Myös erityisen monimutkaisissa väriristisanoissa on lisäksi tarpeen ottaa huomioon värit solujen leikkauskohdassa.

Muuten ratkaisu perustuu samoihin periaatteisiin kuin mustavalkoiset pulmat:

• taattujen varjostettujen solujen alueiden määrittäminen;
• sellaisten alueiden määrittäminen, jotka eivät taatusti sisällä varjostettuja soluja.

Värilliset japanilaiset ristisanatehtävät on yleensä paljon helpompi ratkaista kuin mustavalkoiset.

Muistiinpanot

1. ↑ 1 2 "Loogisella polulla" tarkoitetaan mitä tahansa menetelmiä japanilaisten ristisanatehtävien ratkaisemiseksi, lukuun ottamatta "yritys ja erehdys" -menetelmää
2. ↑ 1 2 3 Japanin ristisanatehtävien historia | Japania käsittelevä sivusto: moderni Japani  (venäläinen)  ? . Haettu: 27. helmikuuta 2021.  (määrätön)
3. ↑ "Yrityksen ja erehdyksen" menetelmä on tarkoitettu nimenomaan ristisanatehtäville, jotka eivät kuulu ryhmään "joilla on yksi ratkaisu, joka on saavutettavissa vain loogisella tavalla", eivätkä siksi saa sisältää tietoja, jotka yksiselitteisesti osoittavat avattavat solut seuraava siirto

Linkit

• Japanin ristisanatehtävien ratkaisumenetelmät

Bibliografisissa luetteloissa	LNB : 000321927