Spørg Læserne: Er 18 sværere end 17 i en sudoku?
more_vert
close

Få de daglige nyheder fra Version2 og Ingeniøren. Læs mere om nyhedsbrevene her.

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser, og at Teknologiens Mediehus og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, tilbud mm via telefon, SMS og email. I nyhedsbreve og mails fra Teknologiens Mediehus kan findes markedsføring fra samarbejdspartnere.

Spørg Læserne: Er 18 sværere end 17 i en sudoku?

'Er dette verdens sværeste sudoku?' står der som billedtekst til denne sudoku i vores billedarkiv. Illustration: Mediehuset Ingeniøren

Lotte Gut spørger helt enkelt: Kan man lave en Sudoku med 18 udfyldte felter, der er sværere end en Sudoku med 17 udfyldte felter?

Ja, nej, hvorfor, hvorfor ikke? Skriv i kommentarfeltet.

Spørg fagfolket

Du kan spørge om alt inden for teknologi og naturvidenskab. Redaktionen udvælger indsendte spørgsmål og finder den bedste ekspert til at svare – eller sender spørgsmålet videre til vores kloge læsere. Klik her for at stille dit spørgsmål til fagfolket.

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Umiddelbart vil jeg mene at placeringen af tallene ville være afgørende. I en opgave hvor 18 indsatte tal er placeret i de øverste 3 (3x3 kvadrater) vil være sværere end 17 jævnt fordelte tal.

  • 0
  • 0

Sværhedsgraden må være bestemt af antallet af iterationer der minimum skal laves før opgaven er løst.

I en simpel børneopgave kan man løse et vilkårligt tomt felt, så opgaven er løst efter 1 iteration.

I en supersvær opgave er det, til enhver tid, kun et (eller få) af de tomme felter det er muligt at løse, så der skal der næsten lige så mange iterationer til som der er tomme felter. En computer kan ret let tælle iterationer, så det er hurtigt regnet ud.

Man kan jo være heldig og hvis man forsøger sig med det rigtige tomme felt hver gang, så kan den oplevede sværhed være helt anderledes.

Jeg tror godt man kan lave en ”let” opgave med 17 tal, hvor der er behov for færre iterationer end en svær opgave med 18.

  • 1
  • 0

Jeg er enig i din konklusion, men det duer ikke at sætte alle tal i de tre øverste rækker, det vil nemlig give flere mulige løsninger.

I den opgave vil det f.eks. være muligt at bytte om på de to nederste rækker og stadig have en gyldig løsning.

  • 2
  • 0

Når man står med en delvist udfyldt sudoku (evt nystartet) er der typisk nogle felter man "umiddelbart" kan udfylde. Som jeg ser det er der
1. Oplagte felter: direkte inspektion af de tal der vises begrænser et felt til kun at indeholde en værdi.
2. Indirekte felter. Her vil de begrænsninger man kan se fortælle at fx tallene 2 og 3 skal stå i to givne felter. Denne oplysning kan så gøre at et felt bliver entydigt bestemt, så det kan udfyldes
3. Ingen af 1 eller 2 felterne findes. Så må man fylde et tilfældigt felt ud. Prøve at løse derfra og man risikerer at skulle vælge om og prøve forfra. Denne løsningsmodel er let at programmere men ikke særlig human.

I praksis kan alle lette og midelsvære sudoku er løses med 1. Og man kan hævde at sudokuer der kræver 3 er irrelevante som menneskelig opgave.
Når man løser en sudoku udvikler antallet af mulige felter sig. Der kan fx være 3 felter der kan løses med 1. Når dette så er gjort vil der være nye oplysninger og der kan måske være 7 felter eller 2 felter der kan udfyldes. Sudokuens sværhedsgrad er så baseret på hvor mange felter man således kan finde og om de er type 1 eller 2. En svær sudoku vil have mange situationer hvor der kun er et felt der kan bringe en videre. Det fremgår heraf at sværhedsgraden ikke direkte er afhængig af antallet af felter der er udfyldt i starten - men selvfølgelig, jo flere uudfyldte felter jo mere skal man lede.
Mange løsere skriver små tilføjelser til sudokuen undervejs for at huske ting. Den bedste strategi her er med en ret zen-agtig tekst: I et felt skal man notere de værdier der ikke kan stå der og som man ikke kan se umiddelbart (type 2 felter ovenfor). Med brug af denne teknik vil man få styr på type 2 felterne. Uanset hvad, kommer man ikke udenom at skulle lede igennem alle felter gang på gang, og sværhedsgraden kan beskrives ved hvor ofte man har ganske få felter, der kan bringe en et skridt videre.

  • 0
  • 0

Det er naturligvis ikke svaret på Lotte Guts spørgsmål, det er jeg slet ikke matematisk kyndig nok til, men Arto Inkala som jo har lavet ovenstående Sudoku vurderer selv sine "puzzles" således: http://www.aisudoku.com/index_en.html
Og her lander ovenstående "Escargot" på førstepladsen hvad angår "besværlighed".

  • 0
  • 0