Eine Solver-Implementierung für das klassische Boggle-Wortspiel! Haben Sie schon einmal an einem intensiven Boggle-Spiel teilgenommen und gedacht, Sie hätten alle möglichen Wörter auf dem Brett ausgeschöpft? Denken Sie nicht mehr darüber nach!
Mit einer Wörterbuchdatei Ihrer Wahl und einem Board mit benutzerdefinierten Abmessungen haben Sie im Handumdrehen alle englischen Wörter, die auf Ihrem Boggle-Board vorhanden sind! (Auf meinem Computer läuft der Algorithmus in < 3 Sekunden auf einer 50x50-Karte!!) Wenn Sie ein anderes Wörterbuch als das von mir bereitgestellte verwenden möchten, ist das kein Problem – stellen Sie einfach sicher, dass jedes Wort durch einen Zeilenumbruch getrennt ist.
Sobald Sie zum Stammverzeichnis des Projekts navigiert sind, verwenden Sie die folgenden Befehle im Terminal:
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Vorausgesetzt, die Datei Boggle.java wurde nicht geändert, findet dieses Programm alle Wörter, die in der folgenden Tafel enthalten sind:
Solving:
a r m
b e s
n i m
arsine
rabies
bismer
bersim
barmen
miners
minbar
abime
abies
abner
resin
bines
bisme
biers
benim
besin
besra
berms
bears
bearm
braes
barse
bares
barms
smear
serab
smear
nears
inerm
mines
miner
miser
arse
aren
ares
arms
rems
reim
rein
reis
rems
rabi
mems
mein
mear
mrem
bine
bise
bien
bier
beni
berm
bear
brei
bren
bars
bare
barm
ears
sime
sine
sier
semi
serb
sera
sear
nims
nies
near
inbe
mise
mien
mems
mear
aes
aer
abn
abr
ars
are
arb
arm
rem
rei
ren
res
reb
rem
rea
rms
rab
mem
men
mer
mea
mrs
bim
bin
bis
ben
bes
ber
bra
bae
bar
ems
ems
ers
era
ear
sim
sin
sie
sib
sem
sei
sen
sem
ser
sea
nim
nis
nib
nei
neb
nea
ism
ise
ism
iba
min
mis
mib
men
mem
mer
mea
Wie Sie sich vorstellen können, wäre es eine ziemlich mühsame Aufgabe, in einem Wörterbuch nachzuschlagen, um zu überprüfen, ob jede einzelne mögliche Buchstabenfolge ein englisches Wort ist. Es stellt sich heraus, dass es für jedes Board der Größe nxn ein Maximum von n^2 x (n^2) gibt! mögliche Buchstabenfolgen, die auf Gültigkeit überprüft werden müssen. Dies geht eindeutig sehr schnell kaputt – ein einfaches 3 x 3- Board erfordert höchstens 3265920 Validierungen, und das ist nicht einmal die Größe eines echten Boggle-Boards! Wie habe ich es also gemacht? Ich meine, selbst das Lösen eines 8 x 8- Boards würde maximal etwa 10^90 Berechnungen erfordern! Ich muss hier etwas wirklich Schlaues gemacht haben. Es stellt sich heraus, dass es einen unglaublich effizienteren Ansatz gibt. Der Kern des Lösungsalgorithmus dreht sich um eine bestimmte Datenstruktur, die als Trie bezeichnet wird. Bei einer gegebenen Zeichenfolge der Länge n kann uns ein Trie sagen, ob die gesuchte Zeichenfolge in O(n) (linearer) Zeit in unserem Wörterbuch vorhanden ist oder nicht! Dies ist eine enorme Verbesserung gegenüber der Durchführung einer binären Suche nach jedem möglichen Wort in der Wörterbuchdatei. Tatsächlich kann ein Trie prüfen, ob das Hinzufügen eines Buchstabens zu einer vorhandenen Zeichenfolge in konstanter Zeit zu einem anderen gültigen Wort führt! Das macht den Algorithmus so schnell, wie er ist: Wir führen eine Tiefensuche für jeden Buchstaben auf der Tafel durch, fügen dem aktuellen Wort, das wir gebildet haben, einen angrenzenden Buchstaben hinzu und hängen ihn an unsere Ergebnisse an, wenn darin ein Wort enthalten ist in unserem Wörterbuch. Wenn wir irgendwann eine Zeichenfolge erreichen, die kein Präfix eines anderen Wortes ist, kehren wir zum nächstgelegenen gültigen Präfix zurück und fahren fort. Ziemlich cooles Zeug!
Die Laufzeiteffizienz hat jedoch ihren Preis. Die von mir verwendete Wörterbuchdatei umfasst ungefähr 5 Megabyte Text, daher ist der Platzbedarf für die Zusammenstellung jedes Wortes in einem Wörterbuch-Trie ziemlich enorm. Das Erstellen eines Versuchs aus dem Wörterbuch dauert mit einer durchschnittlichen Ausführungsgeschwindigkeit von ca. 2,2 Sekunden auf meinem Computer tatsächlich am längsten. Wenn wir es positiv betrachten, erfordert die Erstellung des Wörterbuchs Trie konstante Zeit und Raum in Bezug auf die Dimensionen der Tafel, die wir lösen. Daraus folgt, dass das einzige Problem die Laufzeit unseres Lösungsalgorithmus ist, der sich bei der Lösung von Brettern mit Abmessungen von bis zu 50 x 50 in weniger als 3 Sekunden als effizient erwiesen hat. Wenn Sie sich für die extremen Grenzen interessieren: Der Algorithmus brauchte auf meinem System etwa 77 Sekunden, um Lösungen für ein 250 x 250- Board zu finden.
