Matematik i Sudoku fører til 'Richter-skala' af puslespillets hårdhed

Den globale fascination af Sudoku har ført til en pludselig interesse for puslespillets matematiske egenskaber. I de sidste par måneder på denne blog har vi set på, hvordan matematikere har løst det minimale Sudoku-problem, og endda hvordan de har brugt Sudoku-matematikken til at kryptere billeder.

I dag får vi et anderledes syn på Sudoku takket være arbejdet af Maria Ercsey-Ravasz ved Babes-Bolyai University i Rumænien og Zoltan Toroczkai ved University of Notre Dame i Indiana.

Disse fyre har udviklet en måde at måle sværhedsgraden af ​​et bestemt Sudoku-puslespil og sige, at deres Richter-skala af puslespilssværhedsgrad kan anvendes på en lang række andre spil.

Først lidt baggrund om Sudoku. Dette er et talpuslespil, der består af et 9 x 9 gitter, hvor nogle celler indeholder ledetråde i form af cifre fra 1 til 9. Løserens opgave er at udfylde de resterende celler, så hver række, kolonne og 3×3 boks i gitteret indeholder alle ni cifre. Derudover kan hvert gitter kun have én løsning.

Sudoku-gåder klassificeres generelt som lette, mellemstore eller svære, hvor gåder generelt har flere startspor, men ikke altid nemmere at løse. Men at kvantificere vanskeligheden matematisk er svært.

Nu siger Ercsey-Ravasz og Toroczkai, at de har udarbejdet en måde at gøre det på ved hjælp af algoritmisk kompleksitetsteori. De påpeger, at det er nemt at designe en algoritme, der løser Sudoku ved at teste hver kombination af cifre for at finde den, der virker. Den slags brute force-løsning garanterer dig et svar, men ikke særlig hurtigt.

I stedet leder algoritmedesignere efter smartere måder at finde løsninger på, der udnytter problemets struktur og begrænsninger. Disse algoritmer og deres adfærd er mere komplekse, men de får hurtigere svar.

Det centrale i Ercsey-Ravasz og Toroczkais argument er, at fordi en algoritme afspejler problemets struktur, er dens adfærd – de drejninger og drejninger, den følger gennem tilstandsrummet – et godt mål for problemets sværhedsgrad.

For at demonstrere dette, tackler de eksemplet med Sudoku. I stedet for brute force-løsningen designer de en meget mere elegant algoritme, der udnytter puslespillets forskellige begrænsninger, såsom det faktum, at hver række kolonne og undergitter skal indeholde alle cifrene fra 1 til 9.

På denne måde transformerer de problemet til en type kendt af kompleksitetsteoretikere som et k-sat problem.

De starter med at indsætte et tilfældigt sæt tal i gitteret og følger algoritmens bane gennem tilstandsrummet, mens den søger efter en løsning. For et simpelt problem er denne bane enkel, som vist i den øverste af de to figurer øverst i dette indlæg.

Men alt det ændrer sig for et vanskeligt problem. Ercsey-Ravasz og Toroczkai tester deres algoritme mod et Sudoku-gitter så hårdt, at det har sit eget navn: platinblond. Resultatet er vist i nederste halvdel af figuren. Det er betydeligt mere komplekst og tager ti gange så lang tid at løse.

Ercsey-Ravasz og Toroczkai siger, at for vanskelige problemer bliver banen kaotisk, før de beslutter sig for en løsning. Faktisk er den tid, det tager at undslippe denne kaotiske tilstand, en simpel sværhedsgrad.

På det grundlag skaber de en 'Richter-skala' af puslespilssværhedsgrad baseret på flugthastigheden. Skalaen går fra 1 til 4, hvor en er den nemmeste og 4 er ultrahård.

De siger, at denne skala korrelerer overraskende godt med de subjektive menneskelige vurderinger med 1 svarende til lette gåder, 2 til mellemstore gåder og 3 til svære gåder. Den platinblonde har en sværhedsgrad på 3,5789.

En interessant konsekvens er, at der ikke kendes noget Sudoku-puslespil med en sværhedsgrad på 4. Og antallet af ledetråde er heller ikke altid en god sværhedsgrad. Ercsey-Ravasz og Toroczkai siger, at de testede mange gåder, inklusive flere med de 17 ledetråde, minimumsantallet og nogle få med 18 ledetråde.

Disse var alle nemmere at løse end platinblond, som har 21 spor. Det skyldes, at hårdheden af ​​puslespillet ikke kun afhænger af antallet af ledetråde, men også af deres position.

Et interessant spørgsmål er nu, om der faktisk findes et ultrahårdt puslespil med en sværhedsgrad på 4, og hvordan det kan findes.

Mere væsentligt end dette er, at Ercsey-Ravasz og Toroczkais metode generaliserer til alle k-sat problemer af samme klasse som Sudoku. Så sværhedsgraden af ​​disse problemer kan alle klassificeres efter lignende Richter-skalaer.

Det efterlader kun et spørgsmål - hvad skal sværhedsgraden af ​​puslespil hedde? Det åbenlyse svar er Ercsey-Ravasz og Toroczkai skalaen eller ERT skalaen. Eventuelle andre forslag i kommentarfeltet nedenfor.

Ref: arxiv.org/abs/1208.0370 : Kaoset i Sudoku

skjule