DLX aka Dancing Links / Algorithm X

[Meflin]

Moin!

Ich bin derzeit auf der Suche nach erklärendem Material für den DLX (Dancing Links) Algorithmus und Knuth's Algorithm X (dass man mit DEM Namen berühmt werden kann :8 )

Zwar gibt es für beide einen englischsprachigen Wikipediaartikel (und zwar hier und hier), aus denen werde ich aber nicht so gaaaanz schlau, die weiterführenden Links bei Wikipedia sind auch sehr dürftig und die deutsche Version kann man vergessen.

Auch Google habe ich natürlich bemüht - ausser 2 C++ Templates war aber auch hier nichts brauchbares zu finden, und die Templates helfen mir allein in keinster Weise das ganze irgendwie zu verstehen.

Umsetzen will ich das ganze in Delphi, also wären darauf bezogene Quellen natürlich Top, aber ich wäre schon mit irgendetwas zufrieden :?

Wenn also jemand was dazu haben sollte, lasst es mir zukommen :)

[alzaimar]

Zitat:

Zitat von Meflin

... für den DLX (Dancing Links) Algorithmus und Knuth's Algorithm X (dass man mit DEM Namen berühmt werden kann :8 )

Was meinst Du denn damit? "X" oder "Knuth"?

Und die Wikipedia-Artikel sind doch ganz gut erklärt. Knuth's Algorithm X beschreibt, wie man die Lösung zu dem 1-Matrix Problem findet und die DLX-Seite (Sudoku, darum gehts Dir, oder?) beschreibt, wie man das Sudoku-Problem auf diese 1-Matrizen abbildet.

Und wenn man dem 'C++' Link folgt, bekommst du doch schon den Code auf dem silbernen Tablett. Nur noch in Delphi übersetzen. Das kann doch nicht so schwer sein, oder?

[Meflin]

Zitat:

Zitat von alzaimar

Was meinst Du denn damit? "X" oder "Knuth"?

Ich meinte Knuth :mrgreen:

Zitat:

Und die Wikipedia-Artikel sind doch ganz gut erklärt. Knuth's Algorithm X beschreibt, wie man die Lösung zu dem 1-Matrix Problem findet und die DLX-Seite (Sudoku, darum gehts Dir, oder?) beschreibt, wie man das Sudoku-Problem auf diese 1-Matrizen abbildet.

Jau, habe das ganze für meine Sudoku Komponente ins Auge gefasst. Mag sein dass sie gut beschireben sind, ich blicke jedenfalls nicht ganz durch, obs an meinen mathematischen oder meinen Englischfähigkeiten scheitert weis ich auch nciht so genau, vermutlich an beidem.

Zitat:

Und wenn man dem 'C++' Link folgt, bekommst du doch schon den Code auf dem silbernen Tablett. Nur noch in Delphi übersetzen. Das kann doch nicht so schwer sein, oder?

Da werde ich mich wohl mal dann dranmachen, ohne es zu kapieren, was mich nur abschreckte war die Template Form - mehr als die basischen Syntaxelemente von C++ beherrsche ich nicht, weswegen das etwas verwirrend ist, aber gut, ich kann ja hier dann wieder nachfragen ;)

[Boombuler]

Achja das deutsche Wiki bietet noch folgendes:
http://de.wikipedia.org/wiki/Algorit...h-Morris-Pratt

Greetz
Boombuler

[toms]

Schaue auch mal hier:

http://www.codeproject.com/useritems/XSudokuWnd.asp
http://www.contrib.andrew.cmu.edu/~a...ippets/dance.c

[alzaimar]

Zitat:

Zitat von Meflin

Zitat:

Zitat von alzaimar

Was meinst Du denn damit? "X" oder "Knuth"?

Ich meinte Knuth :mrgreen:

Namen sind Schall und Rauch.

Zitat:

Zitat von Boombuler

Achja das deutsche Wiki bietet noch folgendes:
http://de.wikipedia.org/wiki/Algorit...h-Morris-Pratt

Das hat ja nun nur mit der Tatsache zu tun, das Donald E. Knuth die Koryphäe, der IT-Pabst, der Algorithmik-Gott schlechthin ist. Muhäää: Spottet nicht über ihnEr hat unter Anderem die bahnbrechenden und wegweisenden Informatik-Bibeln ("The Art of Computer Programming") geschrieben, das TeX- und Metafont-System entwickelt, ein System zur Erzeugung von Programm und Dokumentation aus einem Sourcecode (Tangle&Weave) und sich dann noch nebenbei erfolgreich an diversen Problemen. Das nur mal so nebenbei.

Knuth dürfte neben dem KMP-Algorithmus auch bei dem einen oder anderen Wiki-Artikel auftauchen :zwinker:

Na ja, bei Sudoku kommt man doch auch anders und viel einfacher ans Ziel. Suche mal hier oder um Delphi-Forum. Es gibt ettliche Lösungsansätze und Ideen, wie man das hinbekommt.