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. Dus vormen van “slim” kijken zijn hier niet aan de orde!
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 (dus paren van de 1^e soort).
Het is hierbij niet strikt nodig om alle paren van de 1^e soort te vinden. Wel 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).
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.0

Beide mogelijkheden leiden slechts tot een gedeeltelijke invulling. Hier zijn geen 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.
Terug naar stap 3, voor een nieuwe poging.

 

3.1

Beide mogelijkheden geven slechts een gedeeltelijke invulling, maar hier zijn wel treffers bij.  Dan kunnen we dus in de betreffende velden nu ofwel een cijfer ofwel een getallenpaar invullen.
Met de aldus bijgewerkte sudoku gaan we nu opnieuw aan de slag, te beginnen met stap 1.

 

3.2

Een van beide mogelijkheden geeft een tegenspraak. Dan is de andere mogelijkheid dus juist.
We beschouwen hier eerst het geval dat deze juiste mogelijkheid nog maar een gedeeltelijke invulling geeft.
Met deze sudoku gaan we dan opnieuw aan de slag, te beginnen met stap 2.

 

3.3

Een van beide mogelijkheden geeft een tegenspraak. Dan is de andere kandidaat dus juist. We beschouwen nu het geval dat deze mogelijkheid zelfs tot een volledige invulling leidt.
Dan hebben we dus de oplossing van de sudoku en dit is ook de enige.
Klaar dus.

 

3.4.

Geen van beide mogelijkheden heeft tot een tegenspraak geleid.
Een van de twee mogelijkheden heeft zelfs een volledige invulling gegeven.
Dan is dit een oplossing.
We zoeken echter alle oplossingen. Dat betekent dat wij van de andere mogelijkheid moeten laten zien dat deze tot een tegenspraak leidt. Dat zal dus moeten gebeuren door deze mogelijkheid apart te onderzoeken.
We vullen dus deze mogelijkheid (onmogelijkheid moeten we eigenlijk zeggen) in en keren nu met deze sudoku terug naar stap 1 (voor zover nog niet uitgevoerd).
Met de nu bekende werkwijze kan de sudoku steeds verder ingevuld worden en uiteindelijk zal deze weg tot het gewenste einde (dat het een sudoku zonder oplossing is) moeten leiden.

 

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:

 

 

Veel media hebben hier destijds aandacht aan besteed. Met natuurlijk klakkeloos alle uitbundige commentaren overgenomen, want voor de meeste journalisten is moeilijke materie.
Dit bericht kwam ik in december 2019 tegen. Uiteraard heb ik direct op Google gekeken wat ik hier nog meer over kon vinden. Dat was niet veel meer dan allerlei herhalingen van dit bericht.
Als wiskundige en geïnteresseerde in het oplossen van extreem moeilijke sudoku’s was ik natuurlijk direct gegrepen door dit bericht. Ik heb in de afgelopen jaren heel wat vrije tijd besteed aan het oplossen van extreem moeilijke sudoku’s en uiteindelijk is het mij gelukt een oplossingsmethode te vinden (de aanbevolen methode). De hamvraag en een belangrijke toets voor mij waren dus: in hoeverre is mijn oplossingsmethode toereikend om ook deze sudoku te kraken?

Dus zeer gemotiveerd aan de slag gegaan.
Zoals te verwachten is zal opsplitsing hier soelaas moeten bieden.
Allereerst heb ik gekeken of er lege velden zijn die met enige moeite alsnog ingevuld kunnen worden. Die waren er niet, zoals te verwachten was.
Toen nagegaan of er lege velden zijn waar slechts twee cijfers mogelijk zijn. Ik kon maar één veld vinden waar dat het geval was, nl. het 7^e  veld in de 8^e rij. Hier kunnen alleen maar de cijfers 3 en 9 staan. Dit is de eerste plek waar zich maar twee mogelijkheden voordoen.
Vervolgens nagegaan of er rijen, kolommen of deelvierkanten zijn waarbij een bepaald cijfer nog slechts in twee velden kan staan. Dit blijkt vier keer voor te komen.

   - In de 2e kolom kan het cijfer 8 alleen op de 5e en de 6e positie staan (tweede plek).
   - In de 5e kolom kan het cijfer 5 alleen op de 1e en de 2e positie staan (derde plek).
   - In de 6e rij kan het cijfer 7 alleen op de 1e en de 3e positie staan (vierde plek).
   - In de 6e rij kan het cijfer 5 alleen op de 7e en de 9e positie staan (vijfde plek).

Dit zijn nog eens vier plekken waar zich ook twee mogelijkheden voordoen.
Samen betekent dit dat we vijf plekken kunnen aanwijzen waar slechts twee mogelijkheden zijn.
We komen dan uit op 2x2x2x2x2 = 32 mogelijke sudoku’s. We moeten dan 32 sudoku’s bestuderen. Dit zou wel te doen zijn, maar op grond van mijn ervaring met het oplossen van extreem moeilijke sudoku’s schatte ik toch in dat 3 extra cijfers misschien wel voldoende zou zijn. Daarom koos ik voor uitsplitsing in 2x2x2 = 8 mogelijke sudoku’s.
Voor de drie plekken waar zich de twee mogelijkheden voordoen, koos ik de plekken 1, 4 en 5. Nu maar eens kijken wat dit gaat opleveren.
En wat bleek? In minder dan een dag had ik alle 8 sudoku’s succesvol bestudeerd m.b.v. mijn methode.
Zoals te verwachten viel, bleken 7 van deze 8 sudoku’s geen oplossing te hebben en 1 had precies één oplossing.

De conclusie is dus: 1) mijn oplossingsmethode is effectief; 2) de sudoku van Arto Inkala is minder moeilijk dan allerlei berichten doen geloven.

Suggestie
Een goede oefening is om nu zelf eens te proberen deze 8 sudoku's zelf te kraken met de methode die ik beschreven heb.
Als u daarin geslaagd bent en u meldt mij dat per mail, dan vermeld ik uw naam hier op deze site.
E-mail: jderuiter08@gmail.com

 

Tot slot:
Een aantal jaren geleden verscheen het boek Los elke sudoku op (later in 3 delen) van W.H.A. Schilders met daarin de beschrijving van een methode waarmee elke sudoku, hoe lastig ook, via logische redenering opgelost zou kunnen worden.
Met flink wat publiciteit in de media. Dit boek heb ik als sterk geïnteresseerde natuurlijk volledig bestudeerd, omdat ik nieuwsgierig was of er betere alternatieven of bruikbare aanvullingen bij mijn aanpak waren.
Hier de pagina waarin dit onderzoek volledig beschreven is