Sudoku-leksikon · Matematik og computere

Sudokus matematik

Opdateret 2026-10-05

Et latinsk kvadrat med bokse

I et latinsk kvadrat optræder hvert symbol én gang i hver række og hver kolonne. En færdig sudoku er et latinsk kvadrat af størrelse 9 med én betingelse mere: Hver af de ni 3×3-bokse rummer også hvert ciffer én gang.

Kilder: Wikipedia: Latin square

Hvor mange gitre der findes

Bertram Felgenhauer og Frazer Jarvis talte de færdige 9×9-gitre i 2005: Der er 6.670.903.752.021.072.936.960, omkring 6,67 × 10²¹. Mange af dem er det samme gitter i forklædning. Regner man to gitre som ét, når det ene kan omdannes til det andet ved at bytte om på cifrene, dreje eller spejle gitteret eller ombytte rækker og kolonner på de måder, der bevarer et gyldigt gitter, er der 5.472.730.538 væsentligt forskellige gitre tilbage, et tal, som Ed Russell og Frazer Jarvis har beregnet.

Kilder: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minimummet på 17 givne tal

Ingen almindelig 9×9-sudoku med 16 eller færre givne tal har præcis én løsning. Gary McGuire, Bastian Tugemann og Gilles Civario viste dette med en udtømmende computersøgning og offentliggjorde resultatet i januar 2012. Sytten er minimum, ikke en garanti: Mange gitre med 17 givne tal har stadig mere end én løsning.

Kilder: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku som graffarvning

Tegn et punkt for hvert af de 81 felter, og forbind to punkter, når deres felter deler en række, en kolonne eller en boks. Denne sudokugraf har 810 forbindelser, og hvert punkt har præcis 20 naboer. At løse opgaven betyder at udvide de farver, som de givne tal fastlægger, så forbundne punkter aldrig har samme farve. Der kræves mindst ni farver, fordi hver række, kolonne og boks er en gruppe på ni punkter, der alle er forbundet, og ethvert færdigt gitter viser, at ni er nok.

Kilder: Wikipedia: Sudoku graph

Generelt svært, hurtigt ved 9×9

For sudokugitre, der kan vokse ubegrænset (n²×n² med n×n-bokse), er det NP-komplet at afgøre, om et delvist udfyldt gitter kan gøres færdigt, et resultat, som Takayuki Yato og Takahiro Seta offentliggjorde i 2003. Effektive computerprogrammer løser typisk almindelige 9×9-opgaver på en brøkdel af et sekund, men tiden afhænger af programmet, computeren og opgaven.

Kilder: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Se også

Kilder

Alle artikler →