Algorithmus zum Finden aller Wörter bei "Boggle" - Verbesserungsvorschläge?

[walker]

Schönen Tag miteinander, liebe C++-Freunde!

Ich war jetzt bestimmt seit mindestens 2 Jahren nicht mehr hier und habe vor wenigen Tagen das erste mal seit langem wieder einen C++-Compiler angerührt, was für ein Gefühl! Wie es dazu kam? Nun, ich habe mit einem Freund das uralte Denkspiel "Boggle" im Keller ausgegraben und eine Weile gespielt, nach einer Weile wurde es uns zu langweilig und er meinte plötzlich: "Hey, in dieser Kombination steckt bestimmt ein langes Wort drin, wir sehen es nur nicht -- lass uns doch ein Programm schreiben, das einem alle Lösungsworte ausspuckt!"
Gut - gesagt, getan. Da unser Informatik-Studium ohnehin in ~2 Monaten beginnt dürfte das schon mal eine gute, herausfordernde Übung sein.

Zur Erklärung für diejenigen unter euch die denen das Spiel nicht bekannt ist: Das "Spielfeld" besteht aus einem 4x4-Raster in dem sich Buchstabenwürfel befinden. Durch Schütteln erscheint jeweils eine neue Kombination von Buchstaben und die Aufgabe der Spieler ist es, möglichst schnell möglichst viele Wörter daraus zu bilden. Je länger die Wörter, desto mehr Punkte gibt es.
Wichtig ist dabei, dass der selbe Würfel in einem Wort nicht öfters verwendet werden darf.
So schaut das Feld z.B. aus: http://www.t-hunts.com/yaba5/images/boggle_9.gif

... Nachdem wir zunächst mal festgestellt haben, dass es nicht sonderlich intelligent ist, einfach draufloszuschreiben, ohne irgendeine Ahnung zu haben, wie denn der Algorithmus aussehen soll, haben wir uns hingesetzt und mit Bleistift und Papier überlegt, wie sowas am besten anzupacken ist.

Folgende Lösung, die Rekursion benutzt (anders geht es wohl kaum):
[word bezeichnet das Wort, das der aktuelle Buchstabenpfad ergibt
pdic ist der Wörterbuchzeiger]
[] 1. pdic zu erstem Wort hinzeigen lassen, das mit word beginnt
[] 2. Keines gefunden? -> Abbrechen! (return;)
[*] 3. pdic == word? -> Wenn ja, der Liste der gefundenen Wörter hinzufügen!
[] 4. alle umgebenden Buchstaben ermitteln und die Funktion für jeden einzelnen wieder selbst aufrufen

Klingt jetzt vl etwas kompliziert, aber hier mal die Links zum Code:
http://rafb.net/p/1Om5eM50.html - Voggle.h
http://rafb.net/p/d1bqIM17.html - Voggle.cpp

Ich hoffe der Code ist soweit verständlich, wenn nicht, dann fragt einfach.
Ich bin mir sicher, dass hier noch sehr viel optimiert werden kann!

Schöne Grüße,
walker

[frage..]

Woher habt ihr die Wörter zum Vergleichen?

[Jester]

Hast Du auch ne Frage?

Ich hab jedenfalls eine: Kann man die Wörter beliebig bilden? Euer Ansatz sieht irgendwie so aus, als müsse das Wort einen Pfad im 4x4-Block bilden. Davon steht aber in der Aufgabenstellung nichts.

[BerndD]

Eine extreme Optimierungsmöglichkeit fällt mir sofort ein:
Das Wörterbuch sollte nicht direkt benutzt werden, sonder ein daraus erzeugten Deterministischer endlicher Automat (DEA). Spätestens wenn euer Wörterbuch tausende Wörter beinhaltet ist eine direkte Verwendung nicht mehr sinnvoll durchführbar.

Ich wünsche euch viel Spaß beim programmieren!

[walker]

frage.. schrieb:

Woher habt ihr die Wörter zum Vergleichen?

Wir haben folgendes Paket unter Debian/Ubuntu installiert und die Dictionary-Datei einfach eingelesen, wie man ja am Beginn der main()-Funktion sieht;

wngerman - New German orthography wordlist

Jester schrieb:

Hast Du auch ne Frage?

Sorry... die Frage stand eher im Threadtitel -> "Verbesserungsvorschläge?"
Das Programm funktioniert nämlich ohne Probleme und findet alle Wörter, nur habe ich das Gefühl dass das noch viel viel schneller gehen kann (was hätte man denn da früher nur gemacht, mit einem Zehntel der jetzigen Rechenleistung? ). Auf einem ~1,5GHz Prozessor benötigt es durchschnittlich zwischen 1 und 2 Minuten, um alle Ergebnisse zu berechnen.
Eine simple Optimierung war es, als Container für die Wörterbuchdateien list statt vector zu verwenden, hat schon einiges gebracht.
Aber die Experten unter euch haben sicher noch bessere Vorschläge auf Lager, nicht?

Jester schrieb:

Ich hab jedenfalls eine: Kann man die Wörter beliebig bilden? Euer Ansatz sieht irgendwie so aus, als müsse das Wort einen Pfad im 4x4-Block bilden. Davon steht aber in der Aufgabenstellung nichts.

Hast recht, habe ich bei der Spielbeschreibung vergessen; ja, die verwendeten Buchstabenwürfel müssen jeweils zusammenhängen!

BerndD schrieb:

Das Wörterbuch sollte nicht direkt benutzt werden, sonder ein daraus erzeugten Deterministischer endlicher Automat (DEA).

Klingt schon mal interessant, werd mal schaun ob ich Informationen hierfür finde, vielen Dank.

Schöne Grüße,
walker

[mad_martin]

Falls du Besitzer eines Mehrkernprozessors bist, könntest du dir mal überlegen, das Programm zu parallelisieren. Backtracking lässt sich ja relativ einfach auf mehrere Ausführungseinheiten verteilen.

Auf einem System mit mehreren Kernen und/oder CPUs könntest du damit viel Geschwindigkeit holen.

gruß
Martin