Oplossen van (extreem) moeilijke sudoku’s
J. de Ruiter
1 oktober 2018
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?
In dit artikel zal ik u een oplossingsmethode aanreiken die:
moeilijke sudoku’s kraakt, ook extreem moeilijke,
tevens aantoont dat de gevonden oplossing de enige is,
slechts uit enkele betrekkelijk eenvoudige stappen bestaat die dan wel een of meer keren uitgevoerd moeten worden.
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.
Het is hierbij niet strikt nodig om alle velden met 2 cijfers te vinden. Wel zoveel als maar lukt.
Stap 3
Kies een van de velden waar nog slechts 2 cijfers 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 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 mogelijheden 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.
Maar er zijn extreem moeilijke sudoku’s waar deze aanpak nog 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 valt er bij stap 3 niets meer te kiezen 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 opsplitsing van de sudoku in 2 of zelfs nog meer mogelijke sudoku’s.
Stap 4
Opsplitsing van de sudoku in 2 of zelfs meer sudoku’s.
Kies een veld waar nog slechts 2 cijfers mogelijk zijn of kies een rij, kolom of deelvierkant waarbij een bepaald cijfer nog slechts in 2 velden mogelijk is. Dan ontstaan 2 sudoku’s en deze gaan we apart onderzoeken m.b.v. stap 1 t/m 3.
Deze aanpak zal na kortere of langere tijd leiden tot de conclusie dat de ene mogelijkheid onjuist en de andere juist is. De juiste zal ook oplossing van de sudoku geven.
Bij extreem moeilijke sudoku’s kan het voorkomen dat men nog verder moet gaan en 2 mogelijkheden met nog 2 andere mogelijkheden moet combineren. Dan ontstaan 2 x 2 = 4 sudoku’s die men elk afzonderlijk moet onderzoeken. Echter, ze hebben elk dan wel 2 gegeven cijfers meer dan de ongesplitste sudoku, dus de moeilijkheidsgraad is dan afgenomen.