Wie man eine Liste möglicher Wörter aus einer Buchstabenmatrix findet [Boggle Solver]

Question

In letzter Zeit habe ich auf meinem iPhone ein Spiel namens Scramble gespielt. Einige von euch kennen dieses Spiel vielleicht als Boggle. Wenn das Spiel beginnt, erhält man im Wesentlichen eine Matrix von Buchstaben, etwa so:

F X I E
A M L O
E W B X
A S T U

Das Ziel des Spiels ist es, so viele Wörter wie möglich zu finden, die durch Aneinanderreihen von Buchstaben gebildet werden können. Sie können mit einem beliebigen Buchstaben beginnen, und alle Buchstaben, die ihn umgeben, sind Freiwild, und sobald Sie zum nächsten Buchstaben weitergehen, sind alle Buchstaben, die diesen Buchstaben umgeben, Freiwild, mit Ausnahme der bereits verwendeten Buchstaben . In dem obigen Raster könnte ich zum Beispiel die folgenden Wörter finden LOB , TUX , SEA , FAME , usw. Die Wörter müssen aus mindestens 3 Zeichen bestehen und dürfen nicht mehr als NxN Zeichen haben, was in diesem Spiel 16 Zeichen sind, aber in einigen Implementierungen variieren können. Obwohl dieses Spiel Spaß macht und süchtig macht, bin ich offensichtlich nicht sehr gut darin und wollte ein wenig schummeln, indem ich ein Programm erstellte, das mir die bestmöglichen Wörter liefert (je länger das Wort ist, desto mehr Punkte erhält man).

_{(Quelle: <a href="http://www.boggled.org/sample.gif" rel="noreferrer">verblüfft.org </a>)}

Leider kenne ich mich mit Algorithmen, ihrer Effizienz usw. nicht besonders gut aus. Mein erster Versuch verwendet ein Wörterbuch wie zum Beispiel dieses (~2.3MB) und führt eine lineare Suche durch, um Kombinationen mit Wörterbucheinträgen zu finden. Dies dauert eine よほど lange Zeit, um die möglichen Wörter zu finden, und da man nur 2 Minuten pro Runde hat, ist das einfach nicht ausreichend.

Ich bin gespannt, ob Stackoverflowers effizientere Lösungen anbieten können. Ich bin vor allem auf der Suche nach Lösungen mit den Big 3 Ps: Python, PHP und Perl, obwohl alles mit Java oder C++ auch cool ist, da Geschwindigkeit entscheidend ist.

AKTUELLE LÖSUNGEN :

• Adam Rosenfield, Python, ~20s
• John Fouhy, Python, ~3s
• Kent Fredric, Perl, ~1s
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET, ~1s
• Paolo Bergantino, PHP (Live-Link) , ~5s (~2s lokal)

Answer 1

Ich habe 3 Monate damit verbracht, an einer Lösung für das Problem der 10 besten punktedichten 5x5 Boggle-Spielfelder zu arbeiten.

Das Problem ist nun gelöst und auf 5 Webseiten vollständig offengelegt. Bei Fragen kontaktieren Sie mich bitte.

Der Algorithmus für die Board-Analyse verwendet einen expliziten Stapel, um die Board-Quadrate pseudo-rekursiv durch einen gerichteten azyklischen Wortgraphen mit direkten Kindinformationen und einem Zeitstempel-Tracking-Mechanismus zu durchlaufen. Dies könnte sehr gut die weltweit fortschrittlichste lexikalische Datenstruktur sein.

Das Schema bewertet etwa 10.000 sehr gute Boards pro Sekunde auf einem Quad-Core. (9500+ Punkte)

Eltern-Webseite:

DeepSearch.c - http://www.pathcom.com/~vadco/deep.html

Komponenten-Webseiten:

Optimale Scoretabelle - http://www.pathcom.com/~vadco/binary.html

Fortgeschrittene Lexikonstruktur - http://www.pathcom.com/~vadco/adtdawg.html

Board-Analyse-Algorithmus - http://www.pathcom.com/~vadco/guns.html

Parallele Batch-Verarbeitung - http://www.pathcom.com/~vadco/parallel.html

- Dies umfassende Werk wird nur eine Person interessieren, die nur das Beste verlangt.

Answer 2

Ich schlage vor, einen Buchstabenbaum basierend auf Wörtern zu erstellen. Der Baum würde aus Buchstabenstrukturen wie folgt bestehen:

Buchstabe: char
isWord: boolean

Dann bauen Sie den Baum auf, wobei jeder Tiefe ein neuer Buchstabe hinzugefügt wird. Mit anderen Worten, auf der ersten Ebene gäbe es das Alphabet; dann von jedem dieser Bäume gäbe es weitere 26 Einträge, und so weiter, bis alle Wörter buchstabiert sind. Behalten Sie diesen analysierten Baum bei und es wird schneller möglich sein, alle möglichen Antworten nachzuschlagen.

Mit diesem analysierten Baum können Sie sehr schnell Lösungen finden. Hier ist der Pseudo-Code:

ANFANG: 
    Für jeden Buchstaben:
        Wenn die das aktuelle Level repräsentierende Struktur isWord == true hat, tragen Sie es als Antwort ein.
        Gehen Sie alle Nachbarn durch; wenn ein Kind des aktuellen Knotens dem Buchstaben entspricht, rufen Sie rekursiv BEGIN darauf auf.

Dies könnte mit etwas dynamischer Programmierung beschleunigt werden. Zum Beispiel sind in Ihrem Beispiel beide "A" sowohl neben einem "E" als auch einem "W", was (von dem Punkt aus, an dem sie sie treffen) identisch wäre. Ich habe nicht genug Zeit, um den Code dafür wirklich auszuarbeiten, aber ich denke, Sie können die Idee erfassen.

Außerdem bin ich sicher, dass Sie andere Lösungen finden werden, wenn Sie nach "Boggle Solver" googeln.

Answer 3

Zunächst lesen, wie einer der C#-Sprachdesigner ein ähnliches Problem gelöst hat: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx.

Wie er kannst du mit einem Wörterbuch beginnen und die Wörter kanonisieren, indem du ein Wörterbuch aus einem alphabetisch sortierten Array von Buchstaben zu einer Liste von Wörtern erstellst, die aus diesen Buchstaben gebildet werden können.

Dann fange an, mögliche Wörter aus dem Board zu erstellen und sie nachzuschlagen. Ich vermute, das bringt dich ziemlich weit, aber es gibt sicherlich noch weitere Tricks, die die Dinge beschleunigen könnten.

Answer 4

Ich müsste mir eine vollständige Lösung noch einmal durch den Kopf gehen lassen, aber als praktische Optimierung frage ich mich, ob es sich lohnen könnte, eine Tabelle mit Häufigkeiten von Digrammen und Trigrammen (Kombinationen aus 2 und 3 Buchstaben) basierend auf allen Wörtern aus Ihrem Wörterbuch vorzubereiten und diese für die Priorisierung Ihrer Suche zu verwenden. Ich würde mit den Anfangsbuchstaben der Wörter gehen. Wenn Ihr Wörterbuch also die Wörter "Indien", "Wasser", "Extrem" und "Außergewöhnlich" enthielte, dann könnte Ihre vorab berechnete Tabelle folgendermaßen aussehen:

'IN': 1
'WA': 1
'EX': 2

Dann suchen Sie diese Digramme in der Reihenfolge der Häufigkeit (zuerst EX, dann WA/IN)

Answer 5

Nur zum Spaß habe ich einen in Bash implementiert. Es ist nicht super schnell, aber vernünftig.

http://dev.xkyle.com/bashboggle/