Oplossen van extreem moeilijke sudoku’s

 

J. de Ruiter

1 oktober 2018

 

Zoals we hebben gezien is voor zeer moeilijke sudoku’s de volgende aanpak toereikend:

 

Start

Kies een veld waar nog slechts 2 getallen mogelijk zijn, 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.

Werk beide kandidaten uit (op basis van stap 1 en stap 2) net zover tot je niet verder kunt.

Dan doen zich de volgende mogelijkheden voor.

 

1a.

Een van beide kandidaten geeft een tegenspraak. Dan is de andere kandidaat dus juist.

Deze juiste kandidaat leidt zelfs tot een volledige invulling.

Dan hebben we dus de oplossing van de sudoku.

 

1b.

Een van beide kandidaten geeft een tegenspraak. Dan is de andere kandidaat dus juist.

Deze juiste kandidaat geeft slechts een gedeeltelijke invulling.

Met de nieuwe sudoku dan opnieuw naar Start en nu een ander paar uitwerken.

 

2a.

Geen van beide kandidaten heeft tot nu toe een tegenspraak laten zien.

Een van de twee kandidaten heeft een volledige invulling gegeven.

Dat is dan een oplossing.

We zoeken echter alle oplossingen. Dat betekent dat wij van de andere kandidaat moeten laten zien dat deze tot een tegenspraak leidt. Dat zal dus moeten gebeuren door bij deze kandidaat een extra getallenpaar te kiezen en te laten zien dat beide kandidaten van dit extra getallenpaar tot een tegenspraak leiden.

Als geen van beide tot een tegenspraak leidt, dan een ander paar kiezen.

Als slechts een van beide tot een tegenspraak leidt, dan de andere apart onderzoeken door daar opnieuw een getallenpaar bij te kiezen.

In de praktijk zul je merken dat deze weg snel tot het gewenste einde gaat leiden.

 

2b.

Geen van beide kandidaten heeft tot nu toe een tegenspraak laten zien.

Beide kandidaten geven slechts een gedeeltelijke invulling.

Als hier treffers bij zijn, dan deze nu invullen in de betreffende lege velden en met de bijgewerkte sudoku weer terug naar Start om nu een ander paar uit te werken.

Als er geen treffers bij zijn, dan uiteraard ook opnieuw naar Start voor een ander paar.

 

Maar er zijn extreem moeilijke sudoku’s waar deze aanpak nog net niet toereikend is.

We hebben het dan over de meest moeilijke sudoku’s die nog maar ternauwernood door logisch redeneren opgelost kunnen worden. Dit zijn sudoku’s die op het niveau van nationale en internationale kampioenschappen liggen.

De hiervoor geschetste aanpak levert bij dit soort sudoku’s misschien wel een aantal extra cijfers en getallenparen op, maar op een gegeven moment zijn alle paren onderzocht en is de oplossing nog niet bereikt. Dan wordt het tijd om nog een nieuw middel in te strijd te gooien en dat is de zgn. dubbele aanpak.

 

3.

Kies een geschikt getallenpaar en ga beide kandidaten apart onderzoeken door voor beide kandidaten apart naar Start te gaan.

Dat houdt dus in: bij elke kandidaat een geschikt getallenpaar kiezen en dan de eerder geschetste aanpak nu voor beide kandidaten apart uitvoeren.

Deze aanpak zal na kortere of langere tijd leiden tot de conclusie dat de ene kandidaat onjuist is en de andere onjuist en zal ook oplossing van de sudoku geven.

In extreme gevallen kan het voorkomen dat men binnen het aparte onderzoek nog een apart onderzoek moet uitvoeren.

 

Om deze dubbele aanpak te verduidelijken volgt hieronder een uitgewerkt voorbeeld.

De op te lossen sudoku is de volgende:


 

Na uitvoering van stap 1 en stap 2 ontstaat de volgende sudoku:



Kijk nu naar de positie van 7 in de 4e rij. De 5e positie blijkt tot een tegenspraak te voeren. Dus op de 4e positie kan nu 7 worden ingevuld. Na stap 1 en stap 2 krijgen we dan de volgende sudoku:


 


Het nu verkregen resultaat lijkt veelbelovend om door te gaan met de aanpak. Maar het blijkt niet mee te vallen om een paar te vinden dat verdere resultaten oplevert.

We gaan nu maar eens proberen van een geschikt paar beide kandidaten apart te onderzoeken. We kiezen daarvoor het paar 5,6 in het 6e vak.

Eerst  gaan we kandidaat 5 uitwerken. Dat betekent de 5 invullen en dan uiteraard stap 1 en stap 2 uitvoeren. Dit levert de volgende sudoku op:



Kies nu paar 1,7 in het 1e vak. Zowel 1 als 7 voeren beide vrij snel tot een tegenspraak. Dus de conclusie moet zijn dat de onderzochte kandidaat 5 onjuist is.

Dus paar 5,6 in het 6e vak kan vervangen worden door 6. Met stap 1 en stap 2 geeft dit dan de volgende sudoku:



Kies nu paar 8,9 in het 4e vak. De 8 voert tot een tegenspraak, dus de 9 is juist. Met stap 1 en stap 2 krijgen we dan:



Tenslotte kiezen we paar 1,4 in het 8e vak. 4 leidt tot een tegenspraak en 1 geeft een oplossing, dus de oplossing.

 

Samengevat ziet het oplossingspad er, met weglating van stap 1 en stap 2, dus als volgt uit:

1b, 3.

 

Het is zeker niet zo dat deze aanpak van zeer moeilijke en extreem moeilijke sudoku’s tot een eenduidig bepaald oplossingspad leidt. Meerdere oplossingpaden zijn mogelijk, afhankelijk van de getallenparen paren die men steeds kiest.

 

De zojuist geschetste oplossingstechniek heb ik getest op het tijdschrift SUDOKU extrem bis hardcore Nr. 6 van de auteur Stefan Heine. De daarin staande 100 sudoku’s worden door hem aangeduid als 100 zeldzame parels, verdeeld in 3 categorieën. In zijn woorden:

Stufe 10 ist gerade noch auf logischem Wege lösbar. Bei Stufe 11 bedarf es kompliziertester Methoden. Bei der unfassbar schweren Stufe 12 scheitern selbst die modernsten Löseprogramme daran einen logischen Weg zu finden.

 

In onderstaand overzicht heb ik van alle 100 sudoku’s aangegeven welke de gevonden oplossingspaden zijn geweest.

 

Oplossingspad

Stufe 10

Stufe 11

Stufe 12

 

 

 

 

Alleen stap 1 en stap 2

2

 

 

1a

26

1

 

1b, 1a

7

6

1

2x1b, 1a

 

10

1

3x1b, 1a

 

4

2

4x1b, 1a

 

4

2

5x1b, 1a

 

2

1

6x1b, 1a

 

 

1

Pad bevat 2a

1

2

6

Pad bevat 2b

 

1

 

Pad bevat 3

 

1

19

 

 

 

 

 

36 sudoku’s

31 sudoku’s

33 sudoku’s

 

Dit overzicht laat opnieuw zien dat het oplossingspad vaak de component 1b bevat.

Maar ook dat voor het oplossen van extreem moeilijke sudoku’s vaak component 3 (de dubbele aanpak) ingezet moet worden.

 

Hieronder nog een voorbeeld van een extreem moeilijke sudoku.

Gevonden op www.nemokennislink.nl:  Zie Marc Seijlhouwer, 21 oktober 2012.

Deze heb ik, zij het met de nodige inspanning, kunnen oplossen met mijn oplossingsmethode voor extreem moeilijke sudoku's.



Aanvulling d.d. mei 2019

 

In 2019 kreeg ik een nummer van Denksport cadeau, nl. Sudoku 12–13* cum laude. Dit tijdschrift dateert al vanaf het jaar 2014, maar ik was nog nooit een exemplaar

tegengekomen. Het betrof nummer 40 van februari / maart 2019.

Benieuwd als ik was naar de moeilijkheidsgraad van de hierin opgenomen sudoku’s ben ik meteen aan het oplossen geslagen. En ja hoor, tot mijn verrassing bleken deze sudoku’s inderdaad extreem moeilijk te zijn, iets wat ik nog nooit in Nederlandse tijdschriften en kranten was tegengekomen!

Hier volgt een overzicht van de met mijn oplossingsmethode gevonden oplossingspaden van alle 88 sudoku’s uit dit tijdschrift.

 

Oplossingspad

Moeilijheidsgraad 12

Moeilijkheidsgraad 13

 

 

 

Alleen stap 1 en stap 2

2

1

1a

24

2

1b, 1a

7

7

2x1b, 1a

3

6

3x1b, 1a

 

4

4x1b, 1a

1

9

5x1b, 1a

 

 

6x1b, 1a

 

2

Pad beavt 2a

7

 

Pad bevat 2b

 

 

Pad bevat 3

1

12

 

 

 

 

45 sudoku’s

43 sudoku’s

 

Dit overzicht laat duidelijk zien we hier te maken hebben met sudoku’s met vergelijkbare moeilijkheidsgraad als in SUDOKU extrem bis hardcore van Stefan Heine.