Oplossers

De volgende Sudoku oplossers zijn beschikbaar:

Twee overlappende sudokus:

Wat kunt u ermee?

Alle oplossers werken ongeveer hetzelfde. Kies een actieve cel in de Sudoku met de muis. Door toetsen 1 tot en met 9 in te drukken, of met de muis te klikken op een cijfer onder de Sudoku, zet u de inhoud van de actieve cel.

De oplossers bepalen een oplossing die past bij de cellen die handmatig zijn ingevuld. Ook geven de oplossers aan of er 0, 1 of meer oplossingen zijn. Als u de oplossing voor een Sudoku zoekt, dan bent u pas klaar als er nog maar één oplossing is.

De oplossers geven een oplossing (indien er een oplossing bestaat), maar geven niet aan hoe u zelf deze oplossing zelf had kunnen bereiken. De oplosser is wel geschikt om snel te controleren of uw oplossing de juiste is, om snel een Sudoku op te lossen uit een krant o.i.d., of als u gewoon wilt weten wat de oplossing is.

Achter de schermen

Zoals gezegd, geeft de oplosser een oplossing, als deze bestaat. Hieronder is uitgelegd hoe dit (ongeveer) werkt.

Voor de oplosser bestaat de standaard Sudoku uit 81 waardes die gekozen moeten worden uit de cijfers 1 t/m 9. Daarnaast zijn er natuurlijk de regels waaraan een goede oplossing moet voldoen. De eerste regel is dat alle cijfers 1 t/m 9 moeten voorkomen in elke rij. Anders gezegd: op elke rij mogen de cijfers 1 t/m 9 niet meer dan 1 keer voorkomen. De oplosser splitst deze regel in een aantal eenvoudigere regels:

De waarde in rij 1, kolom 1 mag niet hetzelfde zijn als de waarde in rij 1, kolom 2.
De waarde in rij 1, kolom 1 mag niet hetzelfde zijn als de waarde in rij 1, kolom 3.
...
De waarde in rij 1, kolom 1 mag niet hetzelfde zijn als de waarde in rij 1, kolom 9.
De waarde in rij 1, kolom 2 mag niet hetzelfde zijn als de waarde in rij 1, kolom 3.
...
De waarde in rij 1, kolom 2 mag niet hetzelfde zijn als de waarde in rij 1, kolom 9.
...
De waarde in rij 1, kolom 8 mag niet hetzelfde zijn als de waarde in rij 1, kolom 9.

Voor een enkele rij zijn dit 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 regels. Voor alle rijen tesamen zijn dat 9 * 36 = 324 regels.

Op een zelfde manier wordt de regel vertaald die zegt dat alle cijfers 1 t/m 9 moeten voorkomen in elke kolom. Dit wordt vertaald in 324 eenvoudigere regels.

Dan blijft bij de standaard Sudoku alleen nog maar de regel over die zegt dat alle cijfers 1 t/m 9 moeten voorkomen in de 9 3x3 vierkantjes. Op dezelfde manier als bij de rijen en kolommen koen hier in principe 9 * 36 = 324 eenvoudige regels uit voort. Sommige van deze laatste regels hadden we echter al! De eerste eenvoudige regel van het vierkantje linksboven is: de waarde in rij 1, kolom 1 mag niet hetzelfde zijn als de waarde in rij 1, kolom 2. Dat was ook de eerste regel die we afgeleid hadden uit de regel over de waardes in de eerste rij. De regels die we voor de vierkantjes afleiden die gaan over waardes in dezelfde rij of kolom zijn allemaal duplicaten van regels die we al hadden. Het komt er op neer dat er 18 nieuwe regels per vierkant van 3x3 bijkomen. Samen is dat dus 9 * 18 = 162 regels.

We houden dus 324 (rijen) + 324 (kolommen) + 162 (vierkanten) = 810 regels over voor en standaard Sudoku. Elk van die regels zegt dat de waardes voor twee vakjes in de Sudoku niet hetzelfde mogen zijn.

Als de oplosser zijn werk moet doen, heeft u voor een aantal vakjes al een waarde gekozen. De oplosser vult deze waardes in zijn administratie in en komt dan tot de conclusie dat:

Sommige regels nu gecontroleerd kunnen worden, omdat de waardes voor beide vakjes (waarover de regel gaat) bekend zijn.
Sommige regels nog niet gecontroleerd kunnen worden, omdat er maar een waarde van de vakjes (waarover de regel gaat) bekend is (en één waarde nog niet).
De rest van de regels nog niet gecontroleerd kan worden, omdat er nog geen waardes van de vakjes (waarover de regel gaat) bekend zijn.

Het ligt voor de hand dat de oplosser eerst de regels controleert die al gecontroleerd kunnen worden. Als de waardes aan deze regels voldoen, gaat de oplosser verder.

Vervolgens wordt een volgorde gekozen voor het invullen van de lege vakjes. De oplosser varieert de inhoud van een leeg vakje van 1 t/m 9. Na het (tijdelijk) invullen van een vakje met een waarde wordt gekeken of de regels toestaan dat die waarde gekozen wordt. Zo gaat de oplosser alle mogelijke combinaties af, zo snel mogelijk doodlopende sporen afkappend.