Sudoku-encyclopedie · Wiskunde en computers

De wiskunde van Sudoku

Bijgewerkt op 2026-10-05

Een Latijns vierkant met blokken

In een Latijns vierkant komt elk symbool één keer in elke rij en elke kolom voor. Een volledig ingevulde Sudoku is een Latijns vierkant van grootte 9 met één extra voorwaarde: elk van de negen blokken van 3×3 bevat ook elk cijfer één keer.

Bronnen: Wikipedia: Latin square

Hoeveel roosters er zijn

Bertram Felgenhauer en Frazer Jarvis telden in 2005 de volledig ingevulde roosters van 9×9: er zijn er 6.670.903.752.021.072.936.960, ongeveer 6,67 × 10²¹. Veel daarvan zijn hetzelfde rooster in een andere gedaante. Als je twee roosters als één telt wanneer je het ene in het andere kunt veranderen door de cijfers anders te labelen, het rooster te draaien of te spiegelen, of rijen en kolommen te herschikken op manieren die het rooster geldig houden, blijven er 5.472.730.538 wezenlijk verschillende roosters over. Dit aantal werd berekend door Ed Russell en Frazer Jarvis.

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

Het minimum van 17 begincijfers

Geen enkele standaard Sudoku van 9×9 met 16 of minder begincijfers heeft precies één oplossing. Gary McGuire, Bastian Tugemann en Gilles Civario toonden dit aan met een uitputtende computerzoektocht en kondigden het resultaat in januari 2012 aan. Zeventien is het minimum, geen garantie: veel roosters met 17 begincijfers hebben nog steeds meer dan één oplossing.

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

Sudoku als graafkleuring

Teken voor elk van de 81 cellen één punt en verbind twee punten wanneer hun cellen in dezelfde rij, kolom of hetzelfde blok liggen. Deze Sudoku-graaf heeft 810 verbindingen, en elk punt heeft precies 20 buren. De puzzel oplossen betekent dat je de door de begincijfers vastgelegde kleuren uitbreidt, zodat verbonden punten nooit dezelfde kleur hebben. Er zijn minstens negen kleuren nodig, omdat elke rij, kolom en elk blok een groep van negen punten is die allemaal onderling verbonden zijn. Elk volledig ingevuld rooster laat zien dat negen kleuren voldoende zijn.

Bronnen: Wikipedia: Sudoku graph

Moeilijk in het algemeen, snel voor 9×9

Voor Sudoku-roosters die onbeperkt groter kunnen worden (n²×n² met blokken van n×n) is bepalen of een gedeeltelijk ingevuld rooster kan worden voltooid NP-compleet. Takayuki Yato en Takahiro Seta publiceerden dit resultaat in 2003. Efficiënte computerprogramma's lossen gewone puzzels van 9×9 doorgaans in een fractie van een seconde op, al hangt de tijd af van het programma, de computer en de puzzel.

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

Zie ook

Bronnen

Alle artikelen →