Computers, wiskunde en spelletjes hebben veel met elkaar gemeen. Dat de eerste twee mij mateloos boeien, mag duidelijk zijn. Qua spelletjes ben ik een stuk kieskeuriger: de meeste boeien mij niet. Maar… zodra deze (in)direct wiskunde gebruiken, ben ik verkocht. De komende afleveringen gaan over de Sudoku zoals de titel al duidelijk heeft gemaakt.
Henk van de Kamer
Het zou mij verbazen als u niet weet wat een Sudoku is. Minder bekend is dat deze een deelverzameling is van de Latijnse vierkanten. Een Sudoku bevat in alle n rijen en n kolommen exact één keuze uit een set van n symbolen. Dat kunnen weer getallen, kleuren, letters of andere keuzes zijn. De waarde n noemen we de orde.
Deelverzameling
Er zijn 5.524.751.496.156.892.842.531.225.600 (https://oeis.org/A002860) Latijnse vierkanten van orde negen. De meeste daarvan zijn geen Sudoku omdat die een extra eis hebben. Namelijk dat elk van de negen drie bij drie vierkanten ook alle symbolen van de gebruikte set moet bevatten. In 2005 berekenden Felgenhauer en Jarvis (https://people.math.sc.edu/girardi/sudoku/enumerate.pdf) het aantal mogelijke Sudoku-oplossingen: 6.670.903.752.021.072.936.960 stuks. Ofwel slechts 0,00012 procent van alle mogelijke Latijnse vierkanten is een Sudoku-oplossing.
Er is geen algoritme bekend om een Latijns vierkant van orde negen te berekenen. Ofwel deze genereren met een computer is niets anders dan met brute kracht – op zijn Engels brute force – alle mogelijke distributies van negen sets te testen. Dat is zelfs met de huidige supercomputers onmogelijk.
Beide heren gebruiken daarom een serie trucs om het aantal combinaties dat doorgerekend moet worden, te beperken. Waarmee duidelijk is dat vele mogelijke Sudoku-oplossingen eigenlijk hetzelfde zijn. Draai een oplossing een kwart slag en de rijen en kolommen worden verwisseld en we hebben een nieuwe ‘oplossing’. Als we alle mogelijke trucs om vanuit één oplossing een andere te maken als niet uniek beschouwen, houden we slechts 5.472.730.538 echt unieke Sudoku-oplossingen over.
Sudoku maken
Een oplossing is nog niet de Sudoku die u in kranten of online aantreft. Omdat gokken niet de bedoeling is, willen we slechts één mogelijke oplossing. Die maken kan eveneens met de computer door uit een geldige oplossing een cijfer te verwijderen. De zo ontstane Sudoku is wel erg gemakkelijk op te lossen. Ofwel we gaan door met het verwijderen van cijfers totdat de computer via wederom brute kracht meerdere oplossingen vindt. In dat geval zetten we het laatst verwijderde cijfer terug.
De zo ontstane Sudoku heeft minimaal zeventien ingevulde vakjes. Met minder is er geen unieke oplossing zoals een Iers team van wiskundigen in 2012 ontdekten. Let op, simpel 64 getallen verwijderen betekent niet dat er een unieke oplossing is! De meeste Sudoku’s hebben gemiddeld zo’n 25 ingevulde getallen. Het aantal ingevulde vakjes is geen indicatie hoe eenvoudig het geheel is op te lossen. Vandaar dat de Sudoku’s in categorieën worden ingedeeld. Meestal iets als gemakkelijk, gemiddeld, moeilijk en duivels.
Notities
Elk spelletje dat gebaseerd is op wiskunde en niet op simpel gokken of goede reflexen, heeft mijn belangstelling. Al snel loste ik de gemakkelijke Sudoku’s in minder dan tien minuten op. En dankzij een tip van een deelnemer aan de wereldkampioenschappen Sudoku oplossen (https://www.youtube,com/@CrackingTheCryptic) kan ik momenteel een moeilijke variant meestal binnen een half uur voltooien.
Iedereen kent het simpel scannen van rijen en kolommen om zo locaties te vinden waar nog maar één cijfer mogelijk is. De tip is in elk van de negen vierkanten – dus niet in rijen of kolommen! – een notitie te maken als een cijfer nog maar in twee vakjes kan staan. In de serie screenshots ziet u een moeilijke Sudoku. Ik heb opvolgend voor de cijfers 1 tot en met 9 beredeneerd wat de reeds bekende locaties zeggen over de vierkanten waarin het onderzochte cijfer nog niet aanwezig is. Zodra ik voor een cijfer een notitie maak, kijk ik meteen of die nieuwe informatie gebruikt kan worden. In het onderste linker vak kan een 8 ingevuld worden. En die beperkt de locatie van de 8 in het linker middelste vak. Let op, ik kijk dus niet opnieuw naar cijfers die ik reeds heb afgewerkt.
Ook in het middelste vierkant van de bovenste rij is nog maar één vakje beschikbaar voor de 8. Deze heb ik in het klein genoteerd om de procedure van het scannen duidelijk te maken. Als u het zelf probeert, kunt u deze meteen invullen. Het resultaat van zes minuten werk zijn 50 nieuwe aanwijzingen (linker blok). Zes daarvan geven aan dat een cijfer direct ingevuld kan worden, iets wat iedereen automatisch doet als zij beginnen met het oplossen. De overige 44 notities zijn een bonus. De enige mogelijke locatie voor de 4 in het linker vak van de middelste rij dicteert via onze notities meteen ook de locatie voor de cijfers 1 en 6. Dit kunt u ook ontdekken in een tweede ronde van scannen. Maar door het meteen noteren, kunnen we nu niet zes, maar veertien (!) cijfers invullen (middelste blok). Dat maakt het oplossen een stuk sneller en laat deels de kracht van de tip zien.
 |
|
Oplossen moeilijke Sudoku dankzij notitie-tip |
Tweede scan
De werkelijk kracht zien we in het onderste rechter vak in de zevende rij. We hebben hier het paartje 1 en 3 ontdekt. In deze twee vakjes kan nu geen enkel ander cijfer meer. U gelooft mij niet? Probeer dan in gedachten maar eens een 2 in te vullen. Waarna u onmogelijk nog de 1 en 3 kunt plaatsen. Deze paartjes zijn niet alleen in vakjes, maar ook in rijen en kolommen dicterend. Dankzij de notities ontdekt u deze paartjes vanzelf.
Zoals gezegd lukte het mij zonder deze tip niet om de moeilijke Sudoku’s op te lossen. Het ontdekken van (verborgen) paartjes is zonder de notities zeer lastig. Het resultaat van de overgebleven notities uit de eerste scan combineren met alle nieuw ontdekte cijfers en het gevonden paartje, geeft het rechter blok. In deze stap zijn maar liefst elf cijfers in te vullen. De rest laat ik aan u over...
X-wing
Via een website (https://www.sudokuwiki.org/sudoku.htm) met een stap-voor-stap-oplosser, ontdekte ik dat de moeilijke Sudoku’s allemaal – mijn hypothese met ruim vijftig stuks – opgelost kunnen worden met de eerste zes strategieën. Twee daarvan gebruiken de paartjes die ik via de tip nu vrij gemakkelijk vindt.
De duivels, expert of andere kreten die gebruikt worden, vergen de andere 33 trucs. Deze worden allemaal uitgelegd, maar sommige snap ik niet. Laat staan dat ik het patroon herken. De zevende stap is een X-wing en die is mij duidelijk. Ik zou graag een paar honderd Sudoku’s hebben waarin alleen deze extra truc noodzakelijk is voor het oplossen. Helaas kan ik zo’n serie nergens op het internet vinden.
Zelf maken
Mogelijk dat het ergens in de krochten een serie X-wing Sudoku’s aanwezig is. Maar volgens mij is het ‘eenvoudiger’ om gewoon zelf zo’n serie te maken. Hoe? Hierboven heb ik al uitgelegd hoe een Sudoku gemaakt kan worden. Een zoekopdracht op Github in combinatie met Python geeft er op moment van schrijven negentig (https://github.com/topics/sudoku-generator?l=python). De meeste zijn nodeloos ingewikkeld of zijn niet te volgen. Maar uiteindelijk ontdekte ik een paar voorbeelden om mijn eigen versie te kunnen programmeren. Hoe? Dat is stof voor de volgende keer.
Met een automatische Sudoku-maker zal het waarschijnlijk een nachtje kosten om een serie van zeg honderdduizend stuks te genereren. De volgende stap is een programma dat de hierboven uitgelegde manier van oplossen gebruikt, waarschijnlijk in een aantal deelstappen om zo tot een eigen indeling van moeilijkheidsgraad te komen. Dit programma laat ik los op de gemaakte serie, waarna er hopelijk meer dan tienduizend nog geen oplossing hebben. Vervolgens programmeer ik de genoemde X-wing-truc om zo de gewenste set te krijgen.
OpenSudoku
De getoonde afbeeldingen zijn gemaakt met de Open Sudoku app (https://opensudoku.moire.org/). Voor mijn Bash-boek (https://www.hetlab.tk/het-lab/mijn-boeken) heb ik uitgezocht hoe ik aan deze app eigen sets kan toevoegen door gewoon een honderd stuks te downloaden via websites die Sudoku’s aanbieden. Ofwel, zodra ik een serie met een X-wing heb gevonden, kan ik weer maanden vooruit. Uiteraard zal ik alle code en de sets met u delen. Er zit ongeveer twee weken tussen het bij u in de bus vallen van deze aflevering en de volgende aflevering die ik moet inleveren. Wie snel is, kan mij dus mailen met vragen die ik dan mogelijk nog kan meenemen.
