donderdag, 3 oktober 2024
Vraag Rijk
Online Schrijfhulp

Blog

Een sudoku is een probleem dat vraagt om systematisch, logisch denken. Door deductie en eliminatie komt de denker tot de oplossing van het probleem dat de sudoku stelt: het invullen van de ontbrekende cijfers in een raamwerk. Voor wie niet weet wat een sudoku inhoudt, geef ik kort de opzet. Een sudoku bestaat uit een vierkant raster van negen maal negen hokjes; in elk hokje hoort een cijfer. Deze eenentachtig hokjes zijn geordend in drie maal drie negentallen. Alle negen negentallen zijn vierkant en omvatten elk drie maal drie hokjes. De oplosser staat voor het probleem om de cijfers van een tot en met negen zo in de hokjes te plaatsen dat er geen dubbele cijfers voorkomen, noch in enige rij van negen hokjes, noch in enige kolom van negen hokjes, noch in enig negental. Een sudoku geeft altijd een aantal aanwijzingen: sommige hokjes bevatten al een cijfer. Hoe meer cijfers de sudoku geeft, hoe gemakkelijker het probleem, want op grond van de gegeven cijfers moet de denker de overige cijfers plaatsen. De plek van de gegeven cijfers bepaalt waar de overige cijfers komen. Er is altijd maar één oplossing mogelijk.

Ik doe mijn sodoku in drie stappen. Eerst loop ik alle gegeven (en later zoals u zult zien, ook de door mij ingevulde) cijfers af volgens de gerichte schijnwerpermethode. Bij elk cijfer ga ik naar links en rechts, en naar boven en onder, op zoek naar een hokje in een ander negental waarin het betreffende cijfer móet staan, omdat alle acht andere hokjes in dat negental voor dit cijfer verboden terrein zijn. Het verboden terrein voor het betreffende cijfer in een negental wordt dus bepaald door hetzelfde cijfer in andere negentallen. Zij beschijnen het verboden gebied in het betreffende negental vanuit hun eigen negental, ofwel horizontaal over een rij, ofwel verticaal over een kolom. Mijn onderzoek begint meestal bij het eerste cijfer in de leesvolgorde. Het cijfer bepaalt een deel van het verboden terrein in vier andere negentallen. Die negentallen onderzoek ik achtereenvolgens op aanvullend verboden gebied door per rij en per kolom die dit negental doorkruist te zoeken naar hetzelfde cijfer dat op het onderzochte negental schijnt en zo het verboden gebied voor het betreffende cijfer vergroot. Als de schijnwerpers precies één hokje níet belichten, dan moet het betreffende cijfer daar wel staan; invullen dus. Als er meer hokjes kandidaat zijn, moet een volgende ronde soelaas bieden en ga ik naar het volgende negental. (De informatie dat er meerdere hokjes kandidaat zijn voor een bepaald cijfer kan ik bij stap twee gebruiken; daar kom ik zo direct op.) Als ik alle vier negentallen heb onderzocht die door het cijfer beschenen worden, doe ik hetzelfde onderzoek voor het volgende gegeven (of door mij ingevulde) cijfer, tot ik alle cijfers in de sudoku heb gehad. Als ik tijdens deze eerste stap cijfers kan invullen, herhaal ik de gerichte schijnwerpermethode voor alle gegeven en ingevulde cijfers, tot ik geen cijfers meer kan invullen.

Over naar stap twee, de globale schijnwerpermethode. Hierbij onderzoek ik alle negentallen in de sudoku achtereenvolgens. Dit keer zoek ik naar horizontale en verticale delen van een negental waarvan ik zeker weet dat een bepaald cijfer hier, en niet elders, in het negental móet voorkomen, ongeacht de precieze locatie in het betreffende deel. Door de gerichte schijnwerpermethode toe te passen op horizontaal naast elkaar liggende hokjes en op verticaal boven elkaar liggende hokjes binnen een negental, kan ik tweetallen of drietallen van hokjes lokaliseren waarvan ik zeker weet dat alleen zij binnen het negental een bepaald cijfer kunnen bevatten. Ik weet dan zeker dat het cijfer ofwel in het eerste ofwel in het tweede ofwel, als dat van toepassing is, in het derde hokje moet voorkomen, en niet elders in het negental. Horizontaal of verticaal werken deze speciale groepjes van hokjes als schijnwerper, waarmee ik de gerichte schijnwerpermethode van de eerste stap opnieuw kan toepassen. Het doet er voor het effect van een schijnwerper immers niet toe dat we zijn precieze locatie niet kennen, als we maar weten in welke richting hij schijnt. Ik herhaal de globale schijnwerpermethode tot ik geen cijfers meer kan invullen.

Dan is het tijd voor stap drie, de boekhoudmethode – als de sudoku niet al opgelost is, wat bij gemakkelijke sudoku’s heel goed mogelijk is. Eerst ga ik op zoek naar duo’s. Voor elk cijfer ga ik op zoek naar de negentallen waarin dat cijfer maar op twee plaatsen voorkomt. Die noteer ik in het klein, links in beide betreffende hokjes. Wanneer nu twee van deze kandidaten op één horizontale of verticale lijn voorkomen, sluiten zij hetzelfde cijfer op dezelfde lijn uit. Wanneer een lid van een duo uitvalt, staat het andere lid op de juiste plaats. Invullen dus. Daarmee vervallen ook de eventuele andere leden van een duo in het betreffende hokje, waardoor de eer aan de andere leden van de betreffende duo's vervalt. Weer invullen dus. Dat kan behoorlijk opruimen.

Daarna onderzoek ik alle lege hokjes op kandidaten: welke cijfers zijn in elk hokje mogelijk? Natuurlijk maak ik daarbij gebruik van de gevonden duo’s, de gerichte schijnwerpermethode en van de globale schijnwerpermethode. Dit resulteert in een tussentijdse boekhouding per hokje. Elk hokje kent nu een aantal kandidaten. Die noteer ik in het klein, rechts in het betreffende hokje. Deze kandidaten bekijk ik vervolgens in samenhang per rij, per kolom en per negental. Dat doe ik op drie manieren. Eerst kijk ik of er in een rij, een kolom of een negental een unieke kandidaat voorkomt. Als dat zo is, weet ik zeker dat deze in het betreffende hokje hoort; invullen dus. Vanzelfsprekend verwijder ik de zojuist ingevulde kandidaat uit de boekhoudingen waarin hij is opgenomen: per rij, per kolom en per negental. Omdat dit vaak weer nieuwe informatie oplevert, herhaal ik dit onderzoek tot ik geen nieuwe cijfers meer kan invullen.

Dan ga ik per rij, per kolom en per negental op zoek naar vijf soorten patronen in de boekhouding. Ik noem dit patroonherkenning. (We zijn nog steeds bezig met stap drie, de boekhoudmethode.) Het eerste patroon dat ik zoek, bestaat uit gelijke paren, ab en ab. Wanneer in een rij, in een kolom of in een negental twee hokjes voorkomen die elk twee dezelfde kandidaten hebben, verwijder ik deze kandidaten uit de overige boekhouding van respectievelijk de betreffende rij wanneer het patroon in zijn geheel in die rij voorkomt, uit de betreffende kolom wanneer het patroon in zijn geheel in die kolom voorkomt, en uit het betreffende negental wanneer het patroon in zijn geheel in dat negental voorkomt. Beide kandidaten moeten immers in beide hokjes voorkomen - de ene hier, de andere daar of andersom - en kunnen daarom elders niet voorkomen. Als er in de boekhouding van een hokje één kandidaat overblijft, vul ik deze in en verwijder ik deze uit de boekhoudingen waarin hij is opgenomen. Omdat deze stap vaak nieuwe informatie oplevert, herhaal ik dit onderzoek voor alle rijen, kolommen en negentallen tot ik geen kandidaten meer kan wegstrepen. Het tweede patroon bestaat uit drie gelijke drietallen verdeeld over drie hokjes, abc, abc en abc. Deze behandel ik op dezelfde wijze als de twee gelijke paren, tot ik geen kandidaten meer kan wegstrepen. Voor het derde, vierde en vijfde patroon geldt hetzelfde. Het derde patroon bestaat uit twee gelijke drietallen en een tweetal dat deel uitmaakt van een van beide gelijke drietallen, abc, abc en ab. Het vierde patroon bestaat uit een drietal en twee verschillende tweetallen; beide tweetallen maken deel uit van het drietal, elk op een andere manier, abc, ab en bc. Het vijfde patroon bestaat uit drie verschillende tweetallen die elk van een drietal af te leiden zijn, ab, bc en ac. Ik herhaal de boekhoudmethode tot ik geen kandidaten meer kan wegstrepen. (Overigens, dat zult u ook ervaren als u meerdere sudoku's maakt, deze patroonherkenning pas ik vaak eerder tijdens de boekhoudmethode toe, door al tijdens het inventariseren van de kandidaten rekening te houden met de informatie die de patronen van de gegeven en gevonden cijfers tot dat moment oplevert).

Ik zet de patronen van stap drie nog even op een rij en vul ze aan met enkele veelkomende patronen voor viertallen:
1: ab en ab (sluit ab elders uit)
2: abc, abc en abc (sluit abc elders uit)
3: abc, abc en ab (sluit abc elders uit)
4: abc, ab en bc (sluit abc elders uit)
5: ab, bc en ac (sluit abc elders uit)

De patronen voor viertallen:
6: abcd, bcd, bc en ab (sluit abcd elders uit)
7: abcd, cd, bc en ab (sluit abcd elders uit)
8: acd, cd, bc en ab (sluit abcd elders uit)
9: ad, cd, bc en ab (sluit abcd elders uit)

Bij de meeste sudoku’s ben ik er in deze drie stappen. De allermoeilijkste sudoku’s vragen echter om een vierde, aanvullende strategie: de hypothese. Dat zijn de sudoku’s die ook na herhaalde toepassing van alle stappen nog meerdere kandidaten toelaten voor meerdere hokjes. De voorliggende situatie leg ik in dat geval vast, zodat ik ernaar kan terugkeren als de hypothese tot een tegenspraak leidt. Vervolgens zoek ik naar een kansrijke kandidaat voor een hokje – meestal is dat er een van een gelijk paar – en werk ik het vervolg daarvan uit volgens de drie beproefde stappen: de gerichte schijnwerper, de globale schijnwerper en de boekhouding met patroonherkenning. Soms heb ik geluk en leidt dit niet tot twee conflicterende kandidaten in een rij, in een kolom of in een negental voordat de sudoku gereed is. Als ik die conflicterende kandidaten echter wel tegenkom, keer ik terug naar de vastgelegde situatie en probeer ik de volgende kandidaat. De hypothese kan daarna in zeldzame gevallen op vergelijkbare wijze vastlopen en vragen om herhaling, tot de sudoku opgelost is. Eigenlijk is het heel gemakkelijk als je goed oplet waar je in welke stap zit - al wil ik niet zeggen dat de stappen precies in de beschreven volgorde doorlopen moeten worden, zeker niet in een later stadium wanneer u al veel cijfers heeft kunnen invullen - maar het is wel heel ontspannend en een goede oefening voor het scherpen van de geest.