Sudoku

Op deze pagina staat een hulpmiddel voor het oplossen van een sudoku. De pagina bestaat uit twee delen. In het bovenste deel staat de puzzelschema zelf, waarin je de cijfers kan invullen. In het onderste deel staat het hulpschema. In het hulpschema verschijnt voor elke positie het aantal mogelijke cijfers. Als je met de muis boven de positie komt, worden deze mogelijke cijfers getoond.

Bij het puzzelschema staan vier knoppen. De "nieuwe opgave" knop genereert ter plekke een nieuwe sudoku (min of meer willekeurig, maar wel met precies één oplossing), maar je kan natuurlijk ook gewoon een bestaande sudoku invoeren en oplossen. De "alleen hints" knop verwerkt de ingevoerde cijfers en laat in het hulpschema vervolgens de mogelijkheden zien. De "volgende stap" knop vult ook gelijk die mogelijke cijfers in het puzzelschema in. (Handig voor als je er echt niet meer uitkomt, maar deze knop is natuurlijk vooral bedoeld voor de structurele valsspelers... hihi.) Met "alles wissen" wordt het puzzelschema weer geleegd.

Puzzelschema

Hulpschema

Uitleg

Elk cijfer van 1 t/m 9 moet steeds 1x voorkomen in elke rij, elke kolom en elk vak van 3 bij 3 cellen (hier in het wit en lichtgrijs weergegeven). Bij een sudoku opgave staan er reeds een aantal cijfers ingevuld, zodanig dat er maar één goede oplossing mogelijk is.

Aanpak

De volgende stap is het bepalen van de potentiële plaats van een nieuw cijfer. In sommige gevallen kan dat nieuwe cijfer maar op één plek in een vak worden geplaatst. Dat cijfers moet dan worden ingevuld op die ene plaats, waarna het hele proces van wegstrepen weer opnieuw begint.

Vaak komt het echter voor dat een cijfer op meerdere plaatsen in een vak kan worden gezet. Als nu deze potentiële plaatsen alleen in één bepaalde kolom of rij staan, weten we ook dat dat cijfer in die kolom of rij in andere vakken in ieder geval niet meer geplaatst kan worden. Daarmee kunnen alweer extra mogelijkheden worden weggestreept.

Heel soms komt het ook voor dat een bepaalde combinatie van mogelijke cijfers binnen een rij, kolom of sectie meerdere keren voorkomt. Als dat precies even vaak is als het aantal cijfers van de combinatie kunnen deze cijfers in de rest van deze rij, kolom of sectie in ieder geval niet meer voorkomen. In dat geval kan het soms ook noodzakelijk zijn om een van die cijfers te proberen en dan te bepalen of de puzzel opgelost kan worden. Als dat niet het geval is, moet dat cijfer uit de mogelijkheden worden geschrapt. Dit maakt de sudoku een stuk moeilijker (of eigenlijk bewerkelijker).

Programma

Het programma volgt voor het bepalen van de cijfers gewoon deze regels van de sudoku puzzel. Bij een leeg schema kunnen alle cijfers dus nog overal worden geplaatst. Bij het invullen van elk nieuw cijfer, wordt dat betreffende cijfer uit de mogelijkheden van de rest van de rij, de rest van de kolom en de rest van het vak weggestreept. Daarna controleert het programma de potentiële plaatsen van de overige cijfers, en streept daarbij eventueel nog meer mogelijkheden weg. (Zoals bij de situatie van de unieke rij of kolom, of de unieke combinaties.) Met de overgebleven potentiële plaatsen wordt het hulpschema opgebouwd. De probeer-stap wordt daarbij (nog) niet uitgevoerd.

Voor de nieuwsgierige programmeurs zal ik binnenkort de php-code erbij zetten.

Emile Eichenberger, december 2005.