Go Down

Topic: [Projekt] Sudoku Lösungsprogramm f. d. Jackentasche (Update) (Read 2634 times) previous topic - next topic

RudiDL5

Update: Im SudokuSolverUNO ist nun auch ein -Generator [Beitrag #23]


(Teil 1 von 3)

Hallo Freunde der Bits und Bytes,

ich habe KEINE Frage an euch - sondern ich möchte gerne ein Projekt von mir vorstellen, welches an diesem WE in ein bemerkenswertes Stadium getreten ist: Mir ist es nämlich gelungen, ein Lösungsprogramm für die bekannten Zahlenrätsel „Sudoku" in einen Arduino UNO R3 zu bringen...

Einen „SudokuSolver UNO"

Vorgeschichte dazu:

Vor ca. 2 Jahren kaufte ich mir ein „Starterkit", um mein Programmier-Repertoire um das Thema „Microcontroller" zu erweitern. Übermäßig viel gelötet und gebastelt habe ich nicht, sondern ich habe eher etwas „Grundlagenforschung" zur Controller-Programmierung durchgeführt.

Anfang diesen Jahres hat mich „Doc_Arduino" unbewusst dazu inspiriert mich näher mit den LCD-Displays zu befassen, die Beiträge von „Serenifly" zu objektorientierter Programmierung lieferten einen weiteren Antrieb. Und ein persönliches Gespräch mit „agmue" um Pfingsten herum gab mir dann „den Rest". Von diesem Moment an kreisten meine Gedanken nahezu hauptsächlich um einen „alten Plan": Ich löse „zur Entspannung" schon seit Jahren gerne mal ein „Sudoku"-Rätsel. Warum also nicht all meine Programmier-Kenntnisse zusammenkehren und in den Arduino zu pressen? Na ja, damit begann ein Abenteuer, welches m.E. wirklich erwähnenswert ist:

Die wesentliche Story:

Zunächst suchte ich im Netz nach Algorithmen, wie man so etwas durch den PC lösen lassen könnte. So etwas habe ich dann irgendwo in „Javascript" gefunden. Um die internen Strukturen zu verstehen habe ich das vorliegende JS-Script zunächst aufgeschlüsselt und in eine Class in Object-Pascal (Delphi) umgewandelt (geht für mich im Moment einfacher von der Hand). Nach einigem Kopfschütteln ist es mir dann auch gelungen. Das Kopfschütteln lag aber eher daran, weil in der JS-Vorlage extrem viel mit Strings und großen Arrays jongliert wurde. Im Laufe der Zeit stellte ich fest, dass in dieser Vorlage noch ein Haufen Fehler drin waren, die ich entsprechend „ausmisten" konnte. Über kurz oder lang hatte ich dann die massive String-Verabeitung, die vielen globalen Variablen und weitere Fehler in den Griff bekommen - und konnte mit meinem Delphi-Programm auch die schwersten Sudokus lösen lassen.

So weit, so gut. In meiner Euphorie fing ich an, diese Pascal-Class „direkt" in C++ umzustricken. Anfangs ging es gut - bis dann der Speicher schlapp machte... 2048 Bytes auf dem ATMega328P sind wirklich nicht viel. An dieser Stelle war ich nahezu geneigt das Projekt zu begraben. Zumal ja auch noch notwendige Rekursionen auf dem Aufgabenzettel standen.

Na ja, zum Training und um eventuell weitere Erkenntnisse zu sammeln - habe ich die Delphi-Class in eine PHP-Class umgebaut. Das war  schon wieder ein eigenes Abenteuer. Aber auch das klappte später und nun konnte ich das Sudoku-Lösungsprogramm auch auf jede Homepage bringen, die auf einem Server mit PHP-Unterstützung läuft. Ach ja, und weil es so viele „Spaß" machte, baute ich alles für „nicht-PHP-Homepages" noch einmal um in eine OOP-Class unter Javascript. Jawollja, auch das geht nun! Egal ob im WWW oder auf dem „Localhost", alles schnurrt wunderbar! OOP in Pascal, PHP und sogar in Javascript. Nur auf dem Winzling 328P in C++ klappte nix, rein gar nix.

Was konnte ich machen? Das Thema begraben? Neee, wollte ich nicht wirklich. Dafür hatte ich schon zu viel darüber gelernt und in Erfahrung gebracht. Also habe ich meine lange Programmier-Praxis hervorgekramt - und eine Art „Datenkompression" für den UNO erdacht:

Immerhin brauche ich für die Eingabe eines Rästels 9x9 Felder für die Ziffern 1 bis 9 so wie die 0 für „leer". Da die Ziffern 0..9 jedoch jeweils maximal nur 4 Bits belegten, konnte dieses Array bereits via „Nibbles" (halbe Bytes) von 81 Bytes auf 40,5 (41) Bytes reduziert werden. Die entsprechenden I/O-Routinen dafür waren schnell geschrieben. Interessanter wurde es für die „Abstreichliste". Eine Sudoku-Lösung „lebt" eigentlich davon, dass man alle nicht mehr benötigten Ziffern in einem String von „123456789" löscht. Mir den verbleibenden Ziffern konnte man weitere Berechnungen durchführen. Manchmal ergab sich daraus auch direkt nur noch EINE verbleibende Ziffer, die dann schon ein Ergebnis lieferte.

Nun denn, da aber über JEDER „Zelle" des Sudokus erstmal so ein „Init-String" von 9 Zeichen schwebte, ergab das einen Speicherbedarf von immer noch 729 Bytes - plus Eingabe? - zu viel für den UNO! Besonders wenn noch viele For-Schleifen zur Berechnung eingebaut werden mussten. Okay, das wäre fast schon ein frühzeitiges Ende gewesen. In einer ruhelosen Nacht mit Alpträumen ;-) kam mir der Gedanke, dass man diese „Zeichenkette" auch anders darstellen kann: Nämlich als Bit-Folge, wobei jedes Bit eine Ziffer repräsentiert.

Das ergab „nur noch" 2 Bytes für ein „Abstreich-Feld", statt 9. An Stelle 810 Bytes (729+81) konnte ich damit den RAM-Verbrauch schon auf  203 (162+41) Bytes reduzieren. Im Hinterkopf dachte ich aber immer wieder an die Rekursionen aus dem Pascal-Programm: Zwei Bytes (16 Bits) für 9 Ziffern verplemperten immer noch 7 Bits, die man anderweitig verwenden könnte... Also „presste" ich alles noch einmal zusammen und hatte nun eine Struktur von „9 Zahlen-Bits" für jedes Feld erdacht. Das ergab noch einmal eine weitere Reduzierung, so dass letztendlich „nur noch" 92 Bytes übrig blieben, für die ursprünglich ein String-Array von 729 Bytes notwendigt gewesen „wäre" (9x9 /8). Okay, ein Byte hat 8 Bits, 9 Bits je Zelle passen aber nicht in ein Byte. Der Algorithmus, um aus „Bytes mit 9 Bits" einen vernünftigen Wert zu bekommen war nicht „von Pappe". Aber wenn ich mich schon mal mit so einer Sache befasse - dann lasse ich solange nicht los, bis ich es dann DOCH geschafft habe. Punkt.

Unterm Strich verbraucht bei mir ein Sudoku eingangs jetzt nur noch 133 Bytes! Das brachte neben den notwendigen Schleifen- und Kontroll-Variablen nun den notwendigen Platz im RAM, den ich für die „3 Lösungs-Algorithmen plus Rekursion" benötigte.

RudiDL5

(Teil 2 von 3)

Butter bei die Fische: Ein paar Details und Fakten zum Programm „SudokuSolver UNO"

Details und Erklärungen:

Ein Standard-Sudoku besteht in der Regel aus 9x9 Feldern, in denen einige Ziffern bereits vorgegeben sind. Die fehlenden Ziffern müssen dann von Hand eingefügt werden. Dabei ist darauf zu achten, dass in jeder Zeile, in jeder Spalte und in jedem 3er-Block jede Ziffer nur ein einziges Mal vorkommen darf. Die in vielen Publikationen vorgestellten Sudokus kann man im wesentlichen in die Gruppen „Leicht", „Mittel" oder „Schwer" einordnen. Dazu gibt es 3 hauptsächliche Regeln:

Regel 1, „Ausschluß-Verfahren": Man prüft, ob in irgend einer Zeile, Block oder Spalte eine bestimmte Ziffer vorhanden ist und entfernt diese aus den Abstreichlisten der betroffenen Felder der selben Zeile, Spalte oder Block. Daraus ergibt sich oft schon, dass in ein freies Feld nur noch eine einzige Ziffer gesetzt werden darf.

Regel 2, „Blockscan-Verfahren": Wenn eine Ziffer in einer Spalte oder Zeile eines Blocks vorkommt, darf diese Ziffer in keiner anderen Spalte oder Zeile der benachbarten und übernächsten Blöcke vorkommen. Diese sind aus den betreffenden Abstreichlisten ebenfalls zu entfernen.

Regel 3, „Aufdecken versteckter Triplets": Wenn eine Ziffer in einer Zeile (oder Spalte) in zwei Blöcken nicht mehr gesetzt werden darf, dann muss die Ziffer im verbliebenen Block in dieser Zeile (oder Spalte) stehen. Daher muss diese Ziffer ebenfalls aus den verbleibenden Zeilen (oder Spalten) dieses Blocks entfernt werden.

Weiter möchte ich an dieser Stelle nicht darauf eingehen. Es gibt im Netz jede Menge höchst wissenschaftliche Dokumente, in denen dieses alles aufgeführt wird. Hier fürs Forum denke ich, dass es den Rahmen mehr als sprengen würde.

Wenn dann nach obigen Regeln keine Lösung mehr gefunden werden kann, beginnt die Simulation durch Einsetzen von Ziffern an Hand der verbleibenden Exemplare in den betreffenden Absteichlisten: Das Feld und die Ergebnis-Liste wird zunächst gesichert, danach ruft sich diese Funktion nacheinander mit den verbleibenden Ziffer der aktuellen Abstreichliste selbst auf („Rekursion").

Hier kommt der „Knackpunkt" für den Arduino UNO: Die von von mir getesteten Rätsel wurden nach 4-7 Rekursionen erfolgreich beendet. Selbst „extrem schwere". Jeder Aufruf des „Lösungsprogrammes" benötigt exakt 205 Bytes zusätzlichen Speicher (durch „FreeRAM" hier aus den Tutorials ermittelt). Zurückgerechnet kann der UNO also maximal 8 mal sich selbst aufrufen. Ein Rücksprung aus den Rekursions-Schleifen wird also DANN erzwungen., wenn entweder das Rätsel gelöst ist, ODER wenn der Speicher knapp wird. In DIESEM Fall kann es sein, dass es nicht 100% korrekt gelöst wurde. Auf jeden Fall verhindert diese „Grenze", dass der Mega328 „ins Nirvana abschwirrt".

Alle übrigen Fakten:

Speicherbedarf bei Kompilierung:
15.358 von 32.258 Bytes

Globale Variablen:
249 von 2048

Verbleiben noch 1799 Bytes, geteilt durch (siehe oben) 205 ergeben das 8 Ebenen Rekursions-Tiefe. Danach ist Ende im Gelände.

Diese Daten wurden mit der IDE 1.6.0 ermittelt, mit 1.6.9 ergeben sich geringfügig andere Werte.

Verwendete externe Bibliotheken:
KEINE einzige! Alle Classes wurden aus o.g. Gründen neu erstellt und auf das Mindestmaß beschränkt. Daher sind folgende eigene Classes entstanden:

TSudoku, ca. 900 Zeilen Code (Eigene Entwicklung)
TButton, ca. 80 Zeilen Code (Ersatz für „Bounce2" oder ähnliche)
TDisplay, ca. 120 Zeilen Code (Ersatz für „LiquidCrystal.h"
TEprom, ca. 50 Zeilen Code (Ersatz für EEPROM.h)

Texte via PROGMEM, ca. 300 Zeilen Code = knapp 2300 Bytes
Hauptprogramm (Setup, Loop, div. Hilfsfunktionen), ca. 880 Zeilen Code
Source-Code gesamt: ca. 64 kByte
KEINE String-Objekte
Ein paar wenige selbst erzeugte Sonderzeichen fürs Display

Hardware:
Arduino UNO aus dem StarterKit
6 einfache Taster (Down Active, pulled up)
LCD-Display 20x4, weiss auf blau
4 LEDs
- Grün für „Gelöst"
- Gelb für „In Arbeit"
- Rot für „Fehler"
- Blau: Blinkendes „Lebenszeichen"
Und ein paar passende Widerstände für Pullups und LEDs

Lösungszeit für selbst schwere Sudokus: Weniger als 10 Sekunden. Hierbei sind ca. 2 Sekunden manuell eingefügte „Kunstpause", sonst wäre „der kleine" VIEL zu schnell fertig ;-)
Entwicklungszeit inkl. Pascal, PHP und Javascript: gut 2 Monate

RudiDL5

(Teil 3 von 3)

Hier nun ein paar Funktionen des Programmes:
Beim Einschalten erscheint zunächst ein „SplashScreen" und die LEDs blinken etwas. Hier sind ein paar wenige Delays, die optische Effekte beim Start oder nach Reset bewirken sollen:

SplashScreen beim Start

BILD1



Das Menü umfasst 11 Punkte. Es scrollt mittels Up- und Down-Tasten rauf oder runter, der Cursor blinkt damit man merkt dass er „lebt":

- Eingabe (ein beliebiges Sudoku kann eingegeben werden)
- Speichern (für spätere Verwendung kann es in EEPROM verschoben werden)
- Lösung suchen  (Start nach Rückfrage)
- Auswertung
- Alles löschen (zeichnet das Eingabefeld leer, nach Rückfrage)
- Aus EEPROM laden (zuvor gespeichertes Sudoku)
- Lade DEMO (leicht)
- Lade DEMO (mittel)
- Lade DEMO (schwer)
- SplashScreen (zeichnet SplashScreen und setzt diverse Variablen auf null)
- Reset (eigentlich Schnickschnack, ruft „JMP 0" auf)

BILD2



1. Beispiel für die Eingabe: Mittels „ESC" kann man zwischen „Eingeben" und „Nur anzeigen" umschalten. Im Modus „Eingeben" kann man nur rauf- oder runter scrollen.

BILD 3



2. Beispiel für die Eingabe: Nach „ESC" springt der Cursor ins Feld und durch Drücken auf ENT( + ) kann die betreffende Zahl höhergezählt oder eben gelöscht werden.

BILD 4



Beispiel für „Speichern": Das gerade eingegebene Sudoku kann ins EEPROM kopiert werden. Denn falls er mal wirklich abschmieren sollte erspart man sich dadurch das erneute Eintippen

BILD 5



Lösungs-Anforderung nach Bestätigung einer „Sicherheitsabfrage"

BILD 6



Fertig-Meldung (meistens irgendwie bei 3-6 Sekunden oder so)

BILD 7



Die Auswertung eines (nicht?) gelösten Sudokus:
Status-Meldungen:
- GELÖST
- NICHT gelöst
- Inkonsistent
- Abgebrochen
- Fehler
- Feld war leer
- Zu wenig Vorgaben (mindestens 17 Ziffern)
- Zu wenig RAM
- Stand By
A: Aufrufe Regel 1
B: Aufrufe Regel 2
C: Aufrufe Regel 3
R: Benötigte Rekursions-Tiefe

BILD 8



Nachsatz:

Ich habe leider nur einen Arduino UNO mit seinem begrenzen Speicher. Möglicherweise wird ein größeres Exemplar wesentlich tiefere Rekursionen durchführen. Bis jetzt war das aber noch nicht nötig.

Nun denn, ich hoffe dieser Beitrag war für den einen oder anderen interessant. Falls Fragen sind: Sobald ich Zeit finde werde ich diese sicherlich beantworten.

Ein weiterer Schritt wird sein, das ganze auf eine Platine zu löten, damit ich einen „Sudoku-Löser für die Hosentasche" erhalte. Vielleicht mit einem netten Gehäuse. Oder später sogar via kleinem TFT-Display. Schaun mer ma...


Happy Programming,
und mögen die Bits mit euch sein
RudiDL5

RudiDL5

Hmmm, irgendwie klappte das mit dem Hochladen der Bilder nicht. Momento...
So, fertig  ;)
Nun denke ich mir 'ne Platine und 'n Gehäuse aus, dann gehe ich damit spazieren...
 :D

uwefed

Hast Du an das Userinterface schon gedacht?
http://makezine.com/2010/07/20/nixie-tube-sudoku-board/   ;)
Grüße Uwe

RudiDL5

Hallo Uwe,
Wow, das kannte ich noch nicht. Cool. Aber mein Progrämmchen läuft halt auf einem UNO mit einem LCD-Display und kann mit Batterie überall hin getragen werden. Klein genug für fast jede Jackentasche  ;)
LG, Rudi

(ich kämpfe gerade mit den Bildern...)

michael_x

Super, Rudi.

Ich war zwar immer der Meinung, das Lösen ist selbst für einen Uno machbar bis einfach, wenn die Darstellung nicht so aufwendig wäre, aber selbst der Anwendungsfall "für die Hosentasche" hätte mich doch eher zu einer Android-Umgebung verleitet.

RudiDL5

Hi Michael,
joa, aber ich komme noch aus der Steinzeit und habe gar kein Smart-Dingens oder so. Und wo bliebe dann die Herausforderung?
 :D

Eisebaer

hi,

Du magst die herausforderung und dann baust Du Dir ein programm, das Dir das lösen der sudokus abnimmt ???

nein, im ernst, alle achtung.

gruß stefan

uwefed

Wo bekommst Du die Sudokus her? Mit einem zweiten Arduino?  ;)  ;)

Uwe

RudiDL5

@Eisebaer:
Na jaaaaaaa, die Frage ist berechtigt... aber die Rätsel aus den diversen Publikationen löse ich nach wie vor "zu Fuß" :D Ich wollte einfach wissen, ob das Programm in "den Kleinen" passt  :D

@Uwe:
Oooooch, in fast jeder Zeitung stehen doch so Dinger, oder beim Frisör oder so. Aber ich habe erst heute begonnen einen Generator dafür zu bauen. Schaun mer ma, vielleicht bekomme ich den ja auch noch rein. Platz ist ja im Code noch reichlich vorhanden  :)

HotSystems

Hallo Rudi,

auch von mir, RESPEKT!

Das ganze dann mit einem Atmega-StandAllone und einem Oled-Display wird wunderbar klein.
Gruß Dieter

I2C = weniger ist mehr: weniger Kabel, mehr Probleme. 8)

uxomm

Always decouple electronic circuitry.

RudiDL5

Dankeschön für's Lob  :)

@HotSystems:
So in der Art stelle ich es mir vor: Irgend so ein Display, damit ich das im Garten oder so noch gut lesen kann... Welches Display ich dafür einsetzen kann / werde weiß ich noch nicht, da forsche ich noch ein wenig. Aber so als autonomes Spielzeug? Stelle ich mir recht nett vor  ;)
73 de Rudi

volvodani

Code: [Select]
if (projectideaiscool==true){
karma++;}
if(welldocumented==true){
karma++;}


Sehr coole Sache es gefällt mir sehr.
Planst du auch ne Veröffentlichung des Source Codes?
Gruß
DerDani
"Komm wir essen Opa!" - Satzzeichen retten Leben!

Go Up