En sudoku uten praktisk forutsigbarhet i hvert trinn?

[Marianne Skånland]

   
En sudoku uten praktisk forutsigbarhet i hvert trinn?

Jeg har prøvet meg på sudokuene på Telegraph.co.uk.

Jeg finner at de varierer svært. Noen er mekanisk lette, og med det mener jeg at det for hver tilstand eksisterer kvadrater, linjer eller kolonner hvor man kan eliminere tall slik at det i én rute kun blir igjen ett mulig tall. De som elimineres, elimineres på det som sikkert er vanlig vis: enten fordi de ikke kan stå i den ruten eller fordi andre tall må stå der. Tvillinger, trillinger, eventuelt kvadrillinger hvis det noen gang skulle være aktuelt, kjenner jeg til.

Men noen andre oppgaver går over min forstand. Det vil ikke si at de ikke kan løses, og de av disse umuliusene jeg har løst, ser ut til å være korrekte i den forstand at bare én total-løsning er mulig. Men jeg klarer ikke å finne noe farbart resonnement som gir en garantert riktig eliminasjon eller tall-innsetting for hvert trinn. Når jeg har plassert en del tall som er entydige og eliminert det som er sikkert i en del ruter, må jeg derfor prøve meg frem. For eksempel velger jeg da arbitrært en viss fordeling av de to mulige tallene i en tvilling, og ser hvor det fører hen. Først mange trinn senere (det kan være 10 - 20 trinn) viser det seg f.eks at valget førte meg opp i en kontradiksjon. I så fall gir det seg at det opprindelige tvilling-valget var galt og må være omvendt. Da kommer jeg altså videre. I de mest vriene kan jeg måtte forsøke slike arbitrære valg 2 - 3 ganger. Et eksempel er den for 20. juni (den blir vel stående 7 - 10 dager til på skjermen). En annen jeg står fast på nå er 26. juni. Det er rett og slett umulig (for meg) å overskue konsekvensene av et valg så mange trinn frem at jeg kan gjøre dette i hodet.

The Telegraph har mulighet for å skrive inn flere tall i en rute, hvilket gir god oversikt over alternative muligheter og over tvillinger/trillinger, men når entydigheten stopper opp for meg, må jeg altså til med papir, hvor jeg bevarer én versjon og merker av hvor jeg gjorde første, eventuelt andre osv, valg.

VG's sudokuer varierer også i vanskelighetsgrad; selv de vanskeligste og de middels kan være lette mens andre er vriene. Og hjelp på papir må jeg også av og til ha for VG's, men kun for å få oversikt over alle mulige tall i alle tomme ruter. Der har jeg alltid kunnet komme videre med entydig eliminasjon hele tiden.

*

Jeg ser at sudoku er lik 'latinske kvadrater' fra matematikken (kombinatorikk) – med tillegg av at små-kvadratene i sudoku også skal inneholde hvert tall én gang – men jeg har ikke klart å gjøre noe ut av den teknikken min kombinatorikk-bok beskrev for å lage latinske kvadrater. Der tok man utgangspunkt i rektangler, og beviste at de alltid kan utvides med nye rekker inntil man får et (latinsk) kvadrat.

Jeg er heller ikke i nærheten av å forstå hvordan sudoku-oppgavene konstrueres. Det må finnes én eller flere algoritmer for hvordan man kan velge ut de tallene som må oppgis for at oppgaven skal ha en entydig løsning som leseren kan komme frem til. Det er vesensforskjellig fra kryssord, hvor man lett forstår hvordan en kryssord komponeres, og hvor sikkert mange kryssord-gjettere også har prøvet seg som kryssord-komponister. En kryssord kan være vrien å komponere slik at bokstaver i begge retninger danner plausible ord, men teknikken er enkelt forståelig.

Marianne

PS: Jeg ser ikke noen forbindelse mellom sudoku og dens type prediktabilitet (eller ei), og DLFs samfunnsanalyser, hvilket andre spill beskrevet i denne debatt-seksjonen gir bedre eksempler på. Jeg tar allikevel mot til meg og lufter mine sudoku-funderinger, av ren pusle-interesse.

  

[Martin Johansen]

Sudoku er ekvivalent med å løse det såkalte exact cover-problemet, et velkjent problem i matematikk. Å forstå dette problemet er ikke så vanskelig. Men å løse en sudoku, som å løse exact cover, kjenner man ikke til en enkel metode (Det er et såkalt NP-komplett problem). Man kjenner kun i dag til en metode som løser en generel sudoku på en tid som er ekponesielt større en antall ruter i sudokuen. Altså med X ruter kan det ta 2 opphøyd i X minutter å løse, ca, og ingen bedre metode er i dag kjent.

En metode for å løse sudoku er dog såkalt "baktracking". Det vil si at man finner alle mulige tall for en rute, hvis dette er flere en 1 for alle rutene, må man prøve et alternativ for så å forkaste alternativetet hvis det viser seg å føre til en motsigelse. Denne teknikken kan nøstes, altså utføres etter hverandre. Såkalt rekursjon. Man kan også "backtracke" en fullstendig løst sudoku for å se om det er flere løsninger.

For å lage en sudoku finnes det sikkert mange metoder. Men en metode som ville fungert er å ta en blank-sudoku og legge til tilfeldige tall på denne. For hvert tall man legger til sjekker man hvordan den løses (ved metoden jeg beskrev ovenfor). Man kan da si at hvis sudokuen må løses ved mange "backtrackinger" (mange prøv-og-feil) så er den vanskelig og motsatt.

[ehasl]

En av oppgavene jeg har fått i studiet var å lage et program som løser Sudoku.

Det fungerer slik (antagelig samme som Martin Johansen mente):
1. Prøv hvert eneste lovlige tall i første rute som ikke er forhåndsutfylt.
2. For hvert tall som ikke kommer i konflikt med det som allerede er fylt ut,
2.1. Behold dette tallet og gjenta fra steg 1 med neste rute som ikke er forhåndsutfylt. (På denne måten bygges det opp en stabel/stack av kall på funksjonen.)
3. Hvis dette var siste rute,
3.1. Lagre hele brettet i en samling.

Resultatet er en samling av alle de mulige løsningene.
Hmm. Det ble kanskje ikke så mye klarere.

Jeg gidder aldri å bli ekte god i Sudoku når jeg har et såpass raskt program.

Programmet takler brett opp til 12x12. 16x16 blir for tungt.