Sinds een jaar of 10 is Nederland, samen met veel andere landen, in de ban geraakt van de van oorsprong Japanse sudoku’s. In verschillende vormen, moeilijkheidsgraden en met of zonder extra regels en toevoegingen, is de sudoku een van de meest gemaakte cijferpuzzels. Hoewel het idee van de puzzel redelijk eenvoudig is, kan het veel tijd en frustratie kosten om er een op te lossen. Maar afgezien van het oplossen roept ook het maken van deze puzzels bij sommigen veel vragen op. Hoe verschillend zijn alle sudokupuzzels, en hoe veel mogelijkheden zijn er om zo’n veld in te vullen? En hoeveel zegt het aantal begincijfers van een sudoku over het aantal mogelijke oplossingen?

 
Het aantal sudokupuzzels dat rondgaat in kranten en tijdschriften is enorm, en voor wie daar nog niet genoeg aan heeft zijn er puzzelboeken en mobiele apps beschikbaar. Dit riep bij Bertram Felgenhauer en Frazer Jarvis de vraag op of er ook een limiet bestaat aan dit aanbod, en hoeveel sudoku’s gemaakt kunnen worden.
Om die vraag te beantwoorden dient eerst gekeken te worden naar het aantal mogelijke manieren om een veld van 9 bij 9 zo in te vullen dat het aan alle criteria van een sudoku voldoet. In juni 2005 publiceerden Felgenhauer en Jarvis een artikel met hun berekeningen van dit aantal. Belangrijk om te bedenken is dat het duo hier op zoek is naar het aantal ingevulde sudokuvelden, dus het aantal geheel ingevulde velden van 9 bij 9. Dit verschilt van de vraag naar het aantal verschillende sudokupuzzels, waarbij slechts een aantal cijfers is ingevuld.

 

Op zoek naar mogelijkheden

De basis van de methode van Felgenhauer en Jarvis is een zogeheten brute force calculation: een berekening waar een deel bestaat uit het samenstellen van alle mogelijke uitkomsten om vervolgens te controleren welk van deze uitkomsten correct is. Hiervoor kan een algoritme geschreven worden dat kan controleren of een veld van 9 bij 9 een correct sudokuveld is. Echter, gezien het feit dat er  manieren zijn om een veld van 9 bij 9 te vullen met de getallen 1 tot en met 9, zou een computer hier oneindig lang over doen. Daarom wilden Felgenhauer en Jarvis het aantal ingevulde velden dat gecheckt moet worden zo ver mogelijk reduceren.

De eerste stap die het duo zet is het opdelen van een sudokuveld in 9 verschillende blokken, gemarkeerd als B1 tot en met B9:


Om de rest van het onderzoek te vereenvoudigen wordt blok B1 vastgesteld in de standaard vorm:

Vervolgens wordt gezocht naar het aantal manieren om blok B2 en B3 in te vullen wanneer blok B1 gegeven is zoals in de standaard vorm. Vanuit deze verschillende invullingen van B2 en B3 wordt gekeken naar de mogelijkheid dat meerdere invullingen equivalent aan elkaar zijn in het opzicht dat ze allemaal hetzelfde aantal verschillende manieren hebben om de rest van het sudokuveld in te vullen. Dit zou betekenen dat niet voor ieder mogelijk B2-B3 paar het aantal manieren om het verdere veld in te vullen berekend hoeft te worden, maar slechts voor één van de equivalente mogelijkheden. Dit reduceert het aantal ingevulde velden dat gecheckt moet worden.

Met deze methode berekenen Felgenhauer en Jarvis het aantal mogelijke sudokuvelden met blok B1 in de standaard vorm. Met dit aantal kunnen we ook het totaal aantal mogelijke sudokuvelden berekenen, en wel door herordening. Wanneer een sudokuveld correct is ingevuld, blijft dit veld nog steeds een kloppende sudoku wanneer alle getallen 1 worden verwisseld met de getallen 2. Zo kan ieder getal met elkaar verwisseld worden, waarbij er voor het eerste getal 9 mogelijkheden zijn, voor het tweede getal nog 8 en zo verder tot één overgebleven mogelijkheid voor het negende getal. Dit betekent dat blok B1, in de berekening gegeven in de standaard vorm, op  manieren herordend kan worden en dat daarmee alle mogelijke invullingen van dit blok gedekt worden. Hierdoor dient de uitkomst van het aantal mogelijke sudokuvelden met B1 gegeven in de standaard vorm vermenigvuldigd te worden met 362880 om zo het totaal aantal mogelijke velden te vinden.

Met B1 gegeven in de standaard vorm is het doel om uit te vogelen hoe B2 en B3 vervolgens ingevuld kunnen worden zonder de sudokuvoorwaarden te schaden. Allereerst wordt gekeken naar de 3 rijen. Van de bovenste rij is te zien dat de getallen 4 tot en met 9 nog gebruikt moeten worden en dat deze verdeeld moeten worden over 2 groepen van 3, wat kan op  manieren. Als de bovenste rij van B2 wordt aangevuld met de groep {4,5,6} en de bovenste rij van B3 met {7,8,9}, kan de rest van de blokken als volgt worden ingevuld:

Omdat er voor elke groep 3!=6 mogelijkheden zijn om de 3 cijfers te ordenen, komt dit uit op mogelijke indelingen van B2 en B3 wanneer de groepen op de eerste rij zijn gegeven als hierboven. Hetzelfde geldt voor het omgekeerde, dus {7,8,9} in B2 en {4,5,6} in B3. Bij de andere 18 mogelijkheden gaat het anders, omdat de bovenste rijen van B2 en B3 dan bestaan uit een mix van getallen uit rij 2 en 3 van B1. Wanneer bijvoorbeeld de groepen {4,5,7} in B2 en {6,8,9} in B3 als bovenste rij worden gebruikt, zijn er de volgende mogelijkheden om de rest van de blokken te vullen:
Hierbij staan a, b en c voor de getallen 1, 2 en 3, en zijn er voor het invullen van a drie mogelijkheden. Wanneer bijvoorbeeld wordt ingevuld, maakt het vervolgens niet meer uit hoe de getallen 2 en 3 worden verdeeld over b en c. Dit omdat de volgorde de getallen binnen een horizontale groep al meegenomen wordt in de 3!. Hierdoor zijn er  mogelijkheden om de blokken met deze groepen aan te vullen. Dit maakt dat het totaal aantal manieren om de bovenste 3 blokken in te vullen, wanneer B1 is gegeven in de standaard vorm, uit op  manieren.

Dit betekent dat het totaal aantal manieren om de bovenste 3 blokken te vullen, is. In dit getal zijn niet alleen de standaard vorm, maar alle mogelijke vormen van B1 meegerekend.

Reduceren kun je leren

Wat hebben Felgenhauer en Jarvis bereikt nu ze dit weten? In principe zouden de twee vanaf dit punt kunnen beginnen met hun brute force calculations, aangezien ze alle mogelijke invullingen weten. Echter, het kost een computer ontzettend veel tijd om al deze 2612736 mogelijkheden langs te gaan. Het volgende doel is dus om te kijken welke van de mogelijkheden in zoverre equivalent zijn dat ze dezelfde hoeveelheid oplossingen hebben, waardoor slechts één van die equivalente mogelijkheden hoeft te worden uitgerekend.

Een van de reductiemogelijkheden is lexicografische reductie. Dit houdt in dat kolommen binnen een blok verplaatst worden. Wanneer alleen gehele kolommen verwisseld worden met andere gehele kolommen binnen hetzelfde blok, heeft dit geen invloed op de correctheid en het aantal mogelijke oplossingen van de sudoku. Men kan zich voorstellen dat een willekeurig, half ingevuld sudokuveld evenveel verdere oplossingen heeft als hetzelfde half ingevulde veld waar kolom 4 en 5 in zijn geheel verwisseld zijn. De lexicografische methode houdt in dat binnen B2 en B3 de kolommen zo verwisseld worden dat de bovenste rij bestaat uit oplopende getallen binnen het blok. Dit geeft voor ieder blok 6 mogelijkheden om de kolommen te ordenen, en dus 62=36 in totaal. Vervolgens worden B2 en B3 eventueel met elkaar verwisseld, zodat het getal linksboven in B2 lager is dan het getal linksboven in B3. Dit verdubbelt het aantal ordeningsmogelijkheden, waardoor we uitkomen op 72. Hieruit volgt dat we het aantal mogelijkheden dat we moeten checken kunnen delen door 72, gezien de equivalentie van velden waarin gehele kolommen zijn verwisseld. Dit reduceert het aantal tot . Al deze velden zijn lexicografisch ingevuld, wat betekent dat de bovenste rij getallen per blok oplopend is. Alle overige velden, die met deze methode gereduceerd zijn, zijn equivalent aan een van deze velden en hebben dus dezelfde kolommen, maar niet in deze volgorde.

Naast lexicografische reductie gebruiken Felgenhauer en Jarvis nog een aantal andere manieren om het aantal oplossingen dat moet worden gecheckt te verkleinen. Zo kijken ze bijvoorbeeld naar de onderlinge verwisseling van de bovenste drie blokken, waarna via herordening de ‘nieuwe’ B1 weer in de standaardvorm wordt teruggebracht. Verder is het duidelijk dat het in de volgende invulling van de bovenste 3 blokken geen verschil zou maken voor de invulling van de overige blokken, als de roodgekleurde achten en negens verwisseld zouden worden.


Dit houdt in dat beide situaties een gelijk aantal verdere invullingen heeft, wat betekent dat het aantal maar voor één van de twee berekend hoeft te worden en dat dit aantal vervolgens eenvoudigweg verdubbeld kan worden om op het totale aantal te komen.

Via dit soort wegen komen Felgenhauer en Jarvis  op een steeds kleinere selectie invullingen van de bovenste 3 blokken, totdat het eindigt in een selectie van een schamele 44  van de originele 2612736 manieren. Dit getal is dermate klein dat een computer in een redelijk overzichtelijke tijd de brute force calculation kan toepassen. Wanneer deze berekening is uitgevoerd komt hieruit het aantal mogelijke invullingen van een sudokuveld, , wat als volgt kan worden  weergegeven:

Waarbij  staat voor het aantal manieren waarop één van de 44 overgebleven invullingen van B2 en B3 verder ingevuld kan worden, en  staat voor het aantal invullingen dat equivalent is aan, en dus evenveel verdere invullingen heeft als, deze bepaalde invulling. De 9! is nodig om niet alleen het aantal invullingen met B1 in de standaard vorm uit te rekenen, maar het complete aantal invullingen met iedere mogelijke B1. Uit de berekeningen van Felgenhauer en Jarvis kwam hier het volgende getal uit:

Kan het ook makkelijker?

Via deze methode kwamen Felgenhauer en Jarvis op het exacte aantal sudokuvelden uit, maar Kevin Kilfoil heeft een iets eenvoudigere maar verrassend nauwkeurige benadering van dit aantal gevonden. Zijn methode begint met het feit dat een sudokuveld op manieren kan worden ingevuld zodat ieder blok alle getallen 1 tot en met 9 slechts eenmaal bevat. Verder gebruikt hij de vindingen van Felgenhauer en Jarvis dat de blokken B1-B3 op 948109639680 manieren kunnen worden gevuld zodat ieder blok en iedere rij de getallen 1 tot en met 9 slechts eenmaal bevat. Hetzelfde geldt voor blokken B4-B6 en B7-B9. Dit betekent dat het gehele veld op 9481096396803 manieren ingevuld kan worden zodat ieder blok en iedere rij aan de voorwaarden van een sudoku voldoet. Dit betekent dat het deel van de (9!)9 velden dat ook voldoet aan de rijvoorwaarde gelijk is aan:

Het aantal manieren om een veld zo te vullen dat alle blokken en alle kolommen aan de sudokucriteria voldoet, is logischerwijs ook . Wat Kilfoil vervolgens doet is aannemen dat de rijvoorwaarde en de kolomvoorwaarde onafhankelijk van elkaar zijn. Door dit aan te nemen kan hij stellen dat het deel van de ingevulde velden dat ook voldoet aan zowel de  rij- als de kolomvoorwaarde gelijk is aan:

Hoewel dit getal niet het exacte aantal mogelijkheden is, ligt het er niet ver vanaf. Met een verschil van 0,2% is Kolfoil met zijn relatief simpele benadering zeer dicht bij het correcte antwoord van Felgenhauer en Jarvis gekomen. De reden dat het antwoord niet precies goed is ligt in het feit dat de voorwaarde voor rijen en kolommen niet geheel onafhankelijk van elkaar is. Het is namelijk eenvoudig in te  zien dat wanneer de bovenste 3 rijen zo zijn ingevuld dat ze aan alle voorwaarden voldoen, dit invloed heeft op de invulling van de meest linker 3 kolommen, aangezien 9 van deze getallen al ingevuld zijn met de bovenste 3 rijen.

Sudokupuzzels

Nu het aantal mogelijke sudokuvelden gevonden is, is de volgende vraag wat dit getal zegt over het aantal mogelijke sudokupuzzels. In het antwoord op deze vraag schuilt helaas een kleine teleurstelling, het aantal mogelijke sudokupuzzels is namelijk haast onmogelijk te benaderen en nadert oneindig. Van ieder ingevuld sudokuveld zijn namelijk meerdere sudokupuzzels te maken, afhankelijk van hoeveel en welke van de cijfers als gegeven in de puzzel worden gezet. Wanneer iemand een sudoku maakt en vervolgens precies dezelfde sudoku krijgt met andere begincijfers, is de kans zelfs groot dat die persoon niet of pas als hij al klaar is zal merken dat hij tweemaal hetzelfde veld heeft ingevuld.

Over het aantal sudokupuzzels valt dus niets concreets te zeggen, maar hoe zit dat met het aantal begincijfers? Bestaat er een bepaald maximum of minimum waarbij men al dan niet zeker kan zijn dat er slechts één unieke oplossing voor de sudoku is? Op deze vraag is het antwoord ja, maar dit maximum zegt niet erg veel. Het is namelijk zo dat een sudoku zelfs wanneer 77 van de 81 vakken zijn ingevuld zijn, toch nog meerdere oplossingen kan hebben. Neem bijvoorbeeld de bovenstaande afbeelding van B1-B3 waarbij twee achten en negens rood gekleurd zijn. Wanneer een geheel sudokuveld ingevuld is op de velden van deze twee achten en negens na, zijn er twee mogelijke oplossingen omdat de achten en negens onderling inwisselbaar zijn.

Pas wanneer van een sudokupuzzel 78 van de 81 cijfers vooraf gegeven zijn kan men er dus geheel zeker weten dat er maar één oplossing mogelijk is, maar dan is de sudoku natuurlijk niet meer al te uitdagend. Bij een aantal begincijfers van onder de 78 is er dus kans dat de puzzel op meerdere manieren opgelost kan worden. Wanneer minder dan 8 cijfers vooraf gegeven zijn is er zelfs zekerheid over het bestaan van meerdere oplossingen. Wanneer er 7 of minder begincijfers zijn, zijn er namelijk minstens 2 getallen tussen de 1 en de 9 nog niet aanwezig in de puzzel. Dit betekent dat, wanneer bijvoorbeeld de getallen 8 en 9 nog niet voorkomen in de puzzel, alle getallen 8 en 9 onderling verwisseld kunnen worden zonder de sudokucriteria te schaden. Het aantal begincijfers waarbij er zekerheid is over het bestaan van meerdere oplossingen is dus 7 en alles daaronder. Van een willekeurige sudokupuzzel met 14 gegeven getallen is dus niet direct te zeggen of het een unieke  oplossing heeft. Wat wel zeker is, is dat er na het oplossen van deze puzzel nog vele andere zullen volgen, wellicht zelfs met haast hetzelfde ingevulde veld.

Dit artikel is geschreven door Marleen Schumacher