Oplossen van moeilijke sudoku’s

 Snelle en eenvoudige methode voor het oplossen van moeilijke sudoku’s.

 J. de Ruiter
28 april 2015

 

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). Als hier wel meer op ingegaan wordt, dan wordt het al snel een ingewikkeld verhaal. Ook is niet altijd duidelijk welk bereik de uitgelegde oplossingsmethode heeft. Is deze ook met succes toepasbaar op zeer lastige sudoku’s?

In dit artikeltje zal ik u een oplossingsmethode aanreiken die

-        moeilijke sudoku’s kraakt,

-        tevens aantoont dat de gevonden oplossing de enige is,

-        slechts uit 3 betrekkelijk eenvoudige stappen bestaat die een of meer keren uitgevoerd moeten worden,

-        geen aparte hulpvelletjes vraagt, maar rechtstreeks op de afgedrukte sudoku uitgevoerd kan worden.

Het principe KISS (keep it short stupid) volgend demonstreren we deze oplossingsmethode meteen aan de hand van het volgende voorbeeld: onderstaande sudoku met 28 gegeven cijfers.


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! Er is niks op tegen om dit wel te doen, maar het is niet nodig.
Resultaat:
hoewel we in de meeste gevallen dan direct een aantal extra cijfers vinden, is dat hier niet het geval. Stap 1 levert dus bij deze sudoku niets op. Dit duidt erop dat deze sudoku minder eenvoudig is.

Stap 2

We gaan nu op zoek naar vakjes waar nog slechts 2 cijfers mogelijk zijn.
Het is hierbij niet strikt nodig om alle vakjes met 2 cijfers te vinden. Ook hier geldt weer: het mag wel, maar het hoeft niet. In het algemeen kunnen we ons beperken tot het onderzoeken van die rijen, kolommen en deelvierkanten waar al minstens 4 cijfers in staan.
Resultaat:



De oogst is dus 15 paren zoals we boven zien.

Stap 3
De laatste stap is de meest verrassende! We voeren deze stap eerst uit om te laten zien wat deze inhoudt en wat de effecten zijn.
We kiezen een van de 15 paren en wel het paar 24 linksboven in de sudoku. Vervolgens gaan we de twee kandidaten 2 en 4 beide een eind uitwerken. De uitwerking voor cijfer 2 staat linksonder in de vakjes en de uitwerking voor cijfer 4 rechtsboven.
Dit levert de volgende invulling op:



Als bovenstaand eindresultaat voor u nog wat te snel gaat, omdat u hiermee nog onvoldoende ervaring heeft, dan volgt hier een gedetailleerde toelichting.

Print om te beginnen de tweede fig. even uit.
Ga nu eerst invullen op basis van kandidaat 2 van paar 2,4 linksboven.
Dit levert achtereenvolgens de volgende invulling op.
1e rij: 8 op positie 7, daarna 4 op positie 3
2e kolom: 1 op positie 3
2e kolom: 2 op positie 7
3e kolom: 1 op positie 6
6e rij: 4 op positie 6
4e kolom: 4 op positie 8
1e kolom: 4 op positie 9
1e kolom: 9 op positie 5
Er zijn nog wel meer cijfers in te vullen, maar dat is al niet meer nodig.

Print vervolgens opnieuw de tweede fig uit, om verwarring met de vorige invulling te voorkomen.
Ga nu invullen op basis van kandidaat 4 van paar 2,4.
Dit levert het volgende op:
1e kolom: 9 op positie 5
1e rij: 8 op positie 3, daarna 2 op positie 7
8e kolom: 2 op positie 7
9e rij: 2 op positie 9
3e rij: 2 op positie 2
Deelvierkant linksboven: 1, 3, 6 en 9 moeten nog geplaatst worden; 3, 6 en 9 kunnen niet in het middelste veld, dus daar moet de 1 staan!
3e kolom: 1 op positie 6
Ook hier zijn nog best meer cijfers in te vullen, maar dat is niet meer nodig.

Je kunt nu zien dat van het paar 2,4 beide kandidaten het cijfer 9 op positie 5 van de 1e kolom, het cijfer 1 op positie 6 van de 3e kolom en het paar 2,4 op positie 9 van de 1e kolom opleveren. Deze drie invullingen zijn dus correct voor de betreffende velden.
We hadden nog wel even door kunnen gaan met deze paralleluitwerking, maar met de gevonden drie resultaten is de sudoku nu verder op de gewone elementaire wijze (lees: met alleen stap 1 en 2) af te maken. Dus daarom ben ik hier gestopt.
De lezer kan nu zelf wel inzien dat de gevonden oplossing ook de enige is.

Een interessante oefening is om bovenstaande paralleluitwerking nu zelf toch nog verder door te zetten en te zien wat er dan gebeurt. Dit is zeer leerzaam.

Voorgaande laat duidelijk zien dat stap 3, de paralleluitwerking van een geschikt gekozen paar, kan leiden tot meer juiste cijfers en/of paren. U zult merken dat u met de techniek van stap 3 al behoorlijk moeilijke sudoku’s kunt oplossen.

Omdat de essentie van stap 3 gelegen is in de paralleluitwerking van de twee enige mogelijkheden, kan men deze ook toepassen als er sprake is van een rij, kolom of deelvierkant waarbij er voor een bepaald cijfer nog slechts 2 velden beschikbaar zijn.

Als men de paralleluitwerking inzet bij het oplossen van een sudoku, dan kunnen zich allerlei situaties voordoen. We noemen de belangrijkste.

  •  Een van de twee cijfers van het gekozen paar leidt wel tot enige verdere invulling, maar het andere cijfer niet. Dan komen we dus niet verder en zullen we een ander paar moeten kiezen.
  •  Beide cijfers van het gekozen paar leiden wel tot enige verdere invulling, maar niet tot invulling van hetzelfde veld. Ook dan kan men beter overwegen om een ander paar te kiezen.
  •  Beide cijfers van het gekozen paar leiden tot enige verdere invulling en voor een of meer van de nog lege velden zelfs tot dezelfde invulling (een cijfer of een paar). Dan moet deze invulling dus juist zijn.
  •  Een van de twee cijfers van het gekozen paar leidt tot een tegenspraak. Dan is het andere cijfer dus het juiste.


Eventuele nieuw gevonden cijfers en/of paren hoeven echter nog niet toereikend te zijn om de sudoku nu volledig op te kunnen lossen. Bij zeer lastige sudoku's kan het zijn dat stap 3 meerdere keren uitgevoerd moet worden.
Let wel, elke keer als het uitvoeren van stap 3 tot de invulling van nieuwe velden leidt, zal men ook steeds weer even stap 1 en 2 moeten uitvoeren.


Als men ervaring wil opdoen met deze verrassende techniek, dan raad ik de site www.extremesudoku.info aan. Hier worden elke dag 5 nieuwe sudoku’s geplaatst, in 5 moeilijkheidsgraden.


In Nederlandse kiosken ben ik nooit sudokuboekjes tegengekomen die het toepassen van stap 3 vereisen.


Als men wel eens in Duitsland komt, dan is het volgende sudokuboekje een echte aanrader:
Sudoku, Eberhard Krüger, Bassermann Rätsel.
200 sudoku’s, in 4 moeilijkheidsgraden, waarvan de moeilijkste (die echte Herausforderung) stap 3 (de stap van paralleluitwerking) vereisen, meestal 1 keer en soms 2 keer.
Ligt in Duitsland in bijna elk boekenstalletje.