Sudoku’s ontcijferd

De eenvoud van sudoku’s draagt ongetwijfeld bij aan hun populariteit. Maar schijn bedriegt. Wiskundigen breken hun hoofd over de complexe structuur die de sudoku verbergt.

30 maart 2006

Sinds vorige zomer vormen sudoku’s een rage, die nog niet is uitgewoed. Nog steeds kun je geen treincoupé binnenlopen zonder iemand een sudoku te zien ‘kraken’. Ook wiskundigen zijn verslaafd geraakt aan de populaire breinbreker. Maar dan op hun manier.

Dat er begin deze maand in Italië een wereldkampioenschap sudoku’s oplossen werd gehouden, zegt genoeg over de populariteit van dit cijferraadsel. Puzzelaars krijgen geen genoeg van sudoku’s en puzzelmakers weten telkens weer nieuwe varianten te verzinnen. Zo zijn er driedimensionale sudoku’s, sudoku’s met letters, sudoku’s met kleuren, sudoku’s met extra spelregels, enzovoorts. Toch berusten al deze varianten op hetzelfde principe en wiskundigen die over dat principe nadenken, beperken zich daarom tot de normale 9 × 9-sudoku.

Een sudoku van het wereldkampioenschap in Italië. De spelregels zijn eenvoudig: vul het rooster verder in zodat in iedere rij, in iedere kolom en in ieder dikomlijnd vierkant van 3 × 3 hokjes de cijfers 1 tot en met 9 voorkomen. Er is maar een oplossing mogelijk, die door logisch redeneren moet worden gevonden.

Het oplossen van een sudoku is leuk werk, maar zodra alle cijfers zijn ingevuld, volgt de minder spannende controle. Bevat iedere rij, iedere kolom en ieder vierkant echt de cijfers 1 tot en met 9? Het triomfantelijke gevoel wanneer het laatste cijfer is ingevuld, verdwijnt snel door dit vervelende controlewerkje. Is het misschien voldoende om alleen de rijen en de kolommen na te gaan? Volgt dan misschien vanzelf dat de vierkanten ook in orde zijn? Het antwoord is: nee. Immers, neem een ingevulde sudoku en verwissel de bovenste rij met de onderste. De rijen en kolommen van de nieuwe ‘sudoku’ voldoen nog steeds aan de spelregels, maar de vierkanten normaalgesproken niet meer. Helaas, ook de vierkanten moeten worden gecontroleerd.

De winnares van het wereldkampioenschap Sudoku is econome Jana Tylova uit Tsjechië. Ze had maar vijftien minuten nodig om de bovenstaande extra moeilijke sudoku op te lossen.

Sudoku’s ogen heel eenvoudig en roepen simpele vragen op. Toch geeft de sudoku zijn geheimen niet gemakkelijk prijs. In dit artikel bekijken we eerst hoeveel verschillende sudoku’s er eigenlijk bestaan. Daarna vragen we ons af hoeveel begincijfers nodig zijn om een unieke oplossing te vinden. Twee eenvoudige vragen, met lastige antwoorden.

Hoeveel sudoku’s zijn er?

Om met de deur in huis te vallen: er bestaan maar liefst 6.670.903.752.021.072.936.960 sudoku’s. Beter gezegd, dit is het aantal ingevulde sudokuvelden. Er is een verschil tussen een ingevuld sudokuveld en een sudokupuzzel. Een sudokupuzzel bevat namelijk alleen een paar begincijfers van een sudokuveld. Er zijn natuurlijk veel manieren om die begincijfers te geven. Daarom is het aantal sudokupuzzels nog veel groter dan het aantal sudokuvelden.

Felgenhauer en Jarvis zijn degenen die het aantal sudoku’s hebben uitgerekend. Dat was een bewerkelijke klus, omdat er tot nu toe geen eenvoudige formule is gevonden voor het aantal n² x n²-sudokuvelden. Of iemand ooit een eenvoudige formule zal vinden, is de vraag. Ook nu het aantal 9 × 9-sudokuvelden bekend is, blijft de uitkomst 6.670.903.752.021.072.936.960 verbazen. Dit getal is namelijk gelijk aan 9! x 72² x 2⁷ x 27.704.267.971, waarin de laatste factor een priemgetal is, en dus niet verder ontbonden kan worden. Eigenlijk is alleen de factor 9! (‘negen faculteit’) gemakkelijk te verklaren. Dat kan namelijk met verwisselingen.

Verwisselingen

In een sudoku hebben de cijfers 1 tot en met 9 alleen een symbolische waarde. Dat betekent dat de structuur van een sudoku niet verandert wanneer je bijvoorbeeld het cijfer 3 met het cijfer 4 verwisselt. Dat moet natuurlijk wel consequent gebeuren, dus alle drieën moeten met alle vieren verwisseld worden. Ook mogen de drieën door de vieren vervangen worden, vervolgens de vieren door de achten, de achten door de tweeën, de tweeën door de zevens, enzovoorts. Dat kunnen we in een schema zetten:

Dit schema is maar een van de vele mogelijkheden. Om het aantal schema’s – en dus het aantal rolverwisselingen van de negen cijfers – te tellen, begin je met een leeg schema:

Kies voor het linker vraagteken een van de negen cijfers, zeg een zes, en vul dat in het schema in:

Voor het volgende vraagteken in het schema, zijn er nog maar acht cijfers over, omdat de zes niet tweemaal gebruikt mag worden. Zodra ook voor het tweede vraagteken een keuze is gemaakt, zijn er voor het derde vraagteken nog maar zeven cijfers waaruit je kunt kiezen. Voor het vierde vraagteken zijn er nog zes cijfers mogelijk, enzovoorts.

Het totale aantal schema’s vind je door per vraagteken het aantal cijfers te bepalen waaruit je mag kiezen, en door die aantallen met elkaar te vermenigvuldigen. Het aantal schema’s is dus:

9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362.880

en wordt ook wel afgekort als 9! (spreek uit: ‘negen faculteit’). Rolverwisseling van de negen cijfers in een sudoku kan op 9! manieren en daarom moet het aantal sudoku’s een veelvoud van 9! zijn.

In dit schema is een verwisseling van de getallen 1, 2, 3 en 4 te zien. Er zijn in totaal 4 × 3 × 2 × 1 = 24 van zulke verwisselingen.

Zoek de verschillen

Met veel vlijt, goed tellen en hun computer vonden Felgenhauer en Jarvis het totale aantal sudoku’s. Toch is dat nog niet het hele verhaal. Tussen al deze sudoku’s zitten er heel wat die nogal op elkaar lijken. Bijvoorbeeld twee sudoku’s waarin de drieën met de vieren zijn verwisseld. Rolverwisseling van de cijfers levert geen wezenlijk andere sudoku op! Om een idee te krijgen van het aantal echt verschillende sudoku’s is het daarom beter om het totale aantal sudoku’s te delen door 9!. Je filtert als het ware de dubbele sudoku’s eruit. Blijven over 18.383.222.420.692.992 verschillende sudoku’s.

Wie een sudoku een kwartslag draait, verandert rijen in kolommen en kolommen in rijen, en krijgt opnieuw een sudoku. Is dit een andere sudoku? Niet echt. Een sudoku kan drie keer een kwartslag gedraaid worden en genereert zo drie ‘nieuwe’ sudoku’s. Eigenlijk zijn telkens vier sudoku’s een en dezelfde. Zo blijft nog maar een kwart van het vorige aantal over: 4.595.805.605.173.248 stuks. Rekening houdend met dubbeltellingen – want sommige sudoku’s zijn rotatiesymmetrisch – zijn het er iets meer. 4.595.805.644.052.864 om precies te zijn.

Wat voor draaien geldt, geldt ook voor spiegelen. Teken een sudoku op papier, draai het vel om, en houd het tegen het licht. Is de gespiegelde sudoku wezenlijk anders? Verder mogen sommige rijen en kolommen van plaats ruilen. Men kan bijvoorbeeld zonder problemen de kolommen 1, 2 en 3 met elkaar verwisselen. De nieuwe sudoku voldoet immers aan de spelregels. Ook mag bijvoorbeeld het blok met de rijen 4, 5 en 6 verwisseld worden met het blok dat uit de rijen 7, 8 en 9 bestaat. Leveren zulke rij- en kolomverwisselingen weer een reeks sudoku’s op die eigenlijk allemaal hetzelfde zijn? Dat is moeilijk te zeggen. De een zegt dat deze sudoku’s op elkaar lijken, een ander vindt ze echt verschillend. Soms is wiskunde een kwestie van smaak.

Verschillende sudoku’s geteld

Dat er keuzes gemaakt moeten worden, weten ook Jarvis en Russell. Zij rekenden met verschillende varianten. Bij één variant mocht er alleen geroteerd worden, bij een andere waren alleen de rij- en kolomverwisselingen toegestaan. De strengste selectie kregen ze door alle bewerkingen toe te laten: rolverwisseling van de cijfers, rotaties, spiegelingen en de rij- en kolomverwisselingen. Deze variant beschouwt heel veel sudoku’s als gelijken en dat haalt aardig de bezem door de aantallen. Uiteindelijk bleef ongeveer 0,00000000008% van de sudoku’s over. Toch nog een slordige 5.472.730.538.

Puzzelmakers maken dankbaar gebruik van de wetenschap dat veel sudoku’s eigenlijk hetzelfde zijn. Wanneer zij één sudokupuzzel hebben, kunnen zij vele nieuwe maken. Ze kunnen een rolverwisseling van de cijfers toepassen, de puzzel draaien of spiegelen, of bepaalde rijen en kolommen verwisselen. En de puzzelaar, die lost telkens weer dezelfde sudoku op…

Het is natuurlijk wel een beetje frustrerend om eigenlijk steeds dezelfde puzzel op te lossen. Aan de andere kant: als je eenmaal een goede strategie hebt gevonden om een bepaalde Sudoku op te lossen, dan kan je die lekker vaak gebruiken.

Hoeveel begincijfers?

Neem het de puzzelmaker niet kwalijk, want een sudokupuzzel opstellen is lastig. Wie te veel begincijfers weggeeft, maakt de puzzel te gemakkelijk. Als er te weinig begincijfers zijn, bestaat het risico dat de oplossing niet uniek is, dus dat er verschillende oplossingen mogelijk zijn. De cijfers kunnen dan niet meer door logisch redeneren worden gevonden. Dat betekent dat de puzzelaar op een gegeven moment een cijfer moet raden, en dat is niet de bedoeling.

Er zijn sudoku’s met 20 begincijfers die een unieke oplossing hebben, en er zijn sudoku’s met 70 begincijfers die verschillende oplossingen toelaten. De vraag rijst voor welk aantal begincijfers er altijd meerdere oplossingen zijn. En voor hoeveel begincijfers is de oplossing altijd uniek?

Om met de laatste vraag te beginnen: 78, 79, 80 of 81 begincijfers garanderen een unieke oplossing. Voor 77 begincijfers of minder zijn er puzzels te verzinnen die meerdere oplossingen hebben. In de onderstaande sudoku moeten nog twee zevens en twee negens worden ingevuld. Dat kan op twee manieren!

Een sudoku met 77 begincijfers en twee oplossingen.

De omgekeerde vraag is moeilijker. In ieder geval heeft een sudoku met zeven begincijfers of minder geen unieke oplossing. De reden is dat er twee cijfers niet gegeven zijn, zeg de 8 en de 9. De puzzelaar mag dan kiezen waar hij de achten neerzet en waar de negens, want een rolverwisseling van twee cijfers breekt de spelregels niet!

De puzzelmaker weet dus dat hij ten minste acht begincijfers moet geven. Maar is er een grotere ondergrens? Dit is een open vraag. Alle puzzels met een unieke oplossing die men tot nu toe heeft gevonden, hebben minstens zeventien begincijfers. Men vermoedt daarom dat zeventien begincijfers de grootste ondergrens is. Maar bewezen is het niet. Wie weet bestaat er een uniek oplosbare sudoku met meer dan zeven, maar minder dan zeventien begincijfers. Wiskundigen hebben een aardige puzzel aan dit vraagstuk.