Sudoku en grafentheorie - NEMO Kennislink
Auteur: Alex van den Brandhof | 10 juli 2007
Met behulp van grafentheorie hebben twee wiskundigen aangetoond dat er een formule moet bestaan waarmee je kunt vaststellen hoeveel oplossingen een sudoku heeft. Ook hebben zij aangetoond dat het aantal sudoku's dat groter is dan het standaard 9 bij 9 formaat, drastisch afneemt naarmate de afmetingen groter worden.
Van de bekende sudoku, waarvan de populariteit nog altijd niet te stuiten is, wordt vaak gezegd dat bij het oplossen van de puzzel geen wiskunde nodig is. Toch roept de puzzel wiskundige vragen op: hoeveel sudoku's bestaan er, is een puzzel met minder gegeven startwaarden altijd lastiger dan een puzzel met meer startwaarden, wat is het kleinste aantal startwaarden dat nodig is wil de sudoku een unieke oplossing hebben?
Bij een sudoku moeten de hokjes zó worden ingevuld met de getallen 1 tot en met 9, dat elke rij, elke kolom en elk deelvierkant van 3 bij 3 elk van deze getallen precies één keer bevat. De sudoku hierboven heeft 17 startwaarden. Tot op heden heeft niemand een sudoku met minder startwaarden kunnen maken.
In een artikel uit het juninummer van de Notices of the American Mathematical Society geven Agnes M. Herzberg en M. Ram Murty, beiden werkzaam op de Queen's University in Kingston (Canada), antwoorden op enkele vragen.
Zij vertalen een sudoku in een graaf, een figuur bestaande uit punten (de knopen van de graaf) en lijnen. Zo'n graaf heeft 81 knopen, die de hokjes van de puzzel representeren. Een lijn verbindt twee knopen, indien die knopen hokjes voorstellen uit eenzelfde rij, eenzelfde kolom of eenzelfde deelvierkant.
Hoewel sudoku's doorgaans met de getallen 1 tot en met 9 worden ingevuld, kun je natuurlijk negen willekeurige symbolen gebruiken, zoals negen letters of negen kleuren. Een wiskundige noemt een graaf met gelabelde knopen een kleuring van de graaf. Een sudoku is in de begintoestand nog niet helemaal gekleurd: alleen de knopen die corresponderen met de startwaarden hebben een kleur. Als elke knoop is gekleurd en geen twee met elkaar verbonden knopen dezelfde kleur hebben, heet de graaf goed.
In termen van grafentheorie kunnen we zeggen dat een sudoku een oplossing heeft, indien de bijbehorende graaf een goede kleuring heeft.
Deze sudoku stond in Air Canada's in-flight magazine. Hoewel het aantal startwaarden met 29 aan de grote kant is, heeft deze sudoku twee mogelijke oplossingen.
Herzberg en Murty gebruikten theorieën uit de grafentheorie om aan te tonen dat er een formule moet bestaan dat het aantal mogelijke oplossingen bij een gegeven sudoku geeft. Een goed ontworpen sudoku heeft precies één oplossing. Een probleem echter is dat Herzberg en Murty's bewijs van het bestaan van een dergelijke formule, niet constructief is. Dat wil zeggen: ze hebben laten zien dát zo'n formule moet bestaan, maar ze hebben zo'n formule niet kunnen vinden.
Een Latijns vierkant is een vierkant van n bij n hokjes, waarin de getallen 1 tot en met n zodanig worden ingevuld dat elke rij en elke kolom elk getal precies één keer bevat. Een sudoku heeft met de deelvierkanten een extra eis; een sudoku is dus een speciaal geval van een Latijns vierkant. Al in 1975 werd berekend dat er 5.524.751.496.156.892.842.531.225.600 (ongeveer 5,5 × 1027) Latijnse vierkanten van 9 bij 9 bestaan.
Twee jaar geleden berekenden Bertram Felgenhauer en Frazer Jarvis het aantal sudoku's. Het aantal essentieel verschillende sudoku's is 5.472.730.538; lees het onderstaande Kennislinkartikel hierover.
Sudoku's ontcijferd
Hoewel het aantal sudoku's een stuk kleiner is dan het aantal Latijnse vierkanten, zijn er in elk geval meer dan genoeg om een toiletrol mee te vullen.
Herzberg en Murty hebben gekeken naar aantallen sudoku's van andere afmetingen. De standaardsudoku is 9 bij 9 hokjes groot en heeft negen deelvierkanten van 3 bij 3, maar je kunt ook kijken naar sudoku's van bijvoorbeeld 4 bij 4 (met vier deelvierkanten van 2 bij 2) of 16 bij 16 (met zestien deelvierkanten van 4 bij 4). Hoeveel Latijnse vierkanten van n2 bij n2 zijn ook sudoku's?
Deze vraagt lijkt onmogelijk te beantwoorden, omdat niemand weet hoeveel Latijnse vierkanten er bestaan met een afmeting groter dan 11 bij 11. Toch hebben Herzberg en Murty een bijdrage kunnen leveren. Zij hebben voor een willekeurig Latijns vierkant van n2 bij n2 het volgende aangetoond: hoe groter n is, hoe kleiner de kans is dat het Latijnse vierkant een sudoku is. Deze kans daalt naar nul als n voldoende groot wordt genomen. Hiermee hebben zij bewezen dat het aantal sudoku's substantieel kleiner is dan het aantal Latijnse vierkanten.