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.
