Beknopte cursus sudoku-oplossen.

Wat is een Sudoku?

Een sudoku bestaat uit een tabel van 9 bij 9 velden. Een deel van die velden bevat een cijfer. Het is de bedoeling dat ook de lege velden met cijfers worden gevuld en wel op een zodanige manier dat iedere horizontale rij, elk van de cijfers 1 t/m 9 bevat, terwijl tegelijkertijd datzelfde geldt voor iedere vertikale kolom, èn voor elk van de 9 dikomlijnde vierkante blokken. Een tabel die aan deze voorwaarden voldoet is op zichzelf al een bijzonderheid, maar toch bestaan er heel veel van dit soort vierkanten en zij vormen de basis van deze boeiende puzzels. Zie diagram 1.

Juist doordat de rangschikking van de cijfers aan zoveel regels voldoet, is het mogelijk om door middel van logisch nadenken en ijverig zoeken, de ontbrekende getallen te vinden. De makers van deze puzzels zorgen er voor dat dit ook echt mogelijk is en dat er slechts één oplossing is.

Oplossingsstrategie

Ieder vakje in een sudoku-diagram maakt deel uit van 3 verschillende 'clusters': een rij, een kolom en een blok. Als een bepaald vakje bijvoorbeeld het getal 5 bevat, dan kunnen we voor alle overige velden van de daarmee corresponderende clusters (in totaal 20 vakjes) de 5 als mogelijk getal ('optie') wegstrepen. Diagram 2 illustreert wat met 'corresponderende clusters' wordt bedoeld. Als we op deze wijze zoveel mogelijk opties uitsluiten, dan is de kans groot dat we, vroeg of laat, voor bepaalde velden met zekerheid kunnen concluderen welk getal ze moeten bevatten. We hebben dan een oplossing gevonden en deze leidt weer tot het wegstrepen van opties, waardoor weer nieuwe getallen gevonden kunnen worden, zodat weer opties geschrapt kunnen worden etc. etc. Zo ontstaat a.h.w. een kettingreactie van oplossingen. Alleen als we voor 100% zeker weten dat een getal op een bepaalde plaats hoort, hebben we een oplossing. Er zijn in eerste instantie twee verschillende situaties waarin dat het geval is:
Type A: Als voor een veld nog maar één optie is overgebleven. (Alle getallen, op één na, zijn verboden)
Type B: Als binnen een bepaald cluster (rij, kolom of blok) een zeker getal nog maar op één veld geplaatst kan worden. (Alle andere velden zijn voor dat getal verboden)

Als we een leeg veld zien waarbij in de 3 corresponderende clusters al vrij veel getallen zijn ingevuld, dan is het interessant om na te gaan welke getallen er op die lege plaats mogelijk zijn. Er zijn nu drie mogelijkheden:
1. Er zijn meerdere getallen mogelijk.
2. Er is geen enkel getal mogelijk.
3. Er is nog precies één getal mogelijk.
In het eerste geval leidt dit onderzoek niet tot resultaten. In het tweede geval kunnen we concluderen dat er ergens een fout is gemaakt en in het derde geval hebben we een oplossing van type A gevonden. Een voorbeeld van dit geval zien we in diagram 2. In het blauwe vakje past enkel maar een 4, want ieder ander cijfer is al aanwezig in een de van de corresponderende clusters.

Een ander geval dat interessant is om te onderzoeken, is een cluster dat al redelijk compleet is. We bekijken nu waar de nog ontbrekende cijfers eventueel zouden kunnen staan. Als een ontbrekend cijfer op slechts één veld plaatsbaar is, dan hebben we een oplossing van type B gevonden. Dit geval zien we in diagram 3: Er ontbreken in de tweede kolom nog 4 cijfers: de 2, de 3, de 5 en de 9. Met betrekking tot de 3, de 5 en de 9 kunnen we niets met zekerheid zeggen, omdat voor deze cijfers meerdere velden zijn toegestaan. Voor de 2 daarentegen zijn drie van de vier nog lege vakjes verboden, zodat er dus maar één mogelijkheid overblijft: het donkere oranje vakje.

Het oplossen verloopt dus d.m.v. het wegstrepen van opties, net zolang totdat er voor één bepaald veld slechts één mogelijk getal overblijft, òf dat er voor één bepaald getal slechts één mogelijk veld overblijft. Let wel: dit zijn in essentie twee verschillende zaken.

Iets moeilijker

Als hiermee alles gezegd zou zijn, dan is het oplossen van een sudoku eigenlijk maar simpel afstreep- en zoekwerk. Gelukkig is dat niet het geval. Door slim te redeneren, kunnen vaak veel meer opties geschrapt worden dan puur op grond van de ingevulde getallen mogelijk zou zijn. Dit leidt dan direct of indirect tot het vinden van nieuwe oplossingen. Niet zelden kan, als de preciese plaats van een getal niet te bepalen is, dit wel ongeveer gedaan worden. bijvoorbeeld doordat je met zekerheid kan concluderen dat het betreffende getal binnen een groep van bijv. 2 of 3 velden moet vallen. Dit zien we in diagram 4. Als we dit diagram met het vorige vergelijken, zien we dat slechts één van de lege velden in de oranje kolom, direct door een 2 'beschenen' wordt. Zowel blok 6 als 8 bevatten nog geen 2, maar we weten al wel dat deze in beide blokken op de onderste rij zal moeten komen. Daarmee hebben we genoeg informatie om, in de oranje kolom, de 2 te localiseren.

Slim wegstrepen

In het voorbeeld hierboven zagen we dat er vaak meer opties kunnen worden geschrapt, dan alleen op grond van de ingevulde getallen. Als "slim wegstrepen" geactiveerd is, maakt de computer gebruik van deze technieken. Daardoor worden er per stap veel meer oplossingen gevonden, zodat de hele sudoku veel vlugger volledig is opgelost. Het toepassen van deze geavanceerde technieken is juist een van de leukste aspecten van de sudoku. Het principe hierachter komt er op neer dat we van één of meerdere getallen, niet de exacte plaats weten. maar toch wel een kleine groep velden kunnen aanwijzen, waarbinnen die getallen zich moeten bevinden. Die cijfers zijn dan aan die groep velden "gebonden" en dat sluit uit dat ze elders binnen dat cluster voorkomen en/of het sluit uit dat deze velden door andere cijfers bezet kunnen worden. Er zijn verschillende oorzaken waardoor cijfers aan velden gebonden kunnen zijn.

Geval 1: Stel dat twee velden binnen een cluster, ieder, enkel en alleen, precies dezelfde twee opties hebben; dan weet je 100% zeker dat deze cijfers op die velden moeten komen en dus nergens anders binnen dat kluster. (kale groep). Het paarse veld in diagram 5 heeft de opties 2,5,7 en 9. Wegens de twee 'kale' groepen (blauw) vervallen de opties 2,7 en 9 zodat alleen de 5 overblijft.

Geval 2: Stel dat 2 cijfers binnen een cluster slechts op 2 velden plaatsbaar zijn, dan weet je 100% zeker dat er op die velden geen andere cijfers mogelijk zijn (verborgen groep). In diagram 6 ontstaat, dankzij de groen omcirkelde 4 en 5, een verborgen groep (paars). Hierdoor blijft er in deze kolom nog maar één plaats over voor de 1 (rode veld).

NB Verborgen en kale groepen kunnen ook uit meer dan 2 cijfers en velden bestaan.

Geval 3: Stel dat één, twee of drie getallen binnen een blok slechts op één rij of één kolom zijn toegestaan, dan ligt dat daarmee ook voor de overlappende rij c.q. kolom vast en weet je 100% zeker dat deze dus niet elders in dat cluster voor zullen komen (overlappings zones). Dit zagen we in diagram 4.
Op grond van dit soort overwegingen, kunnen er doorgaans heel wat opties gestreept worden en dat draagt direct of indirect bij aan de oplossing. Op de oplospagina zien we, vlak boven de optietabel, een rij knoppen waarmee gezocht kan worden naar deze patronen. De opties die op grond daarvan worden geschrapt, worden rood weergegeven. Verborgen groepen etc. zijn vaak moeilijk te vinden. Om ze toch duidelijk zichtbaar te maken, toont de computer slechts één type tegelijk.

Gokken

Het kan gebeuren dat het spoor dood loopt, doordat er echt geen enkele directe conclusie meer te trekken valt. In dat geval zit er niets anders op dan maar iets te proberen. Vanzelfsprekend doen we dan een gok met een zo groot mogelijke kans op succes. Eén optie uit twee heeft meer slagingskans dan bijvoorbeeld één uit vier. Als deze aanname vroeg of laat tot tegenstrijdigheden leidt, weet je dat dit cijfer verkeerd was en je dus de andere optie moet hebben. Dit is een van de minder leuke aspecten van een sudoku, want het vinden van een oplossing op deze manier schenkt lang niet zo veel voldoening als het vinden van een oplossing door scherpzinnig redeneren. Gelukkig zijn de meeste sudoku's die we dagelijks in krant en tijdschrift vinden, zonder gokken op te lossen. Ook als het lijkt dat je echt niet meer verder kan komen, zijn er vaak nog heel wat verborgen oplossingen. Wie met het oplosprogramma aan de slag gaat, zal zich daarover verbazen.

Tot besluit

Het oplossen van een sudoku is gewoon een hele klus. Er bestaat geen trucje waarmee je het even gauw doet. Wie het bovenstaande goed begrepen heeft, die heeft een redelijk arsenaal aan oplosmethodes ter beschikking. Daardoor gaat het oplossen niet alleen veel vlotter, maar is het ook veel interessanter en leuker.