Herziene versie
J. de Ruiter
Datum: 18 september 2024
Vorige versie: 1 oktober 2018

1. Mogelijke aanpakken

Sudoku’s vormen voor talrijke mensen een denksport die veel ontspanning oplevert en in een aantal gevallen ook veel inspanning. Talrijke sites en talrijke puzzleboekjes bieden grote aantallen sudoku’s aan voor de liefhebber. Vaak staat de moeilijkheidsgraad er ook bij vermeld. De door de verschillende auteurs gebruikte indelingen zijn echter vaak verschillend en de hierbij gehanteerde criteria zijn in de meeste gevallen onnavolgbaar. Sommigen onderscheiden slechts 4 moeilijkheidsgraden, anderen zelfs wel 13.
Veel sites besteden slechts marginaal aandacht aan de oplossingsmethode (of methoden). Ook is niet altijd duidelijk welk bereik de gebruikte oplossingsmethode heeft. Is deze ook met succes toepasbaar op zeer lastige sudoku’s?
Voor de goede orde: een oplossingsmethode moet voldoen aan de eis dat een gevonden cijfer de enige juiste mogelijkheid voor het betreffende veld is.
De meeste sudoku’s die men tegenkomt in kranten, tijdschriften en op internet zijn eigenlijk altijd wel zonder veel moeite oplosbaar. Echt lastige sudoku’s zijn echter minder eenvoudig te vinden. Dan moet je bepaalde tijdschriften nemen of bepaalde websites bekijken.
Welke oplossingsmethoden zijn er nu voor moeilijke tot extreem moeilijke sudoku’s?

1.
Vaak wordt patroonherkenning genoemd als mogelijke aanpak. Bedoeld wordt dan het volgende. In de op te lossen sudoku worden natuurlijk eerst de gemakkelijk te vinden cijfers ingevuld. Daarna worden in de dan nog lege velden alle mogelijke kandidaat-cijfers ingevuld, netjes in een klein 9x9 blokje om het overzichtelijk te houden. In het geheel van deze blokjes zijn dan soms patronen te herkennen die laten zien dat sommige cijfers in de 9x9 blokjes geschrapt kunnen worden. Bekende patronen zijn X-wing, XY-Wing, Jelly-Fish, Sword-Fish enz. De hoop is dan dat op die manier alleen de juiste cijfers nog overblijven. 
Men moet dan dus patronen herkennen. Men weet dan echter nooit zeker of alle aanwezige patronen gezien zijn! Nog erger: wordt dan de volledige oplossing ook bereikt?
Ik heb zelf nog nooit een voorbeeld gezien van een moeilijke sudoku die met patroonherkenning volledig werd opgelost.
Stefan Heine, een autoriteit op het gebied van extreem moeilijke sudoku’s, raadt die methode dan ook af.

2.
Hoe moeilijk de sudoku ook is, er is altijd maar een eindig aantal mogeljjke invullingen voor de lege velden. Dit betekent dat een computerprogramma de oplossing kan vinden. Vele enthousiastelingen zijn dan ook van meet af aan aan de slag gegaan om zo’n computergramma te maken. Op internet wemelt het inmiddels van goede en snelle programma’s.

3,
Als 1) en 2) dan afvallen, welke mogelijkheden zijn er dan om een methode te bedenken die enkel en alleen uit logische stappen bestaat?
Het zal u misschien verbazen, maar het is zelfs eenvoudig in te zien dat zo’n methode er is.
Hoe is dat in te zien?
De praktijk laat zien dat voor zelfs de meest moeilijke sudoku’s het altijd zo is dat er een aantal paren van slechts twee mogelijkheden is.
Zo’n paar kan zijn dat in een bepaald leeg veld slechts 2 cijfers mogelijk zijn.
Zo’n paar kan echter ook inhouden dat in een bepaalde rij, kolom of deelvierkant een bepaald cijfer slechts in 2 velden kan staan. Elke sudoku heeft 9 rijen, 9 kolommen en 9 deelvierkanten. Dus zo’n paar zal nog al eens voorkomen.
Een voorbeeld: de beroemde en uitermate moeilijk op te lossen sudoku van Arto Inkala uit 2012. Deze heeft 1 paar van de eerste soort en in elk geval 4 paren van de tweede soort. Dus in totaal zij er wel 5 paren (zie elders op deze pag).
Het bleek voldoende te zijn 3 van deze paren te kiezen en dan de sudoku van Arto Inkala op te splitsen in 2x2x2 = 8 mogelijke sudoku’s.
Dan heb je dus 8 sudoku’s die elk 3 cijfers extra hebben. Dat betekent dat deze gemakkelijker te bestuderen zijn. En wat bleek: 7 van deze sudoku’s waren tegenstrijdig en precies 1 sudoku was oplosbaar!
Deze opsplitsingstechniek is altijd mogelijk. Hoe verder de opsplitsing, des te meer velden ingevuld, dus dit resulteert wel in meer sudoku’s maar die zijn dan wel gemakkelijker.
Conclusie: elke sudoku is logisch oplosbaar.
Elders op deze pag. ziet u ook nog een voorbeeld van een sudoku die moeilijker is dan de sudoku van Arto Inkala. Ook hier is opsplitsing de voor de hand liggende techniek.

In de praktijk zullen sudoku-oplossers bijna nooit zulke moeilijke sudoku’s tegenkomen waarbij opsplitsing in meerdere sudoku’s onvermijdelijk is. Ik heb grote aantallen extreem moeilijke sudoku’s opgelost door gewoon meerdere nummers van het tijdschrift Denksport Sudoku 14-15* Summit volledig door te werken. Dat is in alle gevallen gelukt zonder onoverkomelijke problemen.
De aanpak die ik daarbij ontwikkeld heb kunt u hieronder zien.

2. Aanbevolen methode voor het oplossen van zelfs extreem moeilijke sudoku’s

J. de Ruiter

1 oktober 2018

 

Stap 1

We gaan eerst na, zonder verdere ingewikkeldheden te plegen, welke cijfers we nog meer kunnen invullen, uitgaande van de eis dat in elke rij, elke kolom en elk van de 9 deelvierkanten steeds alle cijfers 1 t/m 9 staan.
In de meeste gevallen zullen we dan een of meer extra cijfers vinden.

Stap 2

We gaan nu op zoek naar velden waar nog slechts 2 cijfers mogelijk zijn (getallenpaar ofwel paar van de 1^e soort).
Zoveel als maar lukt.

 

Stap 3

Kies een van deze paren, bij voorkeur een getallenpaar waarvan al direct te zien is dat minstens een van de twee getallen aardig wat extra invullingen geeft.
In sommige gevallen is een beter alternatief: kies een rij, kolom of deelvierkant waarbij een bepaald cijfer nog slechts in 2 velden mogelijk is (paar van de 2^e soort).
Advies: vanaf nu met potlood en gum werken.
Werk beide mogelijkheden uit (op basis van stap 1 en stap 2) net zover tot je niet verder kunt.
Dan doet zich een van de volgende uitkomsten voor.

 

3.1

Een van beide mogelijkheden geeft een tegenspraak. Dan is de andere mogelijkheid dus juist. Dus meteen invullen en dan weer terug naar stap 1 en stap 2. Meestal hebben we dan nog maar een gedeeltelijke invulling. Dan beginnen we weer met stap 3 om opnieuw een getallenpaar te kiezen. Enz.
Als de invulling van de juiste mogelijkheid zelfs meteen tot een volledige invulling leidt (gebeurt bijna nooit), dan hebben we dus de oplossing van de sudoku. Klaar dus.

3.2

Beide mogelijkheden geven slechts een gedeeltelijke invulling, maar hier zijn wel treffers bij. We spreken van een treffer als beide invullingen een voorheen nog leeg veld gaan vullen, met ofwel hetzelfde cijfer ofwel twee verschillende cijfers.
Deze treffers zijn dus juist en kunnen dus definitief ingevuld worden.
Met de aldus bijgewerkte sudoku gaan we nu opnieuw aan de slag, te beginnen met stap 1.

 

3.3

Beide mogelijkheden leiden slechts tot een gedeeltelijke invulling, maar zonder treffers. 
Terug naar stap 3, voor een nieuwe poging.

 

Met deze werkwijze kan de sudoku steeds verder ingevuld worden en uiteindelijk blijkt deze weg tot de oplossing te leiden.
Dit heb ik uitgetest door meerdere afleveringen van het tijdschrift Denksport: SUDOKU 14 - 15* Summit volledig door te werken. In totaal gaat het dan om 352 sudoku's. Per sudoku heb ik ca. 2 tot wel 5 of zelfs meer paren nodig gehad om de oplossing te bereiken. Ik tel dan alleen de paren die een nieuw cijfer hebben opgeleverd. De oplossingstijd kan soms wel een paar uur duren.

 

3. Uitgewerkte voorbeelden
Uitgewerkte voorbeelden.pdf

4. De sudoku van Arto Inkala (2012) opgelost

J. de Ruiter
December 2019

 

In 2012 kwam de Finse wiskundige Arto Inkala met het spectaculaire bericht dat hij de moeilijkste sudoku ter wereld zou hebben ontworpen.
Deze puzzle kon volgens hem alleen door de scherpste geesten opgelost worden.
Dit is de sudoku: