Go Down

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

RudiDL5

@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

ElEspanol

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


michael_x

Der MeerschweinchenKöttel-Roboter 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.

RudiDL5

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

Doc_Arduino

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.


Tschau
Doc Arduino '\0'

Messschieber auslesen: http://forum.arduino.cc/index.php?topic=273445
EA-DOGM Display - Demos: http://forum.arduino.cc/index.php?topic=378279

RudiDL5

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

michael_x

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 ;) )

agmue

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 ...
Die Vorstellungskraft ist wichtiger als Wissen, denn Wissen ist begrenzt. (Albert Einstein)

RudiDL5

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"


2. Beim Generator kann man 5 Stufen wählen, vom „1 - Sehr leicht" bis „5 - Sehr schwer"


3. Nach dem Start kann man die Berechnung zur Not abbrechen (wenn es zuuu lange dauert)


4. Fertigmeldung, zeigt die Anzahl der Durchläufe die evtl. notwendig wurden


5. Nach „Okay" springt er direkt in die Eingabe-Maske zum Begutachten


6. 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


michael_x

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.

HotSystems

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....
Gruß Dieter

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

RudiDL5

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

Go Up