Hvad gør et nonogram let eller svært

Et større gitter betyder ganske vist flere linjer at holde styr på og mere krydstjek, så store puslespil tager længere tid. Men længden alene gør ikke en linje svær — en række på 20 i bredden med én stor sekvens er triviel, mens en kort række fyldt med små sekvenser og snævre mellemrum kan kræve ægte tænkning. Størrelsen påvirker langt mere, hvor lang tid et puslespil tager, end hvor svært hvert trin er.

Det sandeste mål for sværhedsgrad er, hvilken slags ræsonnement puslespillet kræver. De letteste puslespil er ”linjeløsbare”: du kan færdiggøre dem ved at se på én række eller kolonne ad gangen, udfylde det, den ene linje tvinger frem, og aldrig skulle holde to linjer i hovedet samtidig. De fleste milde puslespil er præcis dette.

Sværere puslespil kræver, at du kombinerer information — at bemærke, at et felts tilstand først bliver tvunget, når du betragter en række og en kolonne sammen, eller en lille klynge linjer ad gangen. Jo dybere den kombination skal gå, før det næste felt er tvunget, desto sværere føles puslespillet, uanset dets størrelse.

Her kommer den beroligende del. Akademisk arbejde om nonogramløsning (Batenburg and Kosters, 2012) målte, hvor meget ræsonnement entydigt løsbare puslespil faktisk kræver. Ud over simpel linje-for-linje-løsning er det næste skridt en veldefineret, stadig deterministisk teknik — at kombinere par af linjer — og deres udtømmende optælling fandt, at 93.8–95.5% af de ikke-simple puslespil er løsbare med præcis det, helt uden gætteri.

Endnu mere slående: kun omkring 0.06–0.14% af alle entydigt løsbare puslespil har brug for noget ud over det ræsonnement med par af linjer. Med andre ord kan langt de fleste velformede nonogrammer — inklusive hvert svært et, du møder i normalt spil — løses med ren, afgrænset logik. Ægte forsøg og fejl er forsvindende sjælden i et fair puslespil, og derfor er ”gæt aldrig” et så pålideligt råd.

Under alt dette ligger et teoretisk resultat. At afgøre, om et vilkårligt sæt af række- og kolonneledetråde overhovedet har nogen løsning, blev bevist NP-komplet (Ueda and Nagao, 1996) — samme kompleksitetsklasse som berygtet stædige problemer som handelsrejsendes problem. Sagt ligeud: ingen kender en metode, der løser ethvert tænkeligt nonogram hurtigt, og i værste fald eksploderer det nødvendige arbejde, efterhånden som gitteret vokser.

Det lyder alarmerende, indtil du bemærker forskellen mellem ”ethvert tænkeligt nonogram” og ”de nonogrammer, folk faktisk udgiver”. NP-komplethedsresultatet handler om vilkårlige, fjendtlige sæt af ledetråde — mange af dem har ingen løsning eller flere. Et rigtigt puslespil bygges omvendt: det starter fra et billede og udgives kun, hvis det har præcis én løsning, som logikken faktisk kan nå. Derfor holder tallene i forrige afsnit i praksis — og derfor er puslespillet foran dig næsten med sikkerhed fair, selv når det føles brutalt.

Ud over slutningsdybden skubber et par overfladiske træk til sværhedsgraden. Meget sparsomme billeder (for det meste tomme) og meget tætte (for det meste udfyldte) plejer at være lettere, fordi yderpunkterne giver mange tvungne felter tidligt. De vanskeligste puslespil ligger som regel i midten, med en afbalanceret blanding af udfyldt og tomt og masser af korte, opbrudte sekvenser, der modstår de hurtige åbningstræk. Et rent, genkendeligt motiv hjælper også løseren med at holde orienteringen, selv om det ikke ændrer den underliggende logik.

På dette websted kommer et puslespils vurdering fra, hvor dybt ræsonnementet for at løse det går, kombineret med formstatistik som hvor udfyldt gitteret er. Linjeløsbare puslespil havner i let; dem, der kræver ægte kombination på tværs af linjer, bevæger sig mod svær; alt, der ville kræve gætteri, afvises direkte i stedet for at blive udgivet. Hele processen er beskrevet på siden ”hvordan vi laver vores nonogrammer” — men kortversionen er, at sværhedsgrad her måles, ikke gættes.