Suggesties
Sudoku oplosser

sudoku.xlsb
    Sudoku

   1 Routine 1
   1.1 Werkwijze

   2 Routine 2
   2.1 Uniek getal in rij
   2.2 Uniek getal in kolom
   2.3 Uniek getal in vak
   2.4 Uniek getal in (binnen)vak
   2.5 Uniek getal in binnenvak
   2.6 Werkwijze

   3 Routine 3
   3.1 Rij in vak
   3.2 Kolom in vak
   3.3 Rij in binnenvak
   3.4 Kolom in binnenvak
   3.5 Werkwijze

   4 Programmeertechniek
   4.1 Recursie
   4.2 Celwaarden opslag
   4.3 Definitie Deelverzameling

Sudoku

Een Sudoku heeft 9 rijen en 9 kolommen.
Een Sudoku bevat ook 9 vakken van 3 rijen en 3 kolommen.
In alle rijen, kolommen en vakken mogen de cijfers 1 t/m 9 slechts éénmaal voorkomen.

De Sudoku voor deze oplosser is een zogenaamde 'hyper' Sudoku.
Deze bevat 4 extra 'binnenvakken' (gele achtergrond in de afbeelding), waarin de cijfers 1 t/m 9 ook slechts éénmaal mogen voorkomen.



Iedere Sudoku bevat als uitgangsgegeven een aantal cellen met 1 cijfer.
Het is de bedoeling de lege cellen zó te vullen dat aan alle criteria is voldaan.
Dat is het geval als de som van iedere rij én iedere kolom 45 bedraagt en de som van alle cijfers in de Sudoku 405 (9 * 45 ) is.

Iedere cel van een Sudoku maakt deel uit van:
- een rij
- een kolom
- een vak

Sommige cellen maken deel uit van
- een binnenvak (afbeelding gele achtergrond)

We beschouwen iedere rij, kolom, vak en binnenvak als deelverzameling van de Sudoku-matrix.

Iedere cel van de matrix maakt deel uit van 3 of 4 deelverzamelingen.
De invulling van een getal in een cel heeft daardoor meteen gevolgen voor alle deelverzamelingen (rij/kolom/vak/binnenvak) waarin de cel voorkomt.
De cellen in die deelverzamelingen kunnen dan nl. niet hetzelfde getal van die cel hebben.

Routines

1 Routine 1

De Sudoku bevat:
- een aantal begincijfers
- lege cellen

1.1 werkwijze

In alle lege cellen kunnen alle mogelijke cijfers voorkomen.
Daarom komt in alle lege cellen de reeks '123456789' te staan.
De oplossingstrategie bestaat uit het successievelijk verwijderen van díe getallen die op grond van de geformuleerde criteria uitgesloten worden.
- zet in alle lege cellen alle mogelijke waarden: 1 t/m 9
- filter op basis van de positie van een cel met 1 getal rij, kolom, vak en binnenvak waarin de cel voorkomt en verwijder daaruit het getal van die cel.
- als door de verwijdering een cel nog slechts 1 getal bevat herhaal dan de filtering op basis van deze cel

2 Routine 2

Iedere cel van een rij, kolom, vak, binnenvak bevat de cijfers die daarin mogelijk zijn.
Per rij, kolom, vak, binnenvak kan nagegaan worden of een bepaald cijfer slechts in 1 cel van de 9 voorkomt.
Als dit het geval is kan alleen díe cel als enige dat cijfer bevatten.
Vervang dan de inhoud van die cel door dat cijfer.
Verwijder daarna dat cijfer uit de cellen van alle deelverzamelingen waarvan de cel met het unieke getal deel uitmaakt.
Afhankelijk van de positie van de cel is 1 van de onderstaande 5 situaties het geval.

2.1. Uniek getal in rij

De cel in rij 1, kolom 5 bevat als enige in rij 1 het cijfer 9.
Dat betekent dat alle cellen in kolom 5 en in het vak van die cel geen cijfer 9 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een rode cirkel.


2.2 Uniek getal in kolom

De cel in rij 4, kolom 3 bevat als enige in kolom 3 het getal 9.
Dat betekent dat alle cellen in rij 4, het vak van die cel en het binnenvak waarvan de cel deel uitmaakt geen cijfer 9 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een blauwe cirkel.


2.3 Uniek getal in vak

De cel in rij 9, kolom 9 bevat als enige in het vak het getal 9.
Dat betekent dat alle cellen in rij 9 en kolom 9 geen cijfer 9 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een paarse cirkel.


2.4 Uniek getal in vak met binnenvak

De cel in rij 8, kolom 8 bevat als enige in het vak het getal 9.
Dat betekent dat alle cellen in rij 8, kolom 8 en het binnenvak waarvan cel(8,8) deel uitmaakt geen cijfer 9 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een groene cirkel.


2.5 Uniek getal in binnenvak

De cel in rij 4, kolom 4 bevat als enige in het binnenvak het getal 9.
Dat betekent dat alle cellen in rij 4, kolom 4 en het vak waarvan cel(4,4) deel uitmaakt geen cijfer 9 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een groene cirkel.


2.6 Werkwijze

Doorloop alle 31 deelverzamelingen en kontroleer de frekwentie waarin ieder cijfer daarin voorkomt.
- een lus van 31 omwentelingen:
9 rijen
9 kolommen
9 vakken
4 binnenvakken

- met een binnenlus van 9 omwentelingen: alle mogelijke cijfers

Als een cijfer in een deelverzameling slechts 1 keer voorkomt:
- zet dan dat cijfer in de cel in plaats van het groepje van mogelijke cijfers voor die cel.
- filter op basis van de positie van die cel rij, kolom, vak en binnenvak waarin de cel voorkomt en verwijder daaruit het getal van die cel.

3 Routine 3

De sudoku bevat 9 vakken en 4 binnenvakken.
Wanneer een bepaald cijfer alleen in één rij of één kolom van het vak voorkomt, betekent dat

- dat het cijfer niet kan voorkomen in dezelfde rij in een ander vak
- dat het cijfer niet kan voorkomen in dezelfde kolom in een ander vak

Daarom moet je alle 9 vakken en 4 binnenvakken doorlopen en per getal nagaan in welke rij/kolom ze zich bevinden.
Als 2 of max. 3 getallen zich in 1 rij of kolom bevinden, sluit dat het voorkomen van dat getal in dezelfde rij/kolom in een ander vak uit.
Hierna de illustratie van alle 4 voorkomende situaties.

3.1 Rij in vak

De cellen in rij 1, kolom 4 en kolom 6 bevatten als enige in het vak het getal 2.
Dat betekent dat alle overige cellen in rij 1 geen cijfer 2 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een blauwe cirkel.


3.2 Kolom in vak

De cellen in kolom 1, rij 1 en rij 2 bevatten als enige in het vak het getal 1.
Dat betekent dat alle overige cellen in kolom 1 geen cijfer 2 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een rode cirkel.


3.3 Rij in binnenvak

De cellen in rij 7, kolom 7 en kolom 8 bevatten als enige in het binnenvak het getal 4.
Dat betekent dat alle overige cellen in rij 7 geen cijfer 4 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een paarse cirkel.



In het geval er 2 cellen in 1 rij van het binnenvak vallen zijn er 2 situaties mogelijk:

1. beide cellen bevinden zich in een ander vak
De exercitie blijft beperkt tot de rij van beide cellen



2. beide cellen bevinden zich in hetzelfde vak
Ook uit de cellen van dat vak moet het getal 3 verwijderd worden

3.4 Kolom in binnenvak

De cellen in kolom 3, rij 2, rij 3 en rij 4 bevatten als enige in het binnenvak het getal 3.
Dat betekent dat alle overige cellen in kolom 3 geen cijfer 3 kunnen bevatten.
In de afbeelding zijn dat alle cellen met een groene cirkel.



In het geval er 2 cellen in 1 kolom van het binnenvak vallen zijn er 2 situaties mogelijk:

1. beide cellen bevinden zich in een ander vak
Dan blijft de exercitie beperkt tot de kolom van beide cellen



2. beide cellen bevinden zich in hetzelfde vak
Dan moet ook uit de cellen in dat vak het getal 3 verwijderd worden



3.5 Werkwijze

- doorloop alle 9 vakken en 4 binnenvakken
- bepaal per getal in welke rij/kolom het getal voorkomt
- als een getal slechts in 1 rij of 1 kolom voorkomt:
- verwijder dan dat getal uit alle rijen, kolommen en vakken waarin biede (of de drie) cellen met dat nummer voorkomen

- als daardoor een cel slechts 1 cijfer bevat:
- filter op basis van de positie van die cel rij, kolom, vak en binnenvak waarin de cel voorkomt en verwijder daaruit het getal van die cel.

4. Programmeertechniek

4.1 Recursie

De toekenning van één cijfer aan een cel heeft meteen gevolgen voor alle andere cellen in dezelfde rij/kolom/vak/binnenvak.
Het aantal mogelijke cijfers in die cellen wordt daardoor beperkt.
Nadat in al deze cellen het cijfer van de toegekende cel is verwijderd dient opnieuw beoordeeld te worden of aan zo'n cel ook een unieke waarde toegekend kan worden.
De analyse van de Sudoku begint na iedere wijziging dus weer van voren af aan.
Dat is de kern van recursie.
In het voorbeeldbestand is sprake van geneste recursie:
- in een lus van 0 tot 30 worden alle deelverzamelingen geanalyseerd
- in een binnenlus van 1 tot 9 vindt dat voor alle getallen van 1 tot 9 per deelverzameling plaats
- als het resultaat nog niet de oplossing is, vindt de analyse per deelverzameling opnieuw plaats.
- als dat leidt tot verwijdering van getallen wordt de verwijdermacro aangeroepen
- als binnen de verwijdermacro sprake is van unieke waarden in een cel, wordt de verwijdermacro vanuit de verwijdermacro zelf aangeroepen

4.2 Celwaarden opslag

Een sudoku bevat 81 cellen.
De (mogelijke) waarden van iedere cel kunnen opgeslagen worden in bijv. een 1-dimensionele array, een 2-dimensionele array, dictionary of collection.
Het voorbeeldbestand maakt gebruik van een 1-dimensionele Array.

4.3 Definitie deelverzamelingen

Uit welke cellen een rij, kolom, vak of binnenvak bestaat is vastgelegd in een Array.
In het voorbeeldbestand staat die in 1 onzichtbaar benoemd gebied '[sb]'.
Het benoemde gebied bestaat uit een 1-dimensionele Array met 31 elementen.
Ieder element bevat een tekenreeks met de rij/kolom 'naam' van iedere cel in de deelverzameling.
De cel'namen' zijn gescheiden door een underscore.

Bijv. voor rij 1
"11_12_13_14_15_16_17_18_19"

De macro om dat benoemde gebied te vullen staat in de codemodule van 'ThisWorkbook' en heet 'M_names'

De elementen 0 – 8 bevatten de namen van de cellen in rij 1 t/m 9.
De elementen 9 – 17 de namen van de cellen in kolom 1 t/m 9.
De elementen 18 – 26 de namen van de cellen in de vakken 1 t/m 9.
De elementen 27 – 30 de namen van de cellen in de binnenvakken 1 t/m 4.

Routine 1 en routine 2 filteren voor een cel alle deelverzamelingen waarin die cel voorkomt.
Routine 3 filtert voor de gevonden cellen de deelverzamelingen waarin beide cellen (of alle drie cellen) gezamenlijk voorkomen.