Arduino Forum

International => Deutsch => Topic started by: RudiDL5 on Jul 31, 2016, 10:39 pm

Title: [Projekt] Sudoku Lösungsprogramm f. d. Jackentasche (Update)
Post by: RudiDL5 on Jul 31, 2016, 10:39 pm
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.
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 10:41 pm
(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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 10:46 pm
(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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175813)


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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175815)


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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175819)


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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175821)


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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175823)


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

BILD 6
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175825)


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

BILD 7
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175827)


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
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=175829)


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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 10:50 pm
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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: uwefed on Jul 31, 2016, 10:54 pm
Hast Du an das Userinterface schon gedacht?
http://makezine.com/2010/07/20/nixie-tube-sudoku-board/   ;)
Grüße Uwe
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 11:00 pm
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...)
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: michael_x on Jul 31, 2016, 11:07 pm
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.
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 11:18 pm
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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: Eisebaer on Jul 31, 2016, 11:34 pm
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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: uwefed on Jul 31, 2016, 11:39 pm
Wo bekommst Du die Sudokus her? Mit einem zweiten Arduino?  ;)  ;)

Uwe
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Jul 31, 2016, 11:50 pm
@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  :)
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: HotSystems on Aug 01, 2016, 09:51 am
Hallo Rudi,

auch von mir, RESPEKT!

Das ganze dann mit einem Atmega-StandAllone und einem Oled-Display wird wunderbar klein.
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: uxomm on Aug 01, 2016, 11:30 am
Sehr beeindruckendes Projekt!
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Aug 01, 2016, 11:38 am
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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: volvodani on Aug 01, 2016, 11:51 am
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
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Aug 01, 2016, 01:03 pm
@volvodani:
Danke für's Lob und die Pünktchen  :)

Irgendwie schwebt mir im Hinterkopf vor, dass ich das in der Tat veröffentlichen wollte. Zur Zeit erscheint der Code dazu aber eher wie eine ägyptische Wandmalerei - Sprich: Er ist für Außenstehende so gut wie gar nicht "lesbar" dokumentiert und manche Dinge sehen aus wie Hieroglyphen... ( Aussage meiner Lebensgefährtin  ;)  )

Einige Routinen habe ich für mich mit ein paar Anmerkungen versehen - man(n) kann nicht immer ALLES im Kopf behalten. Aber der Rest? "katastrophal". Das müsste ich erst etwas "überarbeiten".

Es steht schon (leider nicht fotografiert) im Display:
"Suche Loesung, bitte warten ...." :D
LG, Rudi
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: ElEspanol on Aug 01, 2016, 01:45 pm
Nächster Schritt:

Kamera liest Sudoku ein
Plotter füllt es aus
 :D  :D  :D

Übernächster Schritt:
Das ganze passt wieder in die Hosentasche

Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: michael_x on Aug 01, 2016, 02:38 pm
Der MeerschweinchenKöttel-Roboter (http://forum.arduino.cc/index.php?topic=360939.10) könnte das doch auch machen:

Sudoku im Käfig abscannen, ausrechnen, ausfüllen.

Müsste man nur den Köttelgreifer durch einen Stifthalter ersetzen.
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Aug 01, 2016, 08:43 pm
Hihihi..... 
das sind in der Tat interessante Gedankengänge. 
Na ja, ein Plotter in der Hosentasche würde einem die Büx wahrscheinlich herunterziehen... :D

Doch die Idee mit einer kleinen Kamera gefällt mir. Ganz am Anfang schwebte mir ebenfalls so etwas vor. Dann hatte ich aber gesehen, dass jemand so etwas schon mit einem LEGO-Mindstorm-Roboter gebaut hatte. Das dauert nur unendlich lange, bis alles eingelesen und ausgefüllt war. Doch einen Cam, deren Bild dann (aufbreitet) auf ein Display gebracht wird? Sicherlich wert mal darüber nachzudenken.

LG, Rudi
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: Doc_Arduino on Aug 01, 2016, 09:58 pm
Hallo Rudi,

auch von mir verspätet großen Respekt.
Der Mann der mehrere Programmiersprachen beherrscht und sich hier im Forum zurückhält.  :)
Die Beschreibung dazu und das Projekt als solches ist einfach genial. Beim lesen Deiner Doku dachte ich sofort daran, dass du das zum Bsp. in der c't veröffentlichen solltest oder in der make von heise, aber die hat eine kleinerer Auflage. In der c't kamen auch schon Arduino Artikel dran. Aber eher kleine, alles für Anfänger. Waren keine Kracher.
Schreib einfach mal hin. Mal sehen was passiert.


Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Aug 01, 2016, 10:37 pm
Hi Doc_Arduino, danke für's Lob  :)

Na ja, ich halte mich wohl deshalb zurück, weil ich nicht so der große Lötkoben-Künstler bin. Sicherlich habe ich im Amateurfunk und in der Musik viel Zeugs zusammengebaut - aber vom Großteil der speziellen Arduino-Peripherie habe ich noch zu wenig Basiswissen um "wirklich" mitmischen zu können. Hier lerne ich täglich hinzu, kann aber mangels Masse nicht wirklich mithalten.

Na ja, ich bin seit eh und je mehr auf den Tasten am klappern. Erst heute habe ich dabei herausgefunden, wie "einfach" und "extrem platzsparend" es sein kann, den seriellen Port OHNE die Standard-Sachen wie "Serial.begin()" und Co. zu verwenden. Genau das brauchte ich aber für mein "Spielzeug"... und habe direkt die Ausgabe auf den seriellen Monitor in eine eigene Mini-Class gegossen  ;)

Warten wir's ab, ich baue noch 'nen Rätselgenerator ein, und die Ideen von den Kollegen oben sind auch irgendwie interessant...

LG, Rudi
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: michael_x on Aug 02, 2016, 04:14 pm
Quote
Na ja, ein Plotter in der Hosentasche
Nicht dass wir uns missverstehen: Mein "machs doch anders" heisst nicht, dass ich von deiner Idee nicht begeistert wäre. Das "hihihi ...interessant..." interpretiere ich aber so, dass wir uns schon verstehen.

Hosentaschenformat ist zwar super, aber das Sudoku auch sehen können, hätte auch was. 8)

Bin auf deinen Generator gespannt. ( Das gäbe locker noch ein Karma ;) )
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: agmue on Aug 02, 2016, 06:49 pm
Hallo,
ich bin mal frei und verlinke Rudis Sudoku Projekt.
Das war mein Vorschlag an Rudi gewesen, eine eigene Projektvorstellung mit Verlinkung zum Sammelthema. Also ja, finde ich gut.

Zur Illustration könntest Du im Sammelthema noch ein Foto ergänzen. Ein Bild sagt mehr ...
Title: Re: [Projekt] Sudoku Lösungsprogramm für die Jackentasche (ATMega328P)
Post by: RudiDL5 on Aug 14, 2016, 09:42 pm
Hallöle,
hier mal ein Update zu meinem Projekt:

Auch wenn es in den Kommentaren zu eingem Schmunzeln kam, speziell die Aussage
Quote
„Wo bekommst Du die Sudokus her? Mit einem zweiten Arduino?"
... hat mich genau DAS angestachelt, an dem Teil weiter zu forschen. Und dieses Folge-Abenteuer ist nun „Geschichte" :D

Seit heute funktioniert innerhalb des SudokuSolver UNO auch ein Sudoku-Generator! Und das sogar mit 5 Schwierigkeitsstufen. Hier ein paar Bilder dazu, Erklärungen am Schluss.

1. Das Programm wurde um 2 Punkte ergänzt: „Serieller Monitor" + „Sudoku-Generator"
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177306)

2. Beim Generator kann man 5 Stufen wählen, vom „1 - Sehr leicht" bis „5 - Sehr schwer"
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177308)

3. Nach dem Start kann man die Berechnung zur Not abbrechen (wenn es zuuu lange dauert)
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177310)

4. Fertigmeldung, zeigt die Anzahl der Durchläufe die evtl. notwendig wurden
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177312)

5. Nach „Okay" springt er direkt in die Eingabe-Maske zum Begutachten
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177314)

6. Da die Eingabe etwas anstrengend ist kann man das auch auf den seriellen Monitor übertragen
(https://forum.arduino.cc/index.php?action=dlattach;topic=415879.0;attach=177316)

Ein paar Details dazu:

Ein Sudoku zu erstellen ist weniger trivial als es zu lösen! Zunächst muss ein vollständig gelöstes Rätsel erstellt werden, danach können einzelne Ziffern gelöscht werden. Jaaa aber... Einfach „beliebige" Ziffern aus einem Rätsel zu löschen kann dazu führen, dass ein Rätsel nicht mehr „eindeutig" lösbar - unter Umständen sogar „unlösbar" wird. Dieses sollte man vermeiden, indem man nach dem Entfernen einer Ziffer nach einer Lösung ohne Rekursion sucht. Falls also ein Rätsel „inkonsistent" wird muss die zuletzt entfernte Ziffer wieder eingesetzt werden. Der Vorgang muss anschließend mit einer anderen Ziffer wiederholt werden („Backtracking").

Anfangs hatte ich versucht, die Rätsel per Zufall füllen zu lassen, das hat sich als viel zu zeitraubend herausgestellt. Dann fand ich einen Algorithmus, bei dem eine fertige „Standard-Lösung" nach bestimmten Regeln, aber auch per Zufall lediglich „vertauscht", „verschoben", „verdreht" und/oder „gespiegelt" wird. Das resultierende Ziffern-Chaos kann nun nach dem oben erwähnten „Backtracking-Verfahren" behandelt werden:



Bei „Schwierig" oder „Sehr schwer" kann das auf Dauer echt langwierig werden, daher auch der Zähler „DL" für die Durchläufe und die Möglichkeit zum Abbruch. Hier zeigt sich ganz deutlich der Unterschied zwischen PCs mit GHz-Takt und dieser „kleinen aber netten Schnecke".  ;)  Mit Sicherheit würde es auf einem Teensy 3.2 oder so ganz anders laufen. Aber das ist erst mal Zukunftsmusik. Mir ging es darum, das Programm in den 328P zu quetschen.

Okay, „mega super kniffelige" Sudokus kommen bei o.g. Verfahren nicht wirklich heraus. Was z.B. auf einigen „professionellen" Homepages aufgezeigt wird, ist m.E. manchmal sehr grenzwertig - vor allen Dingen, weil ja doch öfters mehrfache Lösungswege herauskommen! Und solche Rätsel mag ich irgendwie nicht. Entweder „eindeutig", oder besser gar nix. Gegenüber dem, was in den üblichen Printmedien abgedruckt wird, liefert mein Generator schon etwas anspruchsvolleres. Echte „Profis" mögen darüber vielleicht müde lächeln. Aber was solls? Der UNO kann nun auch Sudoku mit allem Zick und Zack. Und das ist - für mich - ganz okay so.

Noch etwas Technik:

Beim Start des Beitrages hatte ich noch von eigenen Classes für die Buttons, für das LCD-Display und für das EEPROM gesprochen. Das habe ich für den Generator noch um eine Class „TUsart" ergänzt: Die Standard-Befehle „Serial.begin()" und „Serial.print()" benötigten für mich viel zu viel Platz im RAM (173 Bytes für I/O-Buffer etc.). Hierzu habe ich das 660seitige Daten-„Blatt" weiter durchforstet und bin darauf gestoßen, wie man die serielle Schnittstelle „direkt" beschickt. Alles in allem konnte ich den RAM- und Flash-Verbrauch massiv reduzieren und habe die beiden notwendigen Befehle Serial.begin() und Serial.print() mit Minimal-Code nachgebaut. Alles zusammen ergibt das nun folgenden Compiler-Output in der IDE 1.6.9:

Der Sketch verwendet 19.378 Bytes (60%) des Programmspeicherplatzes. Das Maximum sind 32.256 Bytes.
Globale Variablen verwenden 260 Bytes (12%) des dynamischen Speichers,
1.788 Bytes für lokale Variablen verbleiben. Das Maximum sind 2.048 Bytes.

Bietet also noch einigen Raum für weitere „Highlights"...

Ein weiterer Schritt wird zunächst sein, die netten Antworten aus einem parallelen Beitrag bezüglich TFT-Displays in Augeschein zu nehmen. Ich habe ja noch ca. 13 kByte Flash „übrig". Das muss ich mir genauer ansehen wie ich mit den Dingern klar komme. Falls das nicht mehr passt, wandert das Teil mit LCD-Display auf eine Platine und kann in der besagten Hosentasche spazierengetragen werden...

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

Happy Programming,
und immer ein Bit in Reserve halten
RudiDL5

Title: Re: [Projekt] Sudoku Lösungsprogramm f. d. Jackentasche (Update)
Post by: michael_x on Aug 15, 2016, 09:35 am
Quote
Entweder „eindeutig", oder besser gar nix
Das ist vollkommen richtig. Ein Sudoku mit mehreren möglichen Lösungen (selbst wenn es nur 2 tauschbare Pärchen wären) ist keines.

Dein Karma hast du dir verdient! Dass Sudokus Erzeugen schwerer ist als Lösen, ist klar. Glückwunsch!

Ich kenne übrigens einen Sudoku-Generator, der darauf achtet, dass eine Ziffer gar nicht vorkommt.
Und "sehr schwer" nennt er nur solche, bei denen es tatsächlich gar nicht ohne Probieren geht. Wobei "kenne" leider der falsche Ausdruck ist, weil ich nicht weiss, wie der das hinkriegt. Hat vielleicht nur eine endliche Anzahl vordefinerte, die er nur umrührt, damit man es nicht wiedererkennt.
Title: Re: [Projekt] Sudoku Lösungsprogramm f. d. Jackentasche (Update)
Post by: HotSystems on Aug 15, 2016, 10:08 am
Irgendwie ist das ein "geiles" Teil.

Ich habe mich bisher noch nicht weiter mit "Sudoku" befasst, aber die ganzen Funktionen in den 328 reinzupressen ist schon beachtlich. Bin gespannt, was da noch kommt. ;)

Echt toll....
Title: Re: [Projekt] Sudoku Lösungsprogramm f. d. Jackentasche (Update)
Post by: RudiDL5 on Aug 15, 2016, 12:53 pm
Hallo zusammen,
vielen Dank wieder für Lob und Pünktchen  :)

Wie gesagt - ich habe noch ca. 13 kByte Platz im Flash, da ist also noch genügend Luft für diverse Zusätze. Ein wenig sparsam muss ich aber mit dem RAM umgehen: Beim Start des Programmes werden ca. 260 Byte verbraucht, durch den ersten Aufruf des Solvers belegen die dort notwendigen lokalen Variablen wiederum 205 Bytes. 465 in der Summe sind im ersten Moment nicht viel, doch falls es beim Lösen zu Rekursionen kommt, werden in jeder tiefer gelegenen Ebene weitere 205 Bytes angefordert. Bei einer Verschachtelung von 8 Ebenen ist dann das Ende der Fahnenstange erreicht. Daher habe ich auch die Speicherabfrage und den erzwungenem Rücksprung integriert, um den UNO vor „unkontrollierten Freiflügen" zu bewahren. Vielleicht könnte ich noch hier und da etwas einsparen, z.B. durch Ersetzen der Funktionen pinMode(), digitalWrite() und digitalRead() durch Inline-Assembler. Das wäre aber lediglich etwas fürs Flash. Das RAM kann ich dadurch wahrscheinlich nicht weiter schonen. Viel Ersparnis brachte aber das Ersetzen von Serial.begin() und .print() durch meinen Fund im Datenblatt. Durch die „feste" Einstellung auf 10 Bytes im Buffer sehr „unflexibel", aber fürs Sudoku-Projekt ideal angepasst:

Code: [Select]


// --------------------------------------------
// Class TUsart
//

class TUsart
{
  public:
    void Init();                              //  Iniialisiert die Schnittstelle
    void WriteChr( char );                    //  Sendet ein einzelnes Byte
    void WriteStr( const char* );             //  Sendet eine 0-terminierte Zeichenkette
};

void TUsart::WriteChr( char CH )
{
  while( !( UCSR0A & (1<<UDRE0)) ) {}         //  Wartet auf leeren Buffer
  UDR0 = CH;                                  //  Sendet 1 Byte
}

void TUsart::WriteStr( const char* TX )
{
  unsigned char bu[10] = {0};                 //  Bufferlänge, wird anschließend wieder freigegeben
  memcpy_P( bu, TX, 10 );                     //  Zu sendender Text im Flash (max. 10 Bytes je Durchgang)
                                             
  for( byte n = 0; n < 10; n++ )              //  Buffer-Inhalt senden
     if( bu[n] != 0 )                         //  Bei 0 = Ende
       WriteChr( bu[n] );
     else
       break;
}

void TUsart::Init()                           //  Aus dem Datenblatt abgekupfert...
{
  // #define FOSC 16000000
  // #define BAUD 9600
  // #define MYUBRR FOSC/16/BAUD-1
  // Set baud rate to 9600 Baud, 8 DataBits, 1 StoppBit   
 
  word ubrr = 105;                            //  105 > MYUBRR > FOSC/16/BAUD-1 > 16000000/16/9600 -1;
                                              //  (Direkter Wert, spart Rechenzeit)
  UBRR0H = (unsigned char)( ubrr >> 8 );
  UBRR0L = (unsigned char)ubrr;
  UCSR0B = ( 1 << RXEN0 ) | ( 1 << TXEN0 );   //  Enable receiver and transmitter
  UCSR0C = ( 1 << USBS0 ) | ( 3 << UCSZ00 );  //  Set frame format: 8data, 1stopbit
}


@Michael_x
Deine Aussage bringt mich auf eine Idee: Der „Solver" kann ja auch „am Ende seiner Logik" auf genau dieses „Raten" zugreifen! Heisst: Er setzt eine (erlaubte) Ziffer ein und versucht sich erneut an einer Lösung. Bringt das nichts, wird die nächste (erlaubte) Ziffer genommen. Hierdurch kommt es zu den oben beschriebenen Rekursionen. Nun habe ich aber intern eine (komprimierte) Abstreichliste: Dort ist hinterlegt, welche Ziffern gemäß Regeln noch gesetzt werden dürfen... Was also wäre, wenn ich irgendwo eine „beliebige" Ziffer lösche und das Feld nach einer z.B. 2stelligen Abstreichliste absuche? Ist so eine Gruppe vorhanden, kann ich ja wieder versuchen, ob ich in der ersten Rekursions-Ebene zu einer eindeutigen Lösung komme... Ich werde bei Gelegenheit (zunächst in Delphi, geht dort schneller) prüfen, ob hierdurch auch noch „eindeutige" Lösungen möglich sind. Falls nicht müsste eine andere Idee herhalten.

@HotSystems
Na ja, mein Vorteil hierbei war ja, dass der Generator als solches gar nicht so groß war. Lediglich ca. 4 kByte zusätzlich zu den ursprüngliche ca. 15 kByte für den Solver. Im Generator wird „Rekursion" kurzfristig aus- und später wieder eingeschaltet. Außerdem konnte ich im Generator auf einige Funktionen und auf alle „Class-Globalen" Variablen des Solvers zurückgreifen. Ich war selbst überrascht, wie wenig Platz das alles benötigte. Mal sehen wie es später mit einem TFT zusammenspielt. Damit habe ich noch null Erfahrung. Ich träume (spinne?) noch davon, dem „Kleinen" beizubringen wie man Schach spielt, vielleicht mit ausführlichen Eröffnungs-Bibliotheken aus einem externem EEPROM oder so... ;-)

Bis denne
Rudi