Programma: Sudoku_oplossen
Autheur: eFKa
Versie 1.6.05
Oktober 2008
Executable: Sudoku_project.exe
Werking programma:
Het programma lost een Sudoku puzzel op.
Ze probeert een puzzel op te lossen door middel van een aantal ingebouwde algoritmen. In de release nummers hieronder is terug te vinden: de verklaring en de historie van de gebruikte algoritmen of ook wel de oplosmethode benamingen.
Gebruik:
Klik op ‘Invoer’ en vul de velden met de getallen uit de puzzel en klik op ‘Start’. Plaats een vinkje bij de twee weergave opties en het programma zal na elke stap stoppen en weergeven welke module bij het gevonden getal hoort.
Het kan zijn dat er al velden voor ingevuld zijn, in dat geval bestaat er een file op C:\tmp genaamd SudokuTestCase.txt of de file: E:\VB_projecten\SudokuTestCase.txt staat op uw systeem.
Versie historie:
1.1.8 Eerste initiële versie met hierin 4 modules:
- BlokLijnen, horizontaal en verticaal.
- Lijnen, horizontaal en verticaal.
- Blokken
- Cel
1.2.02 Versie uitgebreid met geblokkeerde lijn mogelijkheden (z.g.: locked candidates) Uitzonderingen tabel vullen aan de hand van gevonden geblokkeerde mogelijkheden in lijnen
- Module Lijnen uitgebreid met uitzonderingstabel
1.3.03 Versie uitgebreid met geblokkeerde blok mogelijkheden (z.g.: locked candidates)
Uitzonderingen tabel vullen aan de hand van gevonden geblokkeerde mogelijkheden in blokken
- Module Bloken uitgebreid met uitzonderingstabel
- Module cel inventariseert ook deze uitzonderingstabel
1.4.01 Versie uitgebreid met geïsoleerde paren (z.g.: naked pairs) Uitzonderingen tabel vullen aan de hand van gevonden geïsoleerde paren.
- Module Invent_Naked is geïntegreerd om de paren te lokaliseren uit de uitzonderingstabel en vast te leggen in een aparte administratie (tabel)
- Module NakedPair vult de uitzonderingstabel aan de hand van het gevonden geïsoleerde paar.
1.4.02 Versie uitgebreid met geïsoleerde drietallen (z.g.: naked triples) Uitzonderingen tabel vullen aan de hand van gevonden geïsoleerde drietallen.
- Module NakedTriple vult de uitzonderingstabel aan de hand van het gevonden geïsoleerde drietal.
1.4.03 Gaandeweg bleek een NakedTriple ook te kunnen bestaan uit drie triples van paren van 2. Deze versie is uitgebreid met deze oplosmethode.
1.4.04 Tikfout in NakedTriple waardoor triples niet goed ingevuld worden en programma vast loopt.
1.5.00 Optische wijziging aan programma door gevoerd (zoals naam SUDOKU in het Japans)
1.6.00 Versie uitgebreid met module uitproberen.
1.6.01 Versie aangepast: locked candidates was niet volledig, gevonden geblokkeerde mogelijkheden hoeven niet aansluitend te zijn. Er kan een ruimte zitten tussen de candidates echter wel binnen een blok. Versie is hierop verbeterd.
1.6.02 Foutje hersteld
1.6.03 Module uitproberen kan geactiveerd worden middels vinkje te zetten in “uitproberen toestaan”.
1.6.04 Versie bestaat feitelijk niet. Deze tussen versie is gebruikt voor de conversie van de software waarin het programma is gebouwd namelijk van Visual Basic 5 naar Visual Studio 2005
1.6.05 Versie in VB met kleine verbeteringen zolang 1.7.00 in VS nog niet stabiel is. (o.a. conversie
Strings naar Integers, declaraties, invoer checks ….)
1.7.00 Beta versie in Visual Studio 2005
Gelijktijdig met de ontwikkeling in Visual Studio ben ik ook bezig een sudoku programma te maken voor Windows Mobile 6 wat draait op de nieuwste mobieltjes. Er is nog geen versie voor Symbian. De andere SmartPhone variant.
1.7.01 Versie waarin de Layout moet worden verbeterd. Na de conversie zijn enkele teksten vervaagd.
Module:
BlokLijnen Elke rij/kolom bevat een 1 t/m 9. Hieruit volgt dat bij een blok van drie lijnen de mogelijke oplossingen afgestreept kunnen worden, als er al 2 lijnen gevuld zijn met hetzelfde getal in een ander blok. In de drie overgebleven velden van de derde lijn in het derde blok wordt gezocht in de haaksopstaande lijnen naar de aanwezigheid van dat bewuste getal. Als er dan één optie overblijft wordt dit veld gevuld met het gezochte getal.
Lijnen Elke rij/kolom bevat een 1 t/m 9. In die rij of kolom wordt gezocht naar de ontbrekende nummers en gekeken of deze in de haaksopstaande lijn of betreffend blok al bestaan. Als er dan één optie overblijft wordt deze gevuld met het gezochte getal.
Vanaf versie 1.2.02 wordt gezocht naar zogenaamde locked candidates. Doordat blijkt dat een getal maar op twee plaatsen kan staan in een rij en een blok, vallen een aantal andere mogelijkheden (kandidaten) in een blok af. Deze geblokkeerde mogelijkheden worden geregistreerd in een uitzonderingslijst. Deze uitzonderingen worden behandeld als ware het een gevonden getal.
Blokken Elk blok bevat een 1 t/m 9. In het blok wordt gezocht naar de ontbrekende nummers en gekeken of deze in de kruisende lijnen al bestaan. Als er dan één optie overblijft wordt deze gevuld met het gezochte getal.
Cel In elk individueel veld moet een 1 t/m 9 gevuld worden. In de kruisende lijnen wordt gecontroleerd welke getallen al gebruikt zijn. Bij acht van de negen aanwezige getallen kan het ontbrekende negende getal ingevuld worden. Na de introductie van de geblokkeerde mogelijkheden (versie 1.3.03) wordt ook de uitzonderingstabel hierop geraadpleegd.
NakedPair Wanneer er in twee cellen een unieke combinatie van twee kandidaten voorkomen en alleen deze twee kandidaten dan kunnen de twee waarden als kandidaat uit alle overige cellen verwijderd worden.
NakedTriple Wanneer er in drie cellen een unieke combinatie van drie kandidaten voorkomen en alleen deze drie kandidaten dan kunnen de drie waarden als kandidaat uit alle overige cellen verwijderd worden.
Uitproberen Als er geen oplossing te vinden is gaat deze module zoeken naar een blok waar twee cellen open zijn en kiest een van de twee mogelijkheden. Je zou dit een gok kunnen noemen. Als de gekozen mogelijkheid verkeerd uitpakt wordt dat afgevangen en de tweede optie uitgeprobeerd.
ToDo:
Na naked quads inbouwen.
Check op de handmatig ingevoerde getallen niet afdoende.