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

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

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.

Men kunne han ikke afprøve sin algoritme paa et mere seriøst problem?

  • 0
  • 0

Det er ikke al forskning der skal munde ud i et direkte økonomisk afkast. Nogle gange skal man bare søge viden for at udvikle sig... Newton udviklede difrential- og integralregning for at bevise at jorden ikke var solsystemets centrum, men at solen var det... Den matematik er siden brugt på mange andre områder og har flyttet os i en videnskablig retning... Men jeg tror ikke at undersøgelserne af planetbanerne i sig selv har genereret det store økonomiske overskud...

  • 0
  • 0

Måske han kun har brugt ledig CPU-idle-time - hvis sådan noget findes på en supercomputer...
Hvad mon Irish Centre for High-End Computing ellers laver ?

  • 0
  • 0

Gordon Royle og fler andre forskere har åbenbart ment at det ikke var muligt. Nu er de så blevet klogere, og kan beskæftige sig med andet væsentligt. Jeg er da sikker på at der er nogle hackere for eksempel fra diverse efterretningsvæsner som bliver glade for denne forbedrede allegoritme. Vær nu lidt optimistiske.
Mange hilsner
Klaus

  • 0
  • 0

Men kunne han ikke afprøve sin algoritme paa et mere seriøst problem?

Fordelen ved at arbejde med Sodukos, når man arbejder med NP-problemer, er at der kun er en løsning, og den er let at teste for.

Og så vidt jeg husker kan de forskellige NP-problemer transformeres til hinanden, og så kan man ligeså godt arbejde på en der let at checke.

  • 0
  • 0

Beviset er her en godtgørelse af, at man har gennemregnet alle muligheder ved brug af en hulens masse CPU-år. Man kunne jo nok savne fordum tiders elegance ved et uafviseligt matematisk-logisk bevis i klassisk forstand.

  • 0
  • 0

"Men kunne han ikke afprøve sin algoritme paa et mere seriøst problem?"

Uden at have læst den konkrete artikel, vil jeg mene at der kan være god mening i at vælge et "useriøst" problem, som f.eks. sudokuløsning, som testeksempel når en ny algoritme skal publiceres.
Tit vil et simpelt spil være tæt på eller identisk med minimaleksemplet for det problemtype man vil løse. Dette ses vel tydeligst inden for spilteori, som jo har et væld af nyttige anvendelser. Havde man valgt at løse et "real-world" problem, skulle man ikke blot introducere dette, men også bruge kræfter på at beskrive modelleringen, og redegøre for under hvilke antagelser dette problem kan behandles som et "hitting set problem". Dette kan nemt tage fokus fra artiklens egentlige formål. For et spil er det nemmere, fordi reglerne er veldefinerede. Da kendskabet til sudoku er ret udbredt, skal der ikke spildes for meget krudt introduktion af test-problemet, og også de læsere der ikke kender terminologien inden for grafteori vil alligevel straks have en idé om hvad algoritmen kan, en idé de måske ikke havde fået hvis artiklens abstract beskrev et "rigtigt" problem inden for f.eks. logistik eller IT.
Jeg vil anslå at sudokuproblemet har et fin balance mellem den abstraktion og konkrethed, der kræves af et godt testproblem.

  • 0
  • 0

Jeg forstår ikke, at Ing.dk kommer frem til, at der har taget 810 år, når det nu rent faktisk kun har taget 10-11 måneder i virkeligheden.

Måler i på en hundeårsligende måde eller hvad dækker det over? Jeg ved godt, at 810 cpuår, må svare til 810 cpu'er i et år - eller 1.620 i et halvt år, jeg synes bare ikke det giver mening når det nu rent faktisk kun har taget et år, at skrive at det vil tage 810 år.

  • 0
  • 0

Der står rent faktisk ikke, at "det vil tage 810 år". Der står ordret:

"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."

Han kunne også have skrevet 810 cpu-år, men det er måske ikke en lidt underlig angivelse... Han skriver jo netop, at det "svarer til", så derfor er der ikke noget problem i det. Jeg kan desuden oplyse, at regnestykket passer ganske nydeligt.

  • 0
  • 0

[quote]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.

Men kunne han ikke afprøve sin algoritme paa et mere seriøst problem?

[/quote]

Ved at loese sudokuproblemet loeser man jo netop potentielt mange saa kaldt serioese problemstillinger. Hvad er definitionen paa "serioes"?

  • 0
  • 0

Beviset er her en godtgørelse af, at man har gennemregnet alle muligheder ved brug af en hulens masse CPU-år. Man kunne jo nok savne fordum tiders elegance ved et uafviseligt matematisk-logisk bevis i klassisk forstand.

Maaske findes et saadant "elegant" bevis ikke? Og desuden er det stadig interessant at have bevist formodningen - uanset hvordan. Vaerdien ligger - udover at man nu ved at det er sandt at der ikke findes nogen entydig 16-Sudoku - i de forbedrede algoritmer! Se det er noget der kan vaere vaerdifuldt...selv for mere end eet enkelt seriost problem...maaske endda flere. Taenk sig, man har potentielt loest adskillige (utallige) "serioese" problemer ved at loese et "userioest" - jamen hvad er det dog for en verden vi lever i ;-)

Jesper

  • 0
  • 0

Det er lidt forstemmende ... af alle steder på Ing.dk ... at se indlæg i debatten, der tydeligt demonstrerer mangel på forståelse af

1) vigtigheden af grundforskning
2) matematikkens abstrakte natur, der (jo mere abstrakt og tilsyneladende uanvendeligt det umiddelbart ser ud) netop gør anvendelse af opnåede resultater mulig inden for vidt forskellige fagområder

Håber virkelig ikke de pågældende er eller har været beslutningstagere ...

  • 0
  • 0