25.8.2006

Logisch, oder?

Posted in Theory at 11:10 by Rafayel

Ich habe ja mehrere Fimmel. Zum Beispiel suche ich ausgefallene Wege, um Sudokus per Computer zu loesen. Und gestern konnte ich meine Sammlung wieder um eine neue Variante erweitern.

Schonmal was von constraint satisfaction problems (CSP) gehoert? Wahrscheinlich nicht. Dabei kennt eigentlicher jeder welche und hat sie vielleicht auch schon geloest. Gegeben sei ein Logikraetsel, bei dem Frau A neben der Dame mit dem Hund wohnt, B keine Pilze im Garten anbaut und die Frau mit dem Spinat sich regelmaessig ueber die Katze ihrere Nachbarin aufregt. Und nun soll man herausfinden, welches Haustier Frau D hat und wo die Dame mit den Gurken wohnt, oder so.

Das z.B. sind CSPs. Und wie man sich leicht ueberlegen kann, lassen sich auch Sudokuprobleme aehnlich formulieren.

Richtig interessant wird es erst, wenn man zum Loesen des CSPs ein Computer-Algebra-System (CAS) wie Maple benutzt, wobei ich – wenn man mich fragen wuerde – die Bezeichnung computer aided mathematics (CAM) als passender betrachten wuerde. Denn damit kann man vom 1×1 bis zum Beweis eines der sieben Millennium-Probleme so ziemlich alles berechnen. Maple laesst sich seit einigen Versionen ueber die Schnittstelle OpenMaple auch in eigene Programme einbinden. Und dank der umfangreichen Faehigkeiten von Maple laedt das foermlich zum Spielen ein.

Ich habe vor, mein Sudoku-Solver pms um eine Anbindung an Maple zu ergaenzen und darueber das Sudoku – formuliert als CSP – zu loesen. Das ist zwar extrem umstaendlich, aber irgendwie auch wieder stylisch. Finde ich.

Alle, die an der Formulierung von Sudoku als CSP interessiert sind, gedulden sich bitte noch ein wenig. Da ich pms als Open Source freigebe, wird, sobald ich mit der Integration fertig bin, natuerlich auch der Maple-Teil verfuegbar sein. Eine Loesung direkt als Maple-Worksheet existiert schon, es fehlen nur ein paar Klassen zur Ergaenzung von pms.

[Nachtrag]
Damit man sich besser ein Bild davon machen kann, hier eine Beispielrechnung: Sudoku als constraint satisfaction problem in Maple.

Permalink Trackback