Oplossen van zeer moeilijke sudoku’s

 

J. de Ruiter

1 oktober 2018

 

 

De techniek van stap 3 - de paralleluitwerking uitvoeren als er slechts 2 mogelijkheden zijn – leidt bij een groot aantal moeilijke sudoku’s al snel tot een oplossing.

Er is sprake van 2 mogelijkheden als er een veld is waarin nog slechts 2 getallen passen (geval 1) of als een bepaald cijfer nog slechts in 2 velden past (geval 2).

Vaak zijn er meerdere getallenparen aan te wijzen die zich lenen voor paralleluitwerking. Een gedeeltelijke verdere uitwerking van beide getallen leidt dan al snel tot dezelfde invulling van enige lege velden waarna de sudoku dan verder wel opgelost kan worden. Het komt echter ook voor dat geval 2 zich goed leent voor paralleluitwerking.

 

Gaandeweg ben ik steeds moeilijker sudoku’s gaan oplossen met deze techniek en dat gaat betekenen dat je stap 3 meerdere keren moet toepassen. In dat geval had je er beter aan gedaan om direct al vanaf de eerste keer de paralleluitwerking van beide opties allebei tot het eind uit te voeren. Immers, je hebt dan kans op meer treffers (voor beide kandidaten dezelfde invulling van totnutoe nog lege velden). En, mocht het gebeuren dat een van beide kandidaten tot een tegenspraak leidt, dan is de invulling van de andere kandidaat dus zelfs in zijn geheel juist.

Het kan ook voorkomen dat het uitwerken van een van de twee opties leidt tot volledige invulling van de sudoku. Dat is dan in ieder geval een oplossing van de sudoku. Men kan dan echter stellen dat deze oplossing door raden is gevonden en dat is taboe voor serieuze sudoku-oplossers. Ik stel de eis aan mijn oplossingsmethode dat deze leidt tot alle oplossingen van de sudoku. Dat betekent dat ik ook de andere optie nog moet onderzoeken. Als de opsteller van de sudoku gelijk heeft dat de sudoku precies één oplossing heeft, dan moet deze tweede uitwerking dus tot een tegenspraak leiden. Ik heb slechts een heel enkele keer meegemaakt dat een sudoku twee of zelfs nog meer oplossingen had.

 

Deze bijgestelde aanpak van stap 3 is als volgt op te schrijven:

 

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.

 

De gehele aanpak van het oplossen van de zeer moeilijke sudoku komt er dus zo uit te zien:

            stap 1 en 2

            stap 3: 1a, 1b, 2a of 2b

            stap 1 en 2

            stap 3: 1a, 1b, 2a of 2b

            :

            :

            : enz.

 

Als zich een keer 1a voordoet, dan is de oplossing bereikt.

Als zich een keer 2a voordoet, dan gaan we de oplossing ook wel bereiken.

In de praktijk blijkt dat de boven beschreven bijgestelde aanpak van stap 3 voor bijna alle zeer moeilijke sudoku’s tot een oplossing leidt.

 

Hieronder volgt een voorbeeld van bovenstaande aanpak.

De op te lossen sudoku is de volgende:



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


We gaan nu dus beginnen met stap 3.
Voor de positie van 3 in het 8e vak zijn 2 mogelijkheden. De rechter positie blijkt tot een tegenspraak te voeren. Dus in de linker positie moet de 3 staan. Na invulling hiervan en daarna weer uitvoering van stap 1 en stap 2 ontstaat nu de volgende sudoku:



We kiezen nu paar 5,9 in het 8e vak. Hiervan blijkt 5 tot een tegenspraak te voeren. Na invulling van 9 plus uitvoering van stap 1 en stap 2 krijgen we nu de volgende sudoku:




Vervolgens kiezen we paar 7,9 in het 1e vak. Hiervan blijkt de 9 tot een tegenspraak te leiden. We vullen dus de 7 in en voeren daarna weer stap 1 en stap 2 uit. Dit geeft de volgende sudoku:

 

Tenslotte kiezen we paar 2,7 in het 6e vak. De 2 blijkt al snel tot een tegenspraak te voeren. De 7 voert daarentegen snel tot een oplossing (de oplossing dus).

 

Samengevat ziet het oplossingspad er (met weglating van de stappen 1 en 2 die we tussentijds steeds opnieuw uitvoeren) dus zo uit:

1b, 1b, 1b, 1a

kortweg aangegeven als 3x1b, 1a.

  

Bovenstaande oplossingsmethode heb ik getest op de 87 sudoku’s in het tijdschrrift Sudoku maximal Nr. 5/2017 van Stefan Heine.

Stefan Heine is een autoriteit op het gebied van het samenstellen van zeer moeilijke sudoku’s. Hij wordt regelmatig ingeschakeld bij het opstellen van sudoku’s voor nationale en internationale kampioenschappen.

Deze test heeft geleid tot het volgende overzicht:

 

Oplossingspad

Aantal sudoku’s

 

 

Alleen stap 1 en stap 2

4

1a

35

1b,1a

18

2x1b, 1a

16

3x1b, 1a

4

6x1b, 1a

1

2a

7

1b, 2a

2

                                   Totaal: 87

 

Dit overzicht laat overduidelijk zien hoe nuttig het is om direct te beginnen met het onderzoeken van getallenparen op 1b.