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

Diese Lösung gibt auch die Richtung vor, in der auf dem angegebenen Spielfeld gesucht werden soll

Algorithmus:

1. Verwendet Trie, um alle Wörter im Englischen zu speichern und die Suche zu beschleunigen
2. Verwendet DFS, um die Wörter im Boggle zu suchen

Ausgabe:

Found "pic" Richtungen von (4,0)(p) aus   
Found "pick" Richtungen von (4,0)(p) aus   
Found "pickman" Richtungen von (4,0)(p) aus   
Found "picket" Richtungen von (4,0)(p) aus   
Found "picked" Richtungen von (4,0)(p) aus   
Found "pickle" Richtungen von (4,0)(p) aus   

Code:

from collections import defaultdict
from nltk.corpus import words
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize

english_words = words.words()

# Wenn Sie Stoppwörter entfernen möchten
# stop_words = set(stopwords.words('english'))
# english_words = [w for w in english_words if w not in stop_words]

boggle = [
    ['c', 'n', 't', 's', 's'],
    ['d', 'a', 't', 'i', 'n'],
    ['o', 'o', 'm', 'e', 'l'],
    ['s', 'i', 'k', 'n', 'd'],
    ['p', 'i', 'c', 'l', 'e']
]

# Anstelle von X- und Y-Koordinaten
# verwenden Sie besser Zeile und Spalte
lenc = len(boggle[0])
lenr = len(boggle)

# Initialisieren Sie die Trie-Datenstruktur
trie_node = {'valid': False, 'next': {}}

# ermitteln Sie die Abstände, um alle Nachbarn zu finden
neighbors_delta = [
    (-1,-1, ""),
    (-1, 0, ""),
    (-1, 1, ""),
    (0, -1, ""),
    (0,  1, ""),
    (1, -1, ""),
    (1,  0, ""),
    (1,  1, ""),
]

def gen_trie(word, node):
    """Aktualisiert die Trie-Datenstruktur mit dem übergebenen Wort"""
    if not word:
        return

    if word[0] not in node:
        node[word[0]] = {'valid': len(word) == 1, 'next': {}}

    # rekursiv Trie aufbauen
    gen_trie(word[1:], node[word[0]])

def build_trie(words, trie):
    """Erstellt die Trie-Datenstruktur aus der Liste der Wörter"""
    for word in words:
        gen_trie(word, trie)
    return trie

def get_neighbors(r, c):
    """Gibt die Nachbarn für die angegebenen Koordinaten zurück"""
    n = []
    for neigh in neighbors_delta:
        new_r = r + neigh[0]
        new_c = c + neigh[1]

        if (new_r >= lenr) or (new_c >= lenc) or (new_r < 0) or (new_c < 0):
            continue
        n.append((new_r, new_c, neigh[2]))
    return n

def dfs(r, c, visited, trie, now_word, direction):
    """Durchsucht den Graphen mit DFS"""
    if (r, c) in visited:
        return

    letter = boggle[r][c]
    visited.append((r, c))

    if letter in trie:
        now_word += letter

        if trie[letter]['valid']:
            print('Found "{}" {}'.format(now_word, direction))

        neighbors = get_neighbors(r, c)
        for n in neighbors:
            dfs(n[0], n[1], visited[::], trie[letter], now_word, direction + " " + n[2])

def main(trie_node):
    """Startet die Suche nach Wörtern im Boggle"""
    trie_node = build_trie(english_words, trie_node)

    # Drucken Sie das Spielfeld
    print("Gegebenes Feld")
    for i in range(lenr):print (boggle[i])
    print ('\n')

    for r in range(lenr):
        for c in range(lenc):
            letter = boggle[r][c]
            dfs(r, c, [], trie_node, '', 'Richtungen von ({},{})({}) aus '.format(r, c, letter))

if __name__ == '__main__':
    main(trie_node)

Answer 2

Ein Node.JS JavaScript-Lösungsansatz. Berechnet alle 100 eindeutigen Wörter in weniger als einer Sekunde, einschließlich dem Lesen der Wörterdatei (MBA 2012).

Ausgabe:
["FAM","TUX","TUB","FAE","ELI","ELM","ELB","TWA","TWA","SAW","AMI","SWA","SWA","AME","SEA","SEW","AES","AWL","AWE","SEA","AWA","MIX","MIL","AST","ASE","MAX","MAE","MAW","MEW","AWE","MES","AWL","LIE","LIM","AWA","AES","BUT","BLO","WAS","WAE","WEA","LEI","LEO","LOB","LOX","WEM","OIL","OLM","WEA","WAE","WAX","WAF","MILO","EAST","WAME","TWAS","TWAE","EMIL","WEAM","OIME","AXIL","WEST","TWAE","LIMB","WASE","WAST","BLEO","STUB","BOIL","BOLE","LIME","SAWT","LIMA","MESA","MEWL","AXLE","FAME","ASEM","MILE","AMIL","SEAX","SEAM","SEMI","SWAM","AMBO","AMLI","AXILE","AMBLE","SWAMI","AWEST","AWEST","LIMAX","LIMES","LIMBU","LIMBO","EMBOX","SEMBLE","EMBOLE","WAMBLE","FAMBLE"]

Code:

var fs = require('fs')

var Node = function(value, row, col) {
    this.value = value
    this.row = row
    this.col = col
}

var Path = function() {
    this.nodes = []
}

Path.prototype.push = function(node) {
    this.nodes.push(node)
    return this
}

Path.prototype.contains = function(node) {
    for (var i = 0, ii = this.nodes.length; i < ii; i++) {
        if (this.nodes[i] === node) {
            return true
        }
    }

    return false
}

Path.prototype.clone = function() {
    var path = new Path()
    path.nodes = this.nodes.slice(0)
    return path
}

Path.prototype.to_word = function() {
    var word = ''

    for (var i = 0, ii = this.nodes.length; i < ii; ++i) {
        word += this.nodes[i].value
    }

    return word
}

var Board = function(nodes, dict) {
    // Erwartet ein n x m Array.
    this.nodes = nodes
    this.words = []
    this.row_count = nodes.length
    this.col_count = nodes[0].length
    this.dict = dict
}

Board.from_raw = function(board, dict) {
    var ROW_COUNT = board.length
      , COL_COUNT = board[0].length

    var nodes = []

    // Ersetze das Brett durch Nodes
    for (var i = 0, ii = ROW_COUNT; i < ii; ++i) {
        nodes.push([])
        for (var j = 0, jj = COL_COUNT; j < jj; ++j) {
            nodes[i].push(new Node(board[i][j], i, j))
        }
    }

    return new Board(nodes, dict)
}

Board.prototype.toString = function() {
    return JSON.stringify(this.nodes)
}

Board.prototype.update_potential_words = function(dict) {
    for (var i = 0, ii = this.row_count; i < ii; ++i) {
        for (var j = 0, jj = this.col_count; j < jj; ++j) {
            var node = this.nodes[i][j]
              , path = new Path()

            path.push(node)

            this.dfs_search(path)
        }
    }
}

Board.prototype.on_board = function(row, col) {
    return 0 <= row && row < this.row_count && 0 <= col && col < this.col_count
}

Board.prototype.get_unsearched_neighbours = function(path) {
    var last_node = path.nodes[path.nodes.length - 1]

    var offsets = [
        [-1, -1], [-1,  0], [-1, +1]
      , [ 0, -1],           [ 0, +1]
      , [+1, -1], [+1,  0], [+1, +1]
    ]

    var neighbours = []

    for (var i = 0, ii = offsets.length; i < ii; ++i) {
        var offset = offsets[i]
        if (this.on_board(last_node.row + offset[0], last_node.col + offset[1])) {

            var potential_node = this.nodes[last_node.row + offset[0]][last_node.col + offset[1]]
            if (!path.contains(potential_node)) {
                // Erstelle einen neuen Pfad, wenn auf dem Brett und dieser Knoten noch nicht besucht wurde.
                neighbours.push(potential_node)
            }
        }
    }

    return neighbours
}

Board.prototype.dfs_search = function(path) {
    var path_word = path.to_word()

    if (this.dict.contains_exact(path_word) && path_word.length >= 3) {
        this.words.push(path_word)
    }

    var neighbours = this.get_unsearched_neighbours(path)

    for (var i = 0, ii = neighbours.length; i < ii; ++i) {
        var neighbour = neighbours[i]
        var new_path = path.clone()
        new_path.push(neighbour)

        if (this.dict.contains_prefix(new_path.to_word())) {
            this.dfs_search(new_path)
        }
    }
}

var Dict = function() {
    this.dict_array = []

    var dict_data = fs.readFileSync('./web2', 'utf8')
    var dict_array = dict_data.split('\n')

    for (var i = 0, ii = dict_array.length; i < ii; ++i) {
        dict_array[i] = dict_array[i].toUpperCase()
    }

    this.dict_array = dict_array.sort()
}

Dict.prototype.contains_prefix = function(prefix) {
    // Binäre Suche
    return this.search_prefix(prefix, 0, this.dict_array.length)
}

Dict.prototype.contains_exact = function(exact) {
    // Binäre Suche
    return this.search_exact(exact, 0, this.dict_array.length)
}

Dict.prototype.search_prefix = function(prefix, start, end) {
    if (start >= end) {
        // Wenn kein weiterer Ort zum Suchen vorhanden ist, gibt es unabhängig davon zurück.
        return this.dict_array[start].indexOf(prefix) > -1
    }

    var middle = Math.floor((start + end)/2)

    if (this.dict_array[middle].indexOf(prefix) > -1) {
        // Wenn unser Präfix existiert, geben wir true zurück.
        return true
    } else {
        // Rekurs
        if (prefix <= this.dict_array[middle]) {
            return this.search_prefix(prefix, start, middle - 1)
        } else {
            return this.search_prefix(prefix, middle + 1, end)
        }
    }
}

Dict.prototype.search_exact = function(exact, start, end) {
    if (start >= end) {
        // Wenn kein weiterer Ort zum Suchen vorhanden ist, gibt es unabhängig davon zurück.
        return this.dict_array[start] === exact
    }

    var middle = Math.floor((start + end)/2)

    if (this.dict_array[middle] === exact) {
        // Wenn unser Präfix existiert, geben wir true zurück.
        return true
    } else {
        // Rekurs
        if (exact <= this.dict_array[middle]) {
            return this.search_exact(exact, start, middle - 1)
        } else {
            return this.search_exact(exact, middle + 1, end)
        }
    }
}

var board = [
    ['F', 'X', 'I', 'E']
  , ['A', 'M', 'L', 'O']
  , ['E', 'W', 'B', 'X']
  , ['A', 'S', 'T', 'U']
]

var dict = new Dict()

var b = Board.from_raw(board, dict)
b.update_potential_words()
console.log(JSON.stringify(b.words.sort(function(a, b) {
    return a.length - b.length
})))

Answer 3

Also wollte ich einen weiteren PHP-Weg finden, um das zu lösen, da jeder PHP liebt. Es gibt ein bisschen Refactoring, das ich gerne machen würde, z. B. die Verwendung eines regulären Ausdrucks zum Abgleich mit der Wörterbuchdatei, aber im Moment lade ich gerade die gesamte Wörterbuchdatei in eine Wortliste.

Das habe ich mit einer Idee einer verketteten Liste gemacht. Jeder Knoten hat einen Zeichenwert, einen Ortswert und einen nächsten Zeiger.

Der Ortswert zeigt mir, ob zwei Knoten verbunden sind.

1     2     3     4
11    12    13    14
21    22    23    24
31    32    33    34

Also weiß ich anhand dieses Rasters, dass zwei Knoten verbunden sind, wenn der Ortswert des ersten Knotens dem des zweiten Knotens entspricht +/- 1 für die gleiche Zeile, +/- 9, 10, 11 für die Reihe darüber und darunter.

Ich benutze Rekursion für die Hauptsuche. Es nimmt ein Wort aus der Wortliste, findet alle möglichen Startpunkte und findet dann rekursiv die nächste mögliche Verbindung, unter Berücksichtigung, dass es nicht zu einem bereits verwendeten Ort gehen kann (deshalb füge ich $notInLoc hinzu).

Wie auch immer, ich weiß, dass es einige Refactorings braucht, und würde gerne hören, wie man es sauberer machen könnte, aber es liefert die korrekten Ergebnisse basierend auf der Wörterbuchdatei, die ich verwende. Abhängig von der Anzahl der Vokale und Kombinationen auf dem Brett dauert es etwa 3 bis 6 Sekunden. Ich weiß, dass sich dies erheblich verringern wird, sobald ich die Wörterbuchergebnisse mit preg_match abrufe.

value = $value;
            $next = null;
        }
    }

    class Boggle {
        var $root;
        var $locList = array (1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34);
        var $wordList = [];
        var $foundWords = [];

        function __construct($board) {
            // Nimmt einen Brett-String entgegen und erstellt alle Knoten
            $node = new Node($board[0]);
            $node->loc = $this->locList[0];
            $this->root = $node;
            for ($i = 1; $i < strlen($board); $i++) {
                    $node->next = new Node($board[$i]);
                    $node->next->loc = $this->locList[$i];
                    $node = $node->next;
            }
            // Lädt eine Wörterbuchdatei
            // Verwendet Regex, um alle Wörter zu eliminieren, die nie erscheinen könnten, und lädt den Rest der Wörter in die Wortliste
            $handle = fopen("dict.txt", "r");
            if ($handle) {
                while (($line = fgets($handle)) !== false) {
                    // Verarbeitet die gelesene Zeile
                    $line = trim($line);
                    if (strlen($line) > 2) {
                        $this->wordList[] = trim($line);
                    }
                }
                fclose($handle);
            } else {
                // Fehler beim Öffnen der Datei.
                echo "Problem mit der Datei.";
            } 
        }

        function isConnected($node1, $node2) {
        // Bestimmt, ob 2 Knoten auf dem Boggle-Brett verbunden sind

            return (($node1->loc == $node2->loc + 1) || ($node1->loc == $node2->loc - 1) ||
               ($node1->loc == $node2->loc - 9) || ($node1->loc == $node2->loc - 10) || ($node1->loc == $node2->loc - 11) ||
               ($node1->loc == $node2->loc + 9) || ($node1->loc == $node2->loc + 10) || ($node1->loc == $node2->loc + 11)) ? true : false;

        }

        function find($value, $notInLoc = []) {
            // Gibt einen Knoten mit dem Wert zurück, der nicht an einem Ort liegt
            $current = $this->root;
            while($current) {
                if ($current->value == $value && !in_array($current->loc, $notInLoc)) {
                    return $current;
                }
                if (isset($current->next)) {
                    $current = $current->next;
                } else {
                    break;
                }
            }
            return false;
        }

        function findAll($value) {
            // Gibt ein Array von Knoten mit einem bestimmten Wert zurück
            $current = $this->root;
            $foundNodes = [];
            while ($current) {
                if ($current->value == $value) {
                    $foundNodes[] = $current;
                }
                if (isset($current->next)) {
                    $current = $current->next;
                } else {
                    break;
                }
            }
            return (empty($foundNodes)) ? false : $foundNodes;
        }

        function findAllConnectedTo($node, $value, $notInLoc = []) {
            // Gibt ein Array von Knoten zurück, die mit einem bestimmten Knoten verbunden sind und einen bestimmten Wert enthalten und nicht an einem bestimmten Ort liegen
            $nodeList = $this->findAll($value);
            $newList = [];
            if ($nodeList) {
                foreach ($nodeList as $node2) {
                    if (!in_array($node2->loc, $notInLoc) && $this->isConnected($node, $node2)) {
                        $newList[] = $node2;
                    }
                }
            }
            return (empty($newList)) ? false : $newList;
        }

        function inner($word, $list, $i = 0, $notInLoc = []) {
            $i++;
            foreach($list as $node) {
                $notInLoc[] = $node->loc;
                if ($list2 = $this->findAllConnectedTo($node, $word[$i], $notInLoc)) {
                    if ($i == (strlen($word) - 1)) {
                        return true;
                    } else {
                        return $this->inner($word, $list2, $i, $notInLoc);
                    }
                }
            }
            return false;
        }

        function findWord($word) {
            if ($list = $this->findAll($word[0])) {
                return $this->inner($word, $list);
            }
            return false;
        }

        function findAllWords() {
            foreach($this->wordList as $word) {
                if ($this->findWord($word)) {
                    $this->foundWords[] = $word;
                }
            }
        }

        function displayBoard() {
            $current = $this->root;
            for ($i=0; $i < 4; $i++) {
                echo $current->value . " " . $current->next->value . " " . $current->next->next->value . " " . $current->next->next->next->value . "";
                if ($i < 3) {
                    $current = $current->next->next->next->next;
                }
            }
        }

    }

    function randomBoardString() {
        return substr(str_shuffle(str_repeat("abcdefghijklmnopqrstuvwxyz", 16)), 0, 16);
    }

    $myBoggle = new Boggle(randomBoardString());
    $myBoggle->displayBoard();
    $x = microtime(true);
    $myBoggle->findAllWords();
    $y = microtime(true);
    echo ($y-$x);
    var_dump($myBoggle->foundWords);

    ?>

Answer 4

Ich weiß, dass ich wirklich spät zur Party komme, aber ich habe als Programmierübung einen Boggle Solver in mehreren Programmiersprachen implementiert (C++, Java, Go, C#, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) und dachte, dass es jemanden interessieren könnte, also hinterlasse ich hier den Link: https://github.com/AmokHuginnsson/boggle-solvers

Answer 5

Hier ist die Lösung unter Verwendung von vordefinierten Wörtern im NLTK-Toolkit NLTK hat das Paket nltk.corpus, in dem wir das Paket words haben und es enthält mehr als 2Lakhs englische Wörter, die Sie einfach alle in Ihr Programm einbinden können.

Nachdem Sie Ihre Matrix erstellt haben, konvertieren Sie sie in ein Zeichenarray und führen Sie diesen Code aus

import nltk
from nltk.corpus import words
from collections import Counter

def moeglicheWoerter(input, charSet):
    for word in input:
        dict = Counter(word)
        flag = 1
        for key in dict.keys():
            if key not in charSet:
                flag = 0
        if flag == 1 and len(word)>5: #es hängt davon ab, ob Sie nur nach einer Länge von mehr als 5 suchen, verwenden Sie das, ansonsten entfernen Sie es.
            print(word)

nltk.download('words')
word_list = words.words()
# druckt 236736 aus
print(len(word_list))
charSet = ['h', 'e', 'l', 'o', 'n', 'v', 't']
moeglicheWoerter(word_list, charSet)

Ausgabe:

elf
elfte
Elevon
Entente
Entone
Äthen
Ethenol
entwickeln
Evolver
Höhlenhölle
helvell
hooven
letten
looten
netz
nonene
NONENT
Nichtebene
Notizblatt
Novelle
Novelle
Novelle
novene
TEENET
Brüten
Teevee
Telefon
Erzählung
Pächter
tentlet
theelol
toetoe
Tonlet
Zahnlätzchen
umhauen
tottle
Velum
Samt
Venant
Vennel
ventil
voeten
volent
volvelle
volvent
Voting

Ich hoffe, Sie haben es verstanden.