Så kom beviset: En sudoku med færre end 17 udgangstal har flere løsninger
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.

Så kom beviset: En sudoku med færre end 17 udgangstal har flere løsninger

En irsk matematiker har løst en af verdens vanskeligste opgaver. Han har endegyldigt bevist, hvad der længe har været formodet: at der skal være mindst 17 tal som udgangspunkt i en sudoku-opgave, hvis den skal have en entydig løsning.

De fleste sudokuer, der findes i aviser, har typisk omkring 25 tal som udgangspunkt.

Den australske matematiker Gordon Royle fra University of Western Australia i Perth har en samling af 49.151 forskellige sudokuer, der har en entydig løsning med 17 tal som udgangspunkt, men han er aldrig blevet præsenteret for eller selv fundet en med 16 tal.

Det er nu bevist, at der ikke findes 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).

Nu har Gary McGuire fra University College Dublin langt om længe bevist, at der ikke findes nogen. Andre har gennem mange år puslet med samme problemstilling uden at kunne give et skudsikkert bevis.

Gary McGuire har da også måttet gribe til den hårde metode. Han har undersøgt alle mulige sudoku-kombinationer.

Det lyder næsten umuligt, for der findes 6.670.903.752.021.072.936.960 forskellige sudokuer. Tager man hensyn til symmetrier som rotation, refleksion og ombytning af tal, er der dog i virkeligheden 'kun' 5.472.730.538 forskellige.

Det lyder mere overkommeligt, men er dog stadig en enorm opgave.

Fra 300.000 år til 810 år

Gordon Royle erklærede for et år siden, at medmindre man udviklede en ny teknik, ville det være umuligt at finde ud af, om der fandtes en sudoku med 16 tal som udgangspunkt inden for hans levetid.

Gary McGuire arbejdede allerede i 2006 på en teknik til at gennemgå alle fem en halv milliard sudokuer, men andre forskere estimerede siden hen, at det vil tage omkring 300.000 år på en computer at bruge denne metode.

Nu har han med hjælp fra to kollegaer forbedret algoritmen, så det har været muligt med brug af Stokes-supercomputeren ved Irish Centre for High-End Computing at komme gennem alle forskellige kombinationer.

Det har taget 7,1 millioner cpu-timer, som er brugt i perioden januar 2011 til december 2011. De 7,1 millioner timer svarer til ca. 810 år.

Der var ingen sudoku med 16 tal som udgangspunkt, der kun havde én løsning.

Regner den rigtigt?

McGuire og co. forklarer, at de tjekkede deres metode ved at søge efter 17-tals sudokuer inden for visse af 5.472.730.538 løsninger, hvor man med andre teknikker i forvejen kendte det præcise antal af 17-tals sudokuer. Alle blev fundet korrekt.

Der findes desuden en kendt 16-tals sudoku, der kun leder til to forskellige løsninger (se illustrationen). En lille modifikation af algoritmen gjorde det også muligt for forskerholdet at finde den med deres metode.

Forskerne har i øvrigt gjort kildekoden til deres program tilgængelig via deres website, hvis nogle skulle være interesseret i at studere den mere indgående.

Dokumentation

There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
McGuires Sudoku checker
Stokes-supercomputeren

og tænker over hvilken banebrydende forskning vi her har med at gøre !!
Føler mig pludselig meget mere rustet til at klare hverdagen, med denne viden :-//

  • 0
  • 0

Naa det er det, de bruger deres supercomputere til. Gary har forhaabentlig selv betalt computertiden. Foregaar der lignende projekter i Danmark betalt af skatteyderne?

  • 0
  • 0

Nu læser Gary McGuire næppe ing.dk, men jeg formoder, han vil forsvare sig mod ovennævnte angreb på samme måde, som han har skrevet i artiklens abstract:

The hitting set problem is computationally hard; it is one of Karp’s twenty-one
classic NP-complete problems. We have designed a new algorithm that allows us to efficiently enumerate hitting sets of a suitable size. Hitting set problems have applications in many areas of science, such as bioinformatics and software testing.

  • 0
  • 0