Japansk krydsord

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. maj 2019; checks kræver 43 redigeringer .

Japansk puslespil (også japansk krydsord , japansk tegning , nonogram ) er et puslespil , hvor der i modsætning til almindelige krydsord ikke er kodet ord , men et billede.

Beskrivelse

Billederne er kodet med tal placeret til venstre for rækkerne og også over kolonnerne. Antallet af tal viser, hvor mange grupper af sorte (eller deres egen farve, for farvekrydsord ) celler, der er i den tilsvarende række eller kolonne, og tallene i sig selv viser, hvor mange sammensmeltede celler hver af disse grupper indeholder (f.eks. et sæt med tre tal - 4, 1 og 3 betyder, at der er tre grupper i denne række: den første - fra fire, den anden - fra en, den tredje - fra tre sorte celler). I et sort-hvidt krydsord skal grupper adskilles af mindst én tom celle, i farve gælder denne regel kun for ensfarvede grupper, og flerfarvede grupper kan placeres tæt på (tomme celler kan også være ved kanterne af rækkerne). Det er nødvendigt at bestemme placeringen af ​​grupper af celler.

På trods af den høje udbredelse er der i øjeblikket ingen generel mening om kravene til japanske krydsord . De vigtigste meninger koges ned til forskellige kombinationer af følgende udsagn:

  1. Et korrekt sammensat puslespil bør kun have én løsning.
  2. Størrelsen på krydsordet (i bredde og højde) skal være et multiplum af 5 (så hjælpegitteret kan opdele feltet i 5x5 blokke).
  3. Antallet af farver, der bruges i et japansk farvekryds, bør begrænses, og selve farverne skal være let at skelne fra hinanden.
  4. Baggrundsfarven (farven på de tomme celler på banen) på det japanske krydsord skal være hvid.
  5. Krydsordet skal have en logisk opnåelig løsning (mens der ikke er en klar definition af, hvilken af ​​løsningsmetoderne der hører til denne kategori). Krydsord , som har én løsning, som kun kan nås med brute force , betragtes ikke som et japansk krydsord (på grund af det astronomiske antal kombinationer, som en person ikke er i stand til at sortere igennem).
  6. Det er uacceptabelt at have rækker og kolonner uden udfyldte celler (og følgelig uden tal ).
  7. Det er uacceptabelt at have rækker og kolonner, hvor der "intet er at gætte" (normalt betyder dette fraværet af enkelte tomme celler mellem grupper af antal af forskellige farver, og fraværet af dobbelte tomme celler mellem grupper af samme farve. I i dette tilfælde har grupper af numre den eneste mulighed for placering, da de optager al tilgængelig plads).

Historie

Japanske gåder dukkede op i Japan i slutningen af ​​det 20. århundrede , to personer hævder deres forfatterskab .

En af dem er Non Ishida (石田の ん), en illustrator og grafisk redaktør , som hævdede, at hun allerede i 1970 skabte nonogrammer som et kommunikationsmiddel mellem mennesker og dyr . Ikke Isis mente, at dyr er meget intelligente skabninger, men på grund af manglen på kommunikationsmidler mellem mennesker og dyr, undervurderer mennesket jordiske skabninger. Som et resultat af hendes videnskabelige arbejde blev der ifølge Isis født nonogrammer (eng. Nonogram) (NON + diaGRAM) - felter med sorte og hvide firkanter [2] .

I 1987 deltog Non Ishida i Window Art - konkurrencen . Deltagerne skulle lave et billede på en skyskraber ved hjælp af vinduer, tænde eller slukke lyset i rummene. Om natten blev resultaterne opsummeret, og Isis' arbejde indtog førstepladsen. The Tale of the Bamboo Cutter er en  japansk legende fra det 8. århundrede , der var det første nonogram set af en stor offentlighed .

I 1988 udgiver Non Ishida , inspireret af at vinde en vinduestegningskonkurrence , tre puslespil i Japan under titlen " Window Art Puzzles " [2] .

Samtidig kommer den japanske puslespilsforfatter Tetsuya Nishio ( japansk西尾徹也) med " Paint by Numbers " -puslespil og udgiver dem i en anden publikation [2] .

Oprindeligt vakte nonogrammer ikke megen interesse blandt puslespilelskere, da ingen forstod, hvordan dette puslespil var, hvordan man løser det.

Japanske gåder vandt stor popularitet i 1989-1990 efter at være blevet offentliggjort i den britiske avis The Telegraph , James Delgety , en kendt britisk puslespilelsker, overbeviste avisens ledelse om at udgive japanske gåder ugentligt. Snart lærte de også om nonogrammer eller griddlers (eng. Griddlers ) i Rusland , her blev de kaldt "japanske krydsord" eller "japanske puslespil".

Løsningsteknik

Algoritmen til at løse et japansk krydsord ved hjælp af eksemplet med "hjerte"-mønsteret vist nedenfor er som følger. Det er nemmest at starte med de linjer, der skal males over. I vores eksempel er der kun tre sådanne linjer med 9 celler (fig. 1).

Den anden linje består af to grupper af 4 celler. I dette tilfælde vil afstanden mellem grupperne være i den 5. kolonne. Derefter udfyldes 4 celler i kolonne 1 og 9, hvilket er nødvendigt i henhold til betingelserne.

Alle andre celler i disse kolonner er absolut uskyggede. De er markeret med kryds (fig. 2). Yderligere, i linjen med tallet 7, er alle syv resterende celler malet over. I den midterste kolonne blev begyndelsen af ​​gruppen dannet - 4 ud af 7 krævede af betingelsen. Denne gruppe er ved at slutte.

I linjen med tallet 1 er der allerede en celle, og alle de andre er markeret med et kryds. I linjen med tallet 3 vil den anden og ottende celle helt sikkert forblive fri, og i linjen med gruppe 2-2 vil den tredje og syvende celle definitivt blive malet over (fig. 3).

Derefter afsluttes kolonne 3 og 7, tre celler fra linjen med tallet 5 forbindes med hinanden, overmales de to resterende celler i linjen med tallet 3. Der er tilbage at male over de første celler i den anden og ottende søjle (fig. 4).

"Hjerte" (eksempel)

Computerløsning

Det japanske krydsord er NP-komplet , der er ingen polynomisk tidsløsning , hvis P≠NP .

Men hvis kun krydsord "der har én løsning, som kun kan opnås ad en logisk vej" klassificeres som japanske krydsord, så kan sådanne krydsord ikke tilskrives NP-komplette opgaver, da vi til enhver tid, når vi løser et krydsord, har information, der utvetydigt indikerer hvilke celler der kan åbnes yderligere. Faktisk er alle metoder til løsning af krydsord brugt af en person (med undtagelse af "trial and error"-metoden [3] ) baseret på dette.

I sin enkleste form (8 × 8 kvadrat) blev det japanske krydsord tilbudt i 1992 til deltagere i den internationale olympiade i informatik (IOI) under navnet "øer i havet".

Farvede japanske krydsord

Den største forskel mellem farvede japanske puslespil og sorte og hvide er tilstedeværelsen af ​​to eller flere cellefarver (baggrundsfarven tages ikke i betragtning som en separat farve), hvilket igen introducerer en væsentlig forskel i løsningen af ​​puslespillet . Det skal huskes, at der i et farvepuslespil ikke må være hvide celler mellem grupper af celler i forskellige farver.

Følgelig, hvis det i et sort-hvidt puslespil, når man løser det, antages, at en gruppe af skraverede celler nødvendigvis er adskilt fra en anden af ​​mindst én uskygget celle og tager det i betragtning ved beregningen, så kan dette ikke gøres i en farvepuslespil, da grupper af celler kan placeres tæt på hinanden ven.

Også i særligt komplekse farvekrydsord er det desuden nødvendigt at tage højde for farverne ved skæringspunktet mellem celler.

Ellers er løsningen baseret på de samme principper som for sort/hvide puslespil:

Farvede japanske krydsord er generelt meget nemmere at løse end sorte og hvide.

Noter

  1. ↑ 1 2 Med "logisk vej" menes enhver metode til at løse japanske krydsord, med undtagelse af "trial and error"-metoden
  2. ↑ 1 2 3 Japanske krydsords historie | Site om Japan: moderne Japan  (russisk)  ? . Hentet: 27. februar 2021.
  3. ↑ "Trial and error"-metoden er specifikt beregnet til krydsord, der ikke tilhører gruppen "at have én løsning, kun opnåelig på en logisk måde", og må derfor ikke indeholde information, der entydigt angiver de celler, der skal åbnes i næste træk

Links

  Gå til Wikidata-elementet  I bibliografiske kataloger
 Firma Nikoli
Personligheder
Gåde