Suggesties
Sudoku oplosser

sudoku.xlsb
    Sudoku

   1. Routines

   1.1 Routine 1

   1.2 Routine 2

   1.3 Routine 3

   1.4 Routine 4

   2. Programmeertechniek

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', waarin de cijfers 1 t/m 9 ook slechts éénmaal mogen voorkomen.



Iedere Sudoku bevat een aantal met 1 cijfer gevulde cellen als uitgangsgegeven.
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 geel gearceerd)
- een kadervak (zie afbeelding)



De invulling van een cel heeft meteen gevolgen voor alle deelverzamelingen (rij/kolom/vak) waarin de cel voorkomt.
De cellen in die deelverzamelingen kunnen dan nl. niet de waarde van de ingevulde cel hebben.

1 Routines

1.1 Routine 1

De Sudoku bevat:
- een aantal begincijfers
- lege cellen

werkwijze

- zet in alle lege cellen alle mogelijke waarden 1 t/m 9
- noteer van alle begincijfers drie gegevens:
- het nummer van de rij
- het nummer van de kolom
- het cijfer in de cel

1.2 Routine 2

Alle cellen maken deel uit van 4 deelverzamelingen.
- een rij
- een kolom
- een vak
- een binnenvak of kadervak

werkwijze

- verwijder de waarde van ieder uitgangscijfer uit alle 4 deelverzamelingen waarin de cel voorkomt.

vervolgens
- controleer of een cel slechts 1 cijfer bevat
- als een cel slechts 1 cijfer bevat, noteer dan van die cel drie gegevens:
- het nummer van de rij
- het nummer van de kolom
- het cijfer in de cel

programmeeraanpak

Er zijn 2 manieren om een cijfer te verwijderen uit een overeenkomstige rij/kolom/vak/tussenvak

1. Doorloop alle 36 rijen/kolommen/vakken/binnenvakken/kadervakken
- verwijder de celwaarde uit de met de cel overeenkomende rij/kolom/vak/binnenvak/kadervak
2. Doorloop de rij/kolom/vak/binnenvak/kadervak waarvan de cel deel uitmaakt
- verwijder daaruit de celwaarde

De eerste werkwijze kent 36 akties, de tweede 1.
De code in het bestand maakt gebruik van de tweede werkwijze.

VBA-aanpak

De celcoördinaten(rij, kolom) van iedere deelverzameling worden opgeslagen in een item van een 1-dimensionele Array.
Dat is een 1-dimensionele Array die wordt opgeslagen in een niet-zichtbaar 'benoemd gebied' van Sheet1: Sheet1.Names("sb").
De Array bevat 36 items.
Dankzij het feit dat de Array een 1-dimensionele Array is, kan er op de items van de Array gefilterd worden.
Om alle deelverzamelingen te filteren waarin een bepaalde cel voorkomt volstaat de filteropdracht voor een 1-dimensionele Array.
Bijvoorbeeld: de cel(2,3) kan gefilterd worden met
sn=filter([sb],"23_")

1.3 Routine 3

Iedere cel van een rij, kolom, vak, binnenvak, kadervak bevat de cijfers die daarin mogelijk zijn.
Per rij, kolom, vak, binnenvak, kadervak 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 de inhoud van die cel door dat cijfer.

werkwijze

Doorloop alle 36 deelverzamelingen en kontroleer de frekwentie waarin ieder cijfer daarin voorkomt.
- een lus van 36 omwentelingen: alle deelverzamelingen
- met een binnenlus van 9 omwentelingen: alle mogelijke cijfers

Als een cijfer in een deelverzameling slechts 1 keer voorkomt:
- zet dat cijfer in de cel in plaats van het groepje van mogelijke cijfers voor die cel.
- noteer van die cel drie gegevens:
- het nummer van de rij
- het nummer van de kolom
- het cijfer in de cel

Gebruik vervolgens routine 2 om de gevonden cijfers uit alle gekoppelde deelverzamelingen te verwijderen.

1.4 Routine 4

De sudoku bevat 9 vakken, 4 binnenvakken en 5 kadervakken.
Wanneer een bepaald cijfer alleen in één rij of één kolom van het vak voorkomt, betekent dat
- dat het cijfer niet kan voorkomen in alle andere cellen van de deelverzamelingen waarvan deze cellen deel uitmaken
- voorbeeld: als van het vak cel(1,1) .. cel(3,3) alleen cel(1,1), cel(1,2) of cel(1,3) een 7 bevat kunnen de cellen 1,4 1,5 1,6 1,8 1,9 in rij 1 geen 7 bevatten.

werkwijze

Doorloop alle 18 vakken(vakken, binnenvakken, kadervakken)
- verwijder dat cijfer uit alle cellen van de deelverzamelingen waarvan deze cellen deel uitmaken.
- als daardoor een cel slechts 1 cijfer bevat.
noteer van die cel drie gegevens:
- het nummer van de rij
- het nummer van de kolom
- het cijfer in de cel

Gebruik vervolgens routine 2 om de gevonden cijfers uit alle gekoppelde deelverzamelingen te verwijderen.

2. Programmeertechniek

Recursie

De toekenning van een cijfer aan een cel heeft meteen gevolgen voor alle andere cellen van de deelverzameling waarvan de toegekende cel deel uitmaakt.
Het aantal mogelijke cijfers in die cellen wordt daardoor beperkt.
Nadat in alle betrokken cellen het cijfer van de toegekende cel is verwijderd dient opnieuw geanalyseerd te worden of aan een andere 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.

Deelverzamelingen

In Routine 2 dient op basis van rijnummer en kolomnummer bepaald te worden in welke deelveramelingen de cel voorkomt.
In Routine 3 en 4 dient per deelverzameling bepaald te worden welke cellen in die deelverzameling voorkomen.

Het is mogelijk dit per keer te berekenen, maar dat blijkt behoorlijk wat rekencapaciteit te vergen.
Een vorm van 'harde' codering' blijkt veel sneller en ook gemakkelijker te volgen.
Per deelverzameling worden de cellen met rijnummer en kolomnummer vermeld.
Voor alle routines leidt dat tot een sterke vereenvoudiging van code.
Omdat alle 36 deelverzamelingen in 1 Array staan, kan een filter-opdracht op basis van rij- en kolomnummer in 1 keer alle deelverzamelingen waarin een cel voorkomt slecteren.

De opslag van deze harde gegevens vindt plaats in 1 onzichtbaar benoemd gebied, met een Array van 36 elementen.
De macro om dat benoemde gebied te vullen staat in de codemodule van 'ThisWorkbook' en heet 'M_names'