Sudoku

Sudoku (数独, sūdoku) er en logisk opgave (hvis løsning dog ikke kræver brug af regning, selv om mange tror det), som går ud på, at man skal placere forskellige symboler, typisk cifre, i felter. Den klassiske, oprindelige opgave består af 81 felter eller celler fordelt på 9 vandrette rækker og 9 lodrette kolonner, der igen er samlet i ni blokke, hver med 3 gange 3 felter. Det gælder om at placere cifrene 1-9 således at hver række, kolonne og blok indeholder hvert ciffer én gang.

En sudoku har mindst 17 cifre placeret fra start^[1], og en ægte sudoku må kun have én løsning. Sudoku blev populært i Japan i 1986 og fik en ny blomstringsperiode i Storbritannien 2005. En af årsagerne til at Sudoku er meget populært i Japan, er sandsynligvis at det på nogle områder minder meget om det asiatiske brætspil Go.

Den 12. juni 2005 begyndte Politiken som den første danske avis at bringe en daglig sudoku. Jyllands-Posten fulgte trop dagen efter.

Løsning

En ægte sudoku har kun én løsning, og det skal være muligt at ræsonnere sig frem til placeringen af de enkelte tal i deres respektive felter. Der er hertil flere forskellige teknikker, der kan bruges sideløbende:

Eliminering

En af de simpleste strategier for placering af tal er eliminering. I eksemplet til højre kan flere mulige placeringer af tallet 1 udelukkes, da tallet allerede forekommer flere gange. De rækker og kolonner, der kan elimineres, er markeret med en rød gennemstregning. Efter elimineringen er der tre blokke med kun en mulighed for placering af tallet 1. Disse er vist med grønt. I dette eksempel er der efter en fornyet eliminering kun en mulighed for placering af det sidste 1-tal.

Komplettering

Tallet 2 er det eneste der mangler i den midterste række.

En metode er at se på hvilke tal der mangler for at skabe en komplet samling af tallene fra 1 til 9. I eksemplet til venstre mangler der kun et tal i den midterste række. Da tallet 2 mangler, placeres det i det ledige felt. En placering ved hjælp af denne teknik kan ofte føre til en situation, hvor en fornyet anvendelse af eliminering kan benyttes. Dette er dog ikke tilfældet her.

Afledt udelukkelse

Kan et tal i en blok kun placeres i en bestemt række eller kolonne, om end tallet ikke endeligt kan placeres, kan viden herom anvendes til eliminering af tallets placering i de andre blokke, som rækken eller kolonnen indgår i. I eksemplet til højre er de mulige placeringer af tallet 2 markeret med grønne cirkler i to blokke. I nederste venstre blok kan tallet kun placeres i midterste kolonne, hvilket udelukker placering i denne kolonne i blokken ovenover (markeret med blåt kryds). I denne blok er placering af tallet 2 hermed henvist til cellen i blokkens øverste højre hjørne.

Parrede tal

Kombinationen 48 optræder to steder i den fremhævede række, hvorfor tallene 4 og 8 kan elimineres i de øvrige felter i rækken

Optræder den samme kombination af to mulige tal i en række, kolonne eller blok, kan tallene fjernes i de øvrige celler i rækken, kolonnen eller blokken. På tegningen til venstre optræder den situation i den fremhævede kolonne. Ved betragtning af de mulige tal i de enkelte celler, fremkommer der i to af cellerne kombinationen 48. I den sidste celle er den mulige kombination 34. Tallet 4 kan fjernes fra denne celle, idet pardannelsen 48 nødvendigvis vil kræve at tallet 4 optræder i en af de to celler parret optræder i. En tilsvarende metode kan også anvendes hvis tre celler indeholder den samme kombination af tre tal, eller i sjældne tilfælde, hvis fire celler indeholder den samme kombination af fire tal.

En variant af denne metode er eliminering af de øvrige mulige tal i to celler, hvis disse to celler er de eneste der indeholder en bestemt talkombination. Denne variant er også gyldig for tre celler med tre mulige tal osv.

Rektangler

Har et tal præcis 2 mulige placeringer i en række eller kolonne, og tilsvarende på samme steder i en anden række eller kolonne, kan tallet udelukkes fra resten af de to kolonner eller rækker det kunne være placereret i. I eksemplet til højre er der to mulige placeringer af 7 i kolonne 3 og 8. Da disse placeringer er parvist overfor hinanden, kan de øvrige mulige placeringer af 7 derfor fjernes fra række 3 og 5.

Matematik omkring sudokuer

Der kan dannes 6.670.903.752.021.072.936.960 forskellige løsninger til den klassiske 9×9 sudoku. ^[2] Ses bort fra varianter, som fremkommer ved ombytning af rækker, søjler, ciffer-kodning og spejling og rotation er der dog "kun" 5.472.730.538 forskellige løsninger^[3].

Noter og henvisninger

^ Der kendes pr. 2006 over 500 sudoku'er med 17 cifre i startpositionen, som leder til én løsning og ingen med færre end 17 cifre. Det formodes derfor, at 17 er det mindste tal, men beviset herfor udestår ifølge prof. Wilson
^ Bevist i 2005 af Bertram Felgenhauer og Frazer Jarvis jf. den engelske wiki-side.
^ Samme kilde.

Foredraget Matematikken bag Sudokuer ved professor Robin Wilson i Aalborg den 27. september 2006.

Lignende logiske opgaver

[1] Der kendes pr. 2006 over 500 sudoku'er med 17 cifre i startpositionen, som leder til én løsning og ingen med færre end 17 cifre. Det formodes derfor, at 17 er det mindste tal, men beviset herfor udestår ifølge prof. Wilson

[2] Bevist i 2005 af Bertram Felgenhauer og Frazer Jarvis jf. den engelske wiki-side.

[3] Samme kilde.

[1]

[2]

[3]