Ofte stillede spørgsmål om Sudoku

Ofte stillede spørgsmål om Sudoku

Sudoku afkræver os et svar - men det får os også til at stille et hav af spørgsmål - spørgsmål, som Ingeniøren nu har konfronteret Lektor Thomas Bolander på Institut for Informatik og Matematisk Modellering på DTU med. Han giver nogle svar sammen med sine to specialestuderende Christian Agerbeck og Mikael O. Hansen:

Hvad er det mindste antal felter, der skal være udfyldt for at der er en entydig løsning?

Det korte svar er, det ved man ikke. Gordon Royle fra University of Western Australia i Perth har samlet 47.621 Sudokuer med en entydig løsning, hvor der som udgangspunkt er tal i 17 felter.

Der er ikke fundet Sudokuer med 16 eller færre felter udfyldt, der har en entydig løsning, men det er heller ikke bevist, at sådanne ikke findes.

For at en Sudoku skal have en entydig løsning, skal den mindst indeholde otte forskellige tal. Er der kun syv, kan man jo lave to forskellige løsninger, hvor de to ikke-repræsenterede tal i udgangspunktet kan ombyttes.

Hvor mange Sudokuer findes der?

Der er 6.670.903.752.021.072.936.960 forskellige Sudokuer (af størrelse 9 x 9), men tager man hensyn til symmetrier som rotation, refleksion og ombytning af tal er der ?kun? 5.472.730.538.

Hvordan løser man bedst en Sudoku?

Der findes en lang række strategier man kan følge, når man skal løse en Sudoku.

Som udgangspunkt kan en tom celle indeholde alle ni forskellige tal. Man lærer dog hurtigt, at udelukke tal på grund af de indbyrdes bindingerne (alle ni tal skal være med i hver enkelt række, søjle og kasse). Det vil ofte med det samme give anledning til, at man udelukke alle tal bortset end et enkelt fra nogle af cellerne.

Når dette er sket, er det en god teknik at se efter par, der gensidigt udelukker hinanden (det kaldes for nøgne par eller skjulte par) ? eller nøgne trioer og skjulte trioer - og på den måde reducere antallet af mulige tal, der kan indsættes i en celle - for til sidst at opnå, at tallet i en celle er entydigt bestemt.

Der findes også avancerede teknikker med eksotiske navne X-wing eller sværdfisk og endnu mere komplicerede teknikker, som bliver sværere og sværere at bruge i praksis, da de involverer mange celler langt fra hinanden.

Kan man altid løse en Sudoku?

Der findes en lang række eksempler på Sudokuer, hvor ingen af de nuværende kendte logiske strategier direkte fører til en løsning. I sådanne tilfælde, må man på et eller andet tidspunkt lave et gæt og se, om det fører frem til en løsning. Hvis det ikke sker, må man gå tilbage til udgangspunktet for gættet og prøve på ny.

I princippet kan man blive ved at udvikle nye strategier for at løse Sudokuer, men så længe strategierne hver især kan løses i polynomiel tid, så vil man aldrig finde strategier, der kan løse alle Sudokuer. "I givet fald ville man have vist at P=NP, og det er næppe realistisk," mener Thomas Bolander.

Hvad er en svær Sudoku?

Sværhedsgraden for en Sudoku bestemmes ud fra hvor komplicerede strategier, der skal tages i anvendelse ved løsningen. Men der er ikke nogen entydig definition af, hvad der er svært for den enkelte person, så derfor kan man nogen gange gå i stå i en mellemsvær Sudoku og løse en svær forholdsvist hurtigt.

Den finske matematiker Arto Inkala offentliggjorde i 2006 en Sudoku han kaldte AI Escargot og som han hævdede var verdens mest svære Sudoku på dette tidspunkt. Han skrev en hel bog om denne Sudoku.

Günter Stertenbrink har på en hjemmeside samlet mange af de sværeste sudokoer. Et af sættene i denne samling ?Top 1.465?, anvendes ofte, når man skal undersøge, hvor effektive computerprogrammer er til at løse Sudokuer.

Kommentarer (0)