Hallöle,
hier mal ein Update zu meinem Projekt:
Auch wenn es in den Kommentaren zu eingem Schmunzeln kam, speziell die Aussage
„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“ 
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.
-
Das Programm wurde um 2 Punkte ergänzt: „Serieller Monitor“ + „Sudoku-Generator“
-
Beim Generator kann man 5 Stufen wählen, vom „1 - Sehr leicht“ bis „5 - Sehr schwer“
-
Nach dem Start kann man die Berechnung zur Not abbrechen (wenn es zuuu lange dauert)
-
Fertigmeldung, zeigt die Anzahl der Durchläufe die evtl. notwendig wurden
-
Nach „Okay“ springt er direkt in die Eingabe-Maske zum Begutachten
-
Da die Eingabe etwas anstrengend ist kann man das auch auf den seriellen Monitor übertragen
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:
- „Sehr leicht“: Es werden in jedem Block 2-4 Ziffern per Zufall gelöscht. Jede Löschung wird geprüft und ggf. zurückgenommen.
- „Leicht“: Es werden in jedem Block 4-6 Ziffern per Zufall gelöscht. Jede Löschung wird wieder geprüft.
- „Mittel“: Es werden in jedem Block 3-5 Ziffern gelöscht. Anschließend werden von den verbleibenden Ziffern maximal 8 Ziffern ebenfalls gelöscht, die gemäß Regeln der Eindeutigkeit noch entfernt werden dürfen. Es bleiben in diesem Fall zwischen 20 und 30 Ziffern übrig
- „Schwierig“: Verfahren wie „Mittel“, jedoch dadurch ergänzt, dass 1. „alle“ möglichen Ziffern gelöscht werden, UND bei der Lösung mindestens 1x „Regel 2“ oder 1x „Regel 3“ Anwendung finden MUSS. (Siehe hierzu die Erklärungen zu Beginn dieses Beitrages auf Seite 1, „Teil 2“) Dieses führt dazu, dass manche „gültigen“ Rätsel dennoch verworfen werden. Das ganze dauert dann schon mal etwas mehr als ca. „eine Zigarettenlänge“...
- „Sehr Schwer“: Verfahren wie „Mittel“, jedoch mit der Ergänzung, dass BEIDE „Sonder-Regeln 2 und 3“ vorhanden sein müssen. Wie bei „Schwer“ dauert dieser Vorgang auf dem „Kleinen“ jedoch dann schon mal einige Minuten. Ich hatte mal einen Zyklus von etwas über 10 Minuten (geschätzt).
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