Hvornår har en Sudoku kun én løsning?
Arto Inkala fra Finland har udviklet denne Sudoku i 2006, som han kalder for AI Escargot efter sin forbogstaver og fordi, den ligner en snegl. For at løse den kræver det, at man holder styr på otte relationer. De lette sodokuer kræver kun, at man kan holde styr på et par kombinationer ad gangen.
Spørg Scientariet
Nu kan du også udfordre dine venner med ekspert-spørgsmål fra Scientariet i Ingeniørens Facebook-quiz "Så ka' du lære det!".
Klik for at deltage i quizzen og test dine venner.
Læs mere om
Dokumentation
Som selvstændig i firmaet KLPlab har Per Olesen ikke ret megen fritid til Sudoku, men han har alligevel spekuleret over de matematiske regler, der ligger til grund for de populære Sudoku'er:
"Når man gætter Sudoku, så er opgaverne nogle gange nede på så få forud givne tal, at man ikke helt kan lave en logisk løsning men må gætte og evt. prøve igen. Det har fået mig til at fundere over, om man præcist kan definere, hvornår en Sudoku KUN har en løsning og ved hvilket antal forudgivne tal dette er, samt hvor mange der max. skal til for at være sikker på min. 2 forskellige løsninger."
Thomas Bolander, lektor på Institut for Matematisk Modellering, DTU, svarer:
"Spørgsmål omkring Sudoku er notorisk vanskelige på grund af den store kombinatoriske kompleksitet. I en Sudoku er det almindeligvis et krav, at der kun må findes een korrekt løsning, men der findes ikke nogen simpel betingelse som kan garantere dette. Betingelsen kan reformuleres indenfor eksempelvis logik og grafteori, men det giver ikke en betingelse som er lettere at håndtere.
Det formodes, at det minimale antal af forud givne tal, som kan give en entydig løsning, er 17, selvom dette endnu ikke er bevist. Det betyder naturligvis ikke at alle Sudoku'er med 17 forud givne tal har en entydig løsning, men blot at der findes en Sudoku med 17 forud givne tal, som har en entydig løsning - og at man indtil videre ikke har været i stand til at finde Sudoku'er med færre forud givne tal, som har en entydig løsning.
Hvis man får bevist at de Sudoku'er med entydige løsninger, som har færrest forud givne tal, har netop 17 af slagsen, vil man hermed også få bevist at alle Sudoku'er med 16 eller færre forudgivne tal må have mindst to løsninger. Men det er som nævnt indtil videre kun en formodning. Formodningen er dog eksperimentelt understøttet af omfattende computer-beregninger som har genereret titusindvis af entydige Sudoku'er med 17 forud givne tal, men endnu ingen med 16 eller derunder.
Det vides også at der i hvert fald skal mindst 8 forudgivne tal til at garantere en entydig løsning, for alle Sudoku'er der kun benytter 7 eller færre forskellige tal i de forudgivne felter vil nødvendigvis have mindst to løsninger (idet de to resterende tal som ikke er benyttet i de forudgivne felter kan ombyttes i løsningen).
Man kan også gå i den anden retning og overveje, hvor mange forudgivne tal man maksimalt kan have i en Sudoku med mindst to løsninger. Dette spørgsmål er til gengæld ikke så svært at besvare. Det er muligt at lave en Sudoku, hvor alle på nær 4 felter er forud givne. Disse 4 felter kan eksempelvis optræde som en 2x2 firkant som enten kan udfyldes med værdierne 1,2 i første række og 2,1 i anden række - eller omvendt med 2,1 i første række og 1,2 i anden række. Det svarer til de netop to løsninger som en 2x2 Sudoku har, men kan altså genfindes som en 'sub-Sudoku' af en almindelig 9x9 Sudoku."
Per Olesen vinder to billetter til Experimentarium for sit spørgsmål.
Utætheder skyldes uvidenhed og byggesjusk
Er mørkt stof en negativ tyngdekraft?
