Oplosmethodes

Deze oplosmethodes worden uitgevoerd in volgorde van complexiteit - als een het oplosrooster verandert dan gaat de oplosser terug naar oplosmethode A en begint opnieuw.

Elke keer dat een bepaalde oplosmethode wordt gebruikt, telt het punten voor een 'moeilijkheidsscore' up om een algemene moeilijkheidsgraad te geven voor de sudoku.  

Oplosmethode A

Kijk in een rij in het oplosrooster of er nummers zijn die maar één keer voorkomen in de rij. Als dat zo is, dan moet de cel waarin het nummer voorkomt de oplossing zijn. Deze regel wordt herhaald voor kolommen en blokken.

Moeilijkheidsscore=4

Oplosmethode B

Kijk in een rij in het oplosrooster of er nummer zijn die alleen voorkomen in een specifiek blok. Dat nummer moet dan in die rij staan, dus verwijder dat nummer uit de andere cellen in het blok. Herhaal voor kolommen.

Hetzelfde maar dan omgekeerd - kijk in een blok in het oplosrooster of er nummers zijn die alleen voorkomen in een specifieke rij of kolom. Dat nummer moet in dat blok staan, dus verwijder het nummer uit cellen in de rij of kolom buiten het blok.

Moeilijkheidsscore=8

Oplosmethode C

Kijk in een rij in het oplosrooster of er een nummer is dat maar twee keer voorkomt in de rij. Als de cellen waarin ze voorkomen precies matchen met een ander nummer dat voldoet aan dit criterium, dan moeten deze cellen dat nummerpaar bevatten - dus verwijder de andere opties in deze cellen. Opnieuw wordt dit herhaald voor kolommen en blokken. Deze methode wordt ook herhaald voor drie- en meertallen.

Moeilijkheidsscore=16

Oplosmethode D UPDATED!

Herziene methode geschreven door Alan Chambers - bedankt Al!

Kijk in een rij in het oplosrooster of er een groep is van N cellen die maar N mogelijke nummers bevatten. Als zo'n 'ketting' bestaat, dan moeten deze cellen deze nummers bevatten, dus kunnen de nummers verwijderd worden uit andere cellen in de rij.

Dit wordt herhaald voor kolommen en blokken.

Bijvoorbeeld, in de rij

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        6789      37        458       2         34568     489       1

Kolommen 1,2 en 4 bevatten de nummers 3,7, en 8.

Dus kunnen we [78] verwijderen uit kolom 3, [8] uit kolom 5 en [38] uit kolom 7 en [8] uit kolom 8.

Daarna ziet de rij er zo uit:

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        69        37        45        2         456       49        1

Voor een praktisch voorbeeld, kijk op deze pagina.

Moeilijkheidsscore=32, 48 of 64 voor waarden N=2,3 en 4 respectievelijk.

Oplosmethode E - nog niet geïmplementeerd

We hebben een suggestie voor een nieuwe Oplosmethode om één van onze Challenge Sudokus op te lossen.. maar we hebben nog geen code. Om de regel te zien of als je houdt van een codeeruitdaging, klik hier.

Oplosmethode F UPDATED!

Deze oplosmethode wordt progressief steeds ingewikkelder, zoals we zullen zien.

Maar op z'n simpelst: Kijk in een rij of een nummer maar in twee cellen voorkomt. Als er andere rijen zijn die aan deze regel voldoen met hetzelfde nummer, en de kolommen van de cel matchen in beide gevallen, dan moet dat nummer in twee van deze vier cellen voorkomen. Je kunt daardoor dit nummer verwijderen uit alle andere plaatsen in de matchende kolommen. Herhaal voor kolommen.

Deze methode is bij de guru's bekend als X-Wing.

Er is een soortgelijk iets voor blokken:

Als, voor elke rij, de twee cellen in hetzelfde blokken staan dan kun je dit nummer verwijderen uit de andere cellen in de matchend blokken. Herhaal voor kolommen ten opzichte van rijen en kolommen ten opzichte van blokken. Daarna, herhaal het voor blokken - als twee blokken of rijen of kolommen delen en één enkel nummer komt voor in maar twee cellen in elk blok, in matchende rijen of kolommen, dan kan dit nummer verwijderd worden uit deze rijen of kolommen. (behoorlijk ingewikkeld, hè? ik weet niet zeker of ik het zelf begrijp.)

Dit wordt zelfs nog gecompliceerder met een drie-cellen variant die Swordfish heet. Craig Oakley heeft code geschreven om de Swordfish op te lossen (bedankt Craig), en we hebben deze methode F2 genoemd.

Tenslotte zijn er nog hogere celaantallen voor dit probleem. (vier cellen etc.) Al Chambers heeft is opnieuw naar voren gestapt en heeft code geschreven voor een algemene versie van Oplosmethode F die gaat tot N-cellen complexiteit. Hersenkrakend. Hij heeft de versie waar N=4 Jellyfish genoemd, wat ik vermoed is omdat het je slap maakt in je knieën. Helemaal mee eens, Al.

Moeilijkheidsscore=64

Wat is 'Raden-en-controleren toestaan'?

Dit implementeert een methode die 'Ariadne's Thread' genoemd wordt. Als alle oplosmethodes uitgeput zijn, raadt het het antwoord voor een cel en probeert dan een antwoord te vinden door de oplosmethodes opnieuw toe te passen. Als dit resulteert in een ongeldige Sudoku, raadt het een andere nummer. Als er nog steed opties zijn, gaat het door hiermee totdat het een antwoord vindt (of ongeldig wordt). Er wordt over gediscussieerd of dit 'logica' is, dus hebben we het een optie gemaakt d.m.v. een aankruisvakje.

Geef eerste oplossing

Als je de raden-en-controleren techniek gebruikt, is het altijd mogelijk dat er meer dan een oplosssing is voor een Sudoku. Het uitschakelen van het 'Geef eerste oplossing'-vakje zal alle mogelijkheden controleren om te bevestigen dat je oplossing uniek is.

Erkenningen

Dank naar Sernin Van de Krol voor het vertalen van de site in het Nederlands!