Sudoku - et avanceret matematisk tidsfordriv
more_vert
close
close

Vores nyhedsbreve

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

Sudoku - et avanceret matematisk tidsfordriv

"Det handler ikke om matematik" skrev en dansk avis for nogle år siden troligt ved siden af de daglige sudoku-opgaver. Men intet er mere forkert. Sudoku er godt nok ikke aritmetik, men det er i høj grad matematik.

Og fænomenet er i høj grad en kilde til fascination for Thomas Bolander, lektor på Institut for Informatik og Matematisk Modellering på DTU. Ikke opgaverne i sig selv, men af at så mange danskere på grund af sudokuer har kastet sig over løsningen af komplicerede ligningssystemer i deres fritid.

»Sudoku er direkte relateret til nogle af de helt store problemer inden for matematikken og til en af de syv priser på hver en million dollar, der ved årtusindeskiftet blev indstiftet for at løse syv af matematikkens allerstørste problemer ved indgangen til det 21. århundrede,« forklarer Thomas Bolander.

Der kendes ingen sudokuer med 16 eller færre tal som udgangspunkt, der har en entydig løsning. Men denne sudoku med 16 tal har kun to løsninger (med 8 og 9 ombyttet i løsningen).
Günter Stertenbrink har samlet nogle af sværeste sudokuer i en serie han kalder Top 1465. Her ses nr. 77 fra denne serie, som ofte benyttes til at vurdere, hvor godt et computerprogram er til at løse de svære sudokuer.
Der kendes ingen sudokuer med 16 eller færre tal som udgangspunkt, der har en entydig løsning. Men denne sudoku med 16 tal har kun to løsninger (med 8 og 9 ombyttet i løsningen).

Lette og svære problemer

Sudoku har relation til den præcise matematiske definition af forskellen mellem lette og svære problemer.

Lette problemer kalder matematikerne for P-problemer, de svære kalder de for NP-problemer. Sudoku illustrerer meget vel, hvad denne problemstilling går ud på.

Det er et P-problem at checke, om den løsning, en person har fundet for en sudoku, er rigtig eller forkert, men det er et NP-problem at finde løsningen.

De fleste finder det indlysende, at det er meget sværere at finde en løsning til en sudoku end at checke en anden persons løsning, og at P-problemer derfor er væsentligt forskellig fra NP-problemer. Men det kan jo blot være en mangel på intellektuel formåen - matematisk set behøver det ikke at være således. Det skal bevises eller modbevises. Det er ikke lykkes for nogen endnu.

I matematikkens sprog er man uvidende om, hvorvidt udsagnet P=NP er sandt eller falsk.

Sværhedsgraden af en sudoku-løsning har mange lighedspunkter med almindelige optimeringsproblemer fra hverdagen: Når en sælger skal finde den korteste vej for at besøge sine kunder, når man skal pakke en stor mængde varer ned i en container med begrænset plads og medtage de varer, der kan tjenes mest på, osv.

En million dollar i findeløn

For at kunne løse optimeringsproblemer på en computer har man brug for gode algoritmer. En god algoritme kan løse problemer i polynomiel tid, dvs. hvis problemet indeholder n variable, kan det løses inden for kn^p sekunder (hvor k og p er konstanter).

Problemer, der kan løses i polynomiel tid, er matematikernes præcise definition af, hvad der er P-problemer.

Problemer, der kun kan løses i eksponentiel tid, altså inden for k2^n sekunder, er derimod svære problemer.

Står man over for et svært problem, nytter det ikke noget at bede om en dobbelt så hurtig computer, for den er heller ikke i stand til at løse problemet. De sudokuer, som bringes i aviserne, er normalt af størrelsen 9x9 og i sjældne tilfælde af 16x16.

Kraftige computere må give op

»Det er ingen sag for computere at løse disse, men går man op i endnu større sudokuer (25x25, 36x36 osv.) må selv de kraftigste computere give op, da sværhedsgraden stiger eksponentielt med størrelsen. Det ved vi, fordi sudoku er et NP-komplet problem,« siger Thomas Bolander.

NP-komplette problemer er en gruppe af problemer, der har mindst sandsynlighed for at være P-problemer. Alle NP-komplette problemer kan omformuleres til hinanden.

Kan man derfor bevise, at der ikke findes en algoritme, der kan løse ét NP-komplet problem i polynomiel tid, så har man generelt bevist, at P og NP er to forskellige mængder - og dermed sikret sig evig matematisk berømmelse foruden en million dollar.

Sudoku er derfor lige så velegnet at studere for matematikere og algoritmeudviklere som et ethvert andet NP-komplet problem. Og i modsætning til praktiske optimeringsproblemer, som eksempelvis den rejsende sælger, har det den egenskab, at man ikke kan nøjes med næsten optimale løsninger, som kan findes i polynomiel tid - der findes ikke næsten-rigtige løsninger for sudokuer.

Strategi eller brute force

Det er netop det, som Thomas Bolander finder fascinerende, og han er ikke ene om denne opfattelse. Det vidner den enorme interesse, der for nylig var i anledning af et spørgsmål til Ingeniørens Scientarium på ing.dk om, hvornår en sudoku kun har én løsning, og Thomas Bolanders svar herpå.

To af hans studerende, Christian Agerbeck og Mikael O. Hansen, har i et netop afsluttet speciale udviklet et program, der kan løse en vilkårlig Sudoku af størrelse n² x n² - og ikke blot de 9x9 sudokuer, som vi almindeligvis ser.

Deres program løser flere af de sværeste sudokuer hurtigere end, hvad tilsvarende programmer gør.

Der findes effektive brute force programmer på internettet, der kan løse de almindelige 9x9 sudokuer lynhurtigt - stort set ved blot at prøve sig frem. Men skal man lave et program, der løser sudokuer ud fra de indbyggede logiske sammenhænge, er det, som Christian Agerbeck og Mikael O. Hansen har gjort, tvinges man til at tænke over, hvilke strategier der er anvendelige, og om de i det hele taget kan bruges til at løse alle sudokuer.

Dokumentation

Spørg Scientariet: Hvornår har en sudoku kun én løsning?
Liste med entydige Sudokuer
Sudokusolver

Kommentarer (3)

Datalogernes ord: polynomiel og eksponentiel, er ikke særligt velvalgte, synes jeg, for et polynomium er en flerleddet størrelse, men det interessante ved 'polynomiel tid' er højestegradsleddet, som er en étleddet størrelse, altså et monomium, så man kunne kalde det monomiel tid. Matematikere bruger ordene 'algebraisk' og 'transcendent'.

  • 0
  • 0