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

Verkleinert Ihr Suchalgorithmus kontinuierlich die Wortliste, während Ihre Suche fortgesetzt wird?

Zum Beispiel gibt es in der oben genannten Suche nur 13 Buchstaben, mit denen Ihre Wörter beginnen können (effektiv reduziert auf die Hälfte so vieler Anfangsbuchstaben).

Indem Sie mehr Buchstabenpermutationen hinzufügen, würde sich die verfügbaren Wortsets weiter verringern und die erforderliche Suche verringern.

Dort würde ich anfangen.

Answer 2

Lustig. Ich hätte vor ein paar Tagen fast die gleiche Frage wegen dem verdammten Spiel gepostet! Das habe ich jedoch nicht getan, weil ich einfach bei Google nach boggle solver python gesucht und alle Antworten gefunden habe, die ich brauchte.

Answer 3

Ich weiß, dass die Zeit für diese Frage bereits gekommen und gegangen ist, aber da ich selbst an einem Solver gearbeitet habe und dies beim Googeln entdeckt habe, dachte ich, ich sollte eine Referenz zu meinem posten, da er sich anscheinend etwas von einigen anderen unterscheidet.

Ich habe mich für ein flaches Array für das Spielfeld entschieden und rekursive Jagden von jedem Buchstaben auf dem Spielfeld durchgeführt, indem ich von gültigem Nachbarn zu gültigem Nachbarn traversiere und die Jagd erweitere, wenn die aktuelle Liste von Buchstaben ein gültiges Präfix in einem Index ist. Während des Traversierens besteht die aktuelle Wortvorstellung aus einer Liste von Indexen im Feld, nicht aus Buchstaben, die ein Wort bilden. Beim Überprüfen des Index werden die Indizes in Buchstaben übersetzt und die Überprüfung durchgeführt.

Der Index ist ein brute force Wörterbuch, das ein wenig wie ein Trie ist, aber Python-Abfragen des Index erlaubt. Wenn die Wörter 'Katze' und 'Kater' in der Liste sind, erhalten Sie dies im Wörterbuch:

   d = { 'c': ['cat','cater'],
     'ca': ['cat','cater'],
     'cat': ['cat','cater'],
     'cate': ['cater'],
     'cater': ['cater'],
   }

Wenn also das aktuelle Wort 'ca' ist, wissen Sie, dass es ein gültiges Präfix ist, weil 'ca' in d True zurückgibt (also die Traversierung des Spielfeld fortsetzen). Und wenn das aktuelle Wort 'Katze' ist, dann wissen Sie, dass es ein gültiges Wort ist, weil es ein gültiges Präfix ist und 'cat' in d['cat'] auch True zurückgibt.

Es schien mir, dass dies für einen gut lesbaren Code sorgt, der nicht allzu langsam ist. Wie bei allen anderen liegt der Aufwand in diesem System darin, den Index zu lesen/aufzubauen. Das Lösen des Spielfelds ist so gut wie "Lärm".

Der Code befindet sich unter http://gist.github.com/268079. Er ist absichtlich vertikal und naiv mit vielen expliziten Gültigkeitsüberprüfungen, weil ich das Problem verstehen wollte, ohne es mit einem Haufen Magie oder Dunkelheit zu belasten.

Answer 4

Ich habe meinen Solver in C++ geschrieben. Ich habe eine benutzerdefinierte Baumstruktur implementiert. Ich bin mir nicht sicher, ob es als Trie betrachtet werden kann, aber es ist ähnlich. Jeder Knoten hat 26 Zweige, einen für jeden Buchstaben des Alphabets. Ich durchlaufe die Zweige des Boggle-Boards parallel zu den Zweigen meines Wörterbuchs. Wenn der Zweig nicht im Wörterbuch existiert, höre ich auf, danach auf dem Boggle-Board zu suchen. Ich konvertiere alle Buchstaben auf dem Board in ints. So 'A' = 0. Da es sich nur um Arrays handelt, ist die Suche immer O(1). Jeder Knoten speichert, ob er ein Wort vervollständigt und wie viele Wörter in seinen Kindern existieren. Der Baum wird beschnitten, wenn Wörter gefunden werden, um wiederholte Suchvorgänge nach denselben Wörtern zu reduzieren. Ich glaube, dass das Beschneiden auch O(1) ist.

CPU: Pentium SU2700 1,3 GHz
RAM: 3gb

Lädt Wörterbuch mit 178.590 Wörtern in < 1 Sekunde.
Löst 100x100 Boggle (boggle.txt) in 4 Sekunden. ~44.000 Wörter gefunden.
Das Lösen eines 4x4 Boggle ist zu schnell, um einen aussagekräftigen Benchmark zu liefern. :)

Schneller Boggle Solver GitHub Repo

Answer 5

Bei einem Boggle-Board mit N Zeilen und M Spalten gehen wir von Folgendem aus:

• N*M ist wesentlich größer als die Anzahl der möglichen Wörter
• N*M ist wesentlich größer als das längste mögliche Wort

Unter diesen Annahmen hat diese Lösung eine Komplexität von O(N*M).

Ich denke, der Vergleich der Laufzeiten für dieses eine Beispielboard verfehlt in vielerlei Hinsicht den Punkt, aber der Vollständigkeit halber: Diese Lösung ist auf meinem modernen MacBook Pro in weniger als 0,2s abgeschlossen.

Diese Lösung wird alle möglichen Pfade für jedes Wort im Korpus finden.

#!/usr/bin/env ruby
# Beispielverwendung: ./boggle-solver --board "fxie amlo ewbx astu"

autoload :Matrix, 'matrix'
autoload :OptionParser, 'optparse'

DEFAULT_CORPUS_PATH = '/usr/share/dict/words'.freeze

# Funktionen

def filter_corpus(matrix, corpus, min_word_length)
  board_char_counts = Hash.new(0)
  matrix.each { |c| board_char_counts[c] += 1 }

  max_word_length = matrix.row_count * matrix.column_count
  boggleable_regex = /^[#{board_char_counts.keys.reduce(:+)}]{#{min_word_length},#{max_word_length}}$/
  corpus.select{ |w| w.match boggleable_regex }.select do |w|
    word_char_counts = Hash.new(0)
    w.each_char { |c| word_char_counts[c] += 1 }
    word_char_counts.all? { |c, count| board_char_counts[c] >= count }
  end
end

def neighbors(point, matrix)
  i, j = point
  ([i-1, 0].max .. [i+1, matrix.row_count-1].min).inject([]) do |r, new_i|
    ([j-1, 0].max .. [j+1, matrix.column_count-1].min).inject(r) do |r, new_j|
      neighbor = [new_i, new_j]
      neighbor.eql?(point) ? r : r << neighbor
    end
  end
end

def expand_path(path, word, matrix)
  return [path] if path.length == word.length

  next_char = word[path.length]
  viable_neighbors = neighbors(path[-1], matrix).select do |point|
    !path.include?(point) && matrix.element(*point).eql?(next_char)
  end

  viable_neighbors.inject([]) do |result, point|
    result + expand_path(path.dup << point, word, matrix)
  end
end

def find_paths(word, matrix)
  result = []
  matrix.each_with_index do |c, i, j|
    result += expand_path([[i, j]], word, matrix) if c.eql?(word[0])
  end
  result
end

def solve(matrix, corpus, min_word_length: 3)
  boggleable_corpus = filter_corpus(matrix, corpus, min_word_length)
  boggleable_corpus.inject({}) do |result, w|
    paths = find_paths(w, matrix)
    result[w] = paths unless paths.empty?
    result
  end
end

# Skript

options = { corpus_path: DEFAULT_CORPUS_PATH }
option_parser = OptionParser.new do |opts|
  opts.banner = 'Verwendung: boggle-solver --board  [--corpus ]'

  opts.on('--board BOARD', String, 'Das Board (z.B. "fxi aml ewb ast")') do |b|
    options[:board] = b
  end

  opts.on('--corpus CORPUS_PATH', String, 'Pfad zur Wortliste') do |c|
    options[:corpus_path] = c
  end

  opts.on_tail('-h', '--help', 'Zeigt die Verwendung an') do
    STDOUT.puts opts
    exit
  end
end
option_parser.parse!

unless options[:board]
  STDERR.puts option_parser
  exit false
end

unless File.file? options[:corpus_path]
  STDERR.puts "Kein Korpus vorhanden - #{options[:corpus_path]}"
  exit false
end

rows = options[:board].downcase.scan(/\S+/).map{ |row| row.scan(/./) }

raw_corpus = File.readlines(options[:corpus_path])
corpus = raw_corpus.map{ |w| w.downcase.rstrip }.uniq.sort

solution = solve(Matrix.rows(rows), corpus)
solution.each_pair do |w, paths|
  STDOUT.puts w
  paths.each do |path|
    STDOUT.puts "\t" + path.map{ |point| point.inspect }.join(', ')
  end
end
STDOUT.puts "TOTAL: #{solution.count}"