wake-up-neo.com

So finden Sie die Liste der möglichen Wörter aus einer Buchstabenmatrix [Boggle Solver]

In letzter Zeit habe ich auf meinem iPhone ein Spiel namens Scramble gespielt. Einige von euch kennen dieses Spiel vielleicht als Boggle. Zu Beginn des Spiels erhalten Sie im Wesentlichen eine Buchstabenmatrix wie folgt:

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 jedem Buchstaben beginnen, und alle Buchstaben, die ihn umgeben, sind Fair Game. Wenn Sie dann mit dem nächsten Buchstaben fortfahren, sind alle Buchstaben, die diesen Buchstaben umgeben, Fair Game. Mit Ausnahme aller zuvor verwendeten Buchstaben . So könnte ich zum Beispiel im obigen Raster die Wörter LOB, Tux, SEA, FAME usw. finden. Wörter müssen mindestens 3 Zeichen und nicht mehr als NxN Zeichen umfassen, was in diesem Spiel aber 16 Zeichen entsprechen würde variieren in einigen Implementierungen. Obwohl dieses Spiel Spaß macht und süchtig macht, bin ich anscheinend nicht sehr gut darin und wollte ein bisschen schummeln, indem ich ein Programm erstellte, das mir die bestmöglichen Wörter gab (je länger das Wort, desto mehr Punkte bekommst du).

 Sample Boggle
(Quelle: boggled.org )

Ich bin leider nicht sehr gut mit Algorithmen oder deren Effizienz und so weiter. Mein erster Versuch verwendet ein Wörterbuch wie dieses (~ 2,3 MB) und führt eine lineare Suche durch, bei der versucht wird, Kombinationen mit Wörterbucheinträgen abzugleichen. Das Auffinden der möglichen Wörter dauert sehr lange, und da Sie nur 2 Minuten pro Runde erhalten, ist dies einfach nicht ausreichend.

Ich bin gespannt, ob mit Stackoverflowers effizientere Lösungen gefunden werden können. Ich suche hauptsächlich nach Lösungen mit den Big 3 Ps: Python, PHP und Perl, obwohl alles mit Java oder C++ auch cool ist, da Geschwindigkeit von entscheidender Bedeutung ist.

AKTUELLE LÖSUNGEN:

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

KOPFGELD:

Ich füge dieser Frage ein Kopfgeld hinzu, um mich bei all den Leuten zu bedanken, die mit ihren Programmen mitgewirkt haben. Leider kann ich nur einem von Ihnen die akzeptierte Antwort geben. Daher werde ich in 7 Tagen messen, wer den schnellsten Fehlerlöser hat, und dem Gewinner das Kopfgeld gewähren.

Kopfgeld vergeben. Vielen Dank an alle, die teilgenommen haben.

373

Meine Antwort funktioniert wie die anderen hier, aber ich poste sie, weil sie etwas schneller aussieht als die anderen Python-Lösungen, da das Wörterbuch schneller eingerichtet wird. (Ich habe das mit der Lösung von John Fouhys verglichen.) Nach dem Setup ist die Zeit für die Lösung im Lärm.

grid = "fxie amlo ewbx astu".split()
nrows, ncols = len(grid), len(grid[0])

# A dictionary Word that could be a solution must use only the grid's
# letters and have length >= 3. (With a case-insensitive match.)
import re
alphabet = ''.join(set(''.join(grid)))
bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match

words = set(Word.rstrip('\n') for Word in open('words') if bogglable(Word))
prefixes = set(Word[:i] for Word in words
               for i in range(2, len(Word)+1))

def solve():
    for y, row in enumerate(grid):
        for x, letter in enumerate(row):
            for result in extending(letter, ((x, y),)):
                yield result

def extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield result

def neighbors((x, y)):
    for nx in range(max(0, x-1), min(x+2, ncols)):
        for ny in range(max(0, y-1), min(y+2, nrows)):
            yield (nx, ny)

Verwendungsbeispiel:

# Print a maximal-length Word and its path:
print max(solve(), key=lambda (Word, path): len(Word))

Bearbeiten: Wörter aus weniger als 3 Buchstaben herausfiltern.

Edit 2: Ich war neugierig, warum Perl-Lösung von Kent Fredric schneller war. Es stellt sich heraus, dass Sie einen regulären Ausdruck anstelle eines Zeichensatzes verwenden. Das Gleiche in Python zu tun, verdoppelt die Geschwindigkeit.

140
Darius Bacon

Die schnellste Lösung, die Sie erhalten werden, wird wahrscheinlich das Speichern Ihres Wörterbuchs in einem trie beinhalten. Erstellen Sie dann eine Warteschlange mit Triolen (x, y, s), wobei jedes Element in der Warteschlange einem Präfix s entspricht. eines Wortes, das im Gitter buchstabiert werden kann und an der Stelle endet (x, y). Initialisieren Sie die Warteschlange mit N x N Elementen (wobei N die Größe Ihres Gitters ist), einem Element für jedes Quadrat in der Gitter. Dann geht der Algorithmus wie folgt vor:

 Während die Warteschlange nicht leer ist: 
 Enteue ein Triple (x, y, s) 
 Für jedes Quadrat (x ', y') mit dem Buchstaben c neben (x, y): 
 Wenn s + c ein Wort ist, geben Sie s + c .__ aus. Wenn s + c ein Präfix eines Wortes ist, fügen Sie (x ', y', s + c) in die Warteschlange ein 

Wenn Sie Ihr Wörterbuch in einem Trie speichern, können Sie prüfen, ob s + c ein Word ist oder ein Präfix eines Words in konstanter Zeit ausgeführt werden kann (vorausgesetzt, Sie haben auch einige zusätzliche Metadaten in Da jedes Warteschlangendatum (z. B. ein Zeiger auf den aktuellen Knoten im Trie), ist die Laufzeit dieses Algorithmus O (Anzahl der Wörter, die geschrieben werden können).

[Edit] Hier ist eine Implementierung in Python, die ich gerade codiert habe:

#!/usr/bin/python

class TrieNode:
    def __init__(self, parent, value):
        self.parent = parent
        self.children = [None] * 26
        self.isWord = False
        if parent is not None:
            parent.children[ord(value) - 97] = self

def MakeTrie(dictfile):
    dict = open(dictfile)
    root = TrieNode(None, '')
    for Word in dict:
        curNode = root
        for letter in Word.lower():
            if 97 <= ord(letter) < 123:
                nextNode = curNode.children[ord(letter) - 97]
                if nextNode is None:
                    nextNode = TrieNode(curNode, letter)
                curNode = nextNode
        curNode.isWord = True
    return root

def BoggleWords(grid, dict):
    rows = len(grid)
    cols = len(grid[0])
    queue = []
    words = []
    for y in range(cols):
        for x in range(rows):
            c = grid[y][x]
            node = dict.children[ord(c) - 97]
            if node is not None:
                queue.append((x, y, c, node))
    while queue:
        x, y, s, node = queue[0]
        del queue[0]
        for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)):
            x2, y2 = x + dx, y + dy
            if 0 <= x2 < cols and 0 <= y2 < rows:
                s2 = s + grid[y2][x2]
                node2 = node.children[ord(grid[y2][x2]) - 97]
                if node2 is not None:
                    if node2.isWord:
                        words.append(s2)
                    queue.append((x2, y2, s2, node2))

    return words

Verwendungsbeispiel:

d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))

Ausgabe:

['fa', 'xi', 'dh', 'io', 'el', 'bin', 'axt', 'ae', 'aw', 'mi', 'ma', 'me', ' lo ',' li ',' oe ',' ox ',' em ',' ea ',' ea ',' es ',' wa ',' wir ',' wa ',' bo ',' bu ' , 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli', ' Ulme ',' Elb ',' AMI ',' AMA ',' Ame ',' Aes ',' Ahle ',' Avis ',' Awe ',' Awe ',' Avis ',' Mix ',' Mim ',' Mil ' , 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei', 'leo', 'lüge' lim ',' öl ',' olm ',' mutterschaf ',' eme ',' wachs ',' waf ',' wae ',' waw ',' wem ',' wea ',' wea ',' was ' , 'waw', 'wae', 'bob', 'blo', 'bub', 'aber', 'ast', 'ase', 'asa', 'ahle', 'awa', 'awe', ' awa, aes, swa, swa, nähen, meer, meer, sah, Tux, badewanne, tut, twa, twa , 'tst', 'utu', 'fama', 'fame', 'ixil', 'imam', 'amli', 'amil', 'ambo', 'axil', 'Achse', 'mimi', ' mima, mime, milo, meile, mewl, mese, mesa, lolo, lobo, lima, limette, limette, lile , 'oime', 'oleo', 'olio', 'oboe', 'obol', 'emim', 'emil', 'ost', 'leichtigkeit', 'wame', 'wawa', 'wawa', ' Weam, West, Wese, Waste, Wase , 'wawa', 'wawa', 'kochen', 'bolo', 'bole', 'bobo', 'blob', 'bleo', 'bubo', 'asem', 'stub', 'stut', ' Schwamm, Semi, Seme, Naht, Seax, Sasa, Sawt, Tutu, Tuts, Twae, Twas, Twae, Ilima , 'amble', 'axile', 'awest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax', 'limes', 'limbo', 'limbu', ' obole ',' emesa ',' embox ',' awest ',' swami ',' famble ',' mimble ',' maxima ',' embolo ',' embole ',' wamble ',' semese ',' semble ' , 'sawbwa', 'sawbwa']

Hinweise: Dieses Programm gibt keine Wörter mit nur einem Buchstaben aus und filtert nicht nach Wortlänge. Das lässt sich leicht hinzufügen, ist aber für das Problem nicht wirklich relevant. Einige Wörter werden auch mehrmals ausgegeben, wenn sie auf mehrere Arten buchstabiert werden können. Wenn ein bestimmtes Wort auf viele verschiedene Arten geschrieben werden kann (im schlimmsten Fall: Jeder Buchstabe im Raster ist derselbe (z. B. 'A') und ein Wort wie 'aaaaaaaaaa' in Ihrem Wörterbuch), dann wird die Laufzeit schrecklich exponentiell . Das Herausfiltern von Duplikaten und das Sortieren ist nach Beendigung des Algorithmus trivial bis fällig.

116
Adam Rosenfield

Für eine Wörterbuchbeschleunigung gibt es eine allgemeine Umwandlung/einen allgemeinen Vorgang, mit dem Sie die Wörterbuchvergleiche im Voraus erheblich reduzieren können.

Da das obige Raster nur 16 Zeichen enthält, von denen einige doppelt vorhanden sind, können Sie die Anzahl der Schlüssel in Ihrem Wörterbuch erheblich reduzieren, indem Sie einfach Einträge mit nicht erreichbaren Zeichen herausfiltern.

Ich dachte, dies sei die offensichtliche Optimierung, aber als ich sah, dass niemand es tat, erwähne ich es.

Es reduzierte mich von einem Wörterbuch mit 200.000 Schlüsseln auf nur 2.000 Schlüssel, einfach während der Eingabe. Dies reduziert zumindest den Arbeitsspeicher-Overhead, und das wird sich sicher irgendwo auf eine Geschwindigkeitssteigerung auswirken, da der Arbeitsspeicher nicht unendlich schnell ist.

Perl-Implementierung

Meine Implementierung ist etwas kopflastig, da ich Wert darauf legte, den genauen Pfad jedes extrahierten Strings zu kennen, nicht nur die Gültigkeit.

Ich habe dort auch ein paar Anpassungen vorgenommen, die theoretisch die Funktion eines Gitters mit Löchern und Gittern mit Linien unterschiedlicher Größe ermöglichen (vorausgesetzt, Sie haben die richtige Eingabe und es richtet sich irgendwie aus).

Der Early-Filter ist, wie bereits vermutet, der mit Abstand größte signifikante Engpass in meiner Anwendung.

Bei der Ausführung scheint es so zu sein, als ob alle einzelnen Ziffern ihre eigenen gültigen Wörter enthalten, aber ich bin mir ziemlich sicher, dass dies aufgrund der Funktionsweise der Wörterbuchdatei der Fall ist.

Es ist ein bisschen aufgebläht, aber zumindest verwende ich Tree :: Trie von cpan

Ein Teil davon wurde teilweise von den vorhandenen Implementierungen inspiriert, ein Teil davon hatte ich bereits im Sinn.

Konstruktive Kritik und Verbesserungsmöglichkeiten sind willkommen (/ ich nehme zur Kenntnis, dass er nie CPAN nach einem Fehlerlöser durchsucht hat , aber es hat mehr Spaß gemacht, das herauszufinden)

aktualisiert für neue Kriterien

#!/usr/bin/Perl 

use strict;
use warnings;

{

  # this package manages a given path through the grid.
  # Its an array of matrix-nodes in-order with
  # Convenience functions for pretty-printing the paths
  # and for extending paths as new paths.

  # Usage:
  # my $p = Prefix->new(path=>[ $startnode ]);
  # my $c = $p->child( $extensionNode );
  # print $c->current_Word ;

  package Prefix;
  use Moose;

  has path => (
      isa     => 'ArrayRef[MatrixNode]',
      is      => 'rw',
      default => sub { [] },
  );
  has current_Word => (
      isa        => 'Str',
      is         => 'rw',
      lazy_build => 1,
  );

  # Create a clone of this object
  # with a longer path

  # $o->child( $successive-node-on-graph );

  sub child {
      my $self    = shift;
      my $newNode = shift;
      my $f       = Prefix->new();

      # Have to do this manually or other recorded paths get modified
      Push @{ $f->{path} }, @{ $self->{path} }, $newNode;
      return $f;
  }

  # Traverses $o->path left-to-right to get the string it represents.

  sub _build_current_Word {
      my $self = shift;
      return join q{}, map { $_->{value} } @{ $self->{path} };
  }

  # Returns  the rightmost node on this path

  sub tail {
      my $self = shift;
      return $self->{path}->[-1];
  }

  # pretty-format $o->path

  sub pp_path {
      my $self = shift;
      my @path =
        map { '[' . $_->{x_position} . ',' . $_->{y_position} . ']' }
        @{ $self->{path} };
      return "[" . join( ",", @path ) . "]";
  }

  # pretty-format $o
  sub pp {
      my $self = shift;
      return $self->current_Word . ' => ' . $self->pp_path;
  }

  __PACKAGE__->meta->make_immutable;
}

{

  # Basic package for tracking node data
  # without having to look on the grid.
  # I could have just used an array or a hash, but that got ugly.

# Once the matrix is up and running it doesn't really care so much about rows/columns,
# Its just a sea of points and each point has adjacent points.
# Relative positioning is only really useful to map it back to userspace

  package MatrixNode;
  use Moose;

  has x_position => ( isa => 'Int', is => 'rw', required => 1 );
  has y_position => ( isa => 'Int', is => 'rw', required => 1 );
  has value      => ( isa => 'Str', is => 'rw', required => 1 );
  has siblings   => (
      isa     => 'ArrayRef[MatrixNode]',
      is      => 'rw',
      default => sub { [] }
  );

# Its not implicitly uni-directional joins. It would be more effient in therory
# to make the link go both ways at the same time, but thats too hard to program around.
# and besides, this isn't slow enough to bother caring about.

  sub add_sibling {
      my $self    = shift;
      my $sibling = shift;
      Push @{ $self->siblings }, $sibling;
  }

  # Convenience method to derive a path starting at this node

  sub to_path {
      my $self = shift;
      return Prefix->new( path => [$self] );
  }
  __PACKAGE__->meta->make_immutable;

}

{

  package Matrix;
  use Moose;

  has rows => (
      isa     => 'ArrayRef',
      is      => 'rw',
      default => sub { [] },
  );

  has regex => (
      isa        => 'Regexp',
      is         => 'rw',
      lazy_build => 1,
  );

  has cells => (
      isa        => 'ArrayRef',
      is         => 'rw',
      lazy_build => 1,
  );

  sub add_row {
      my $self = shift;
      Push @{ $self->rows }, [@_];
  }

  # Most of these functions from here down are just builder functions,
  # or utilities to help build things.
  # Some just broken out to make it easier for me to process.
  # All thats really useful is add_row
  # The rest will generally be computed, stored, and ready to go
  # from ->cells by the time either ->cells or ->regex are called.

  # traverse all cells and make a regex that covers them.
  sub _build_regex {
      my $self  = shift;
      my $chars = q{};
      for my $cell ( @{ $self->cells } ) {
          $chars .= $cell->value();
      }
      $chars = "[^$chars]";
      return qr/$chars/i;
  }

  # convert a plain cell ( ie: [x][y] = 0 )
  # to an intelligent cell ie: [x][y] = object( x, y )
  # we only really keep them in this format temporarily
  # so we can go through and tie in neighbouring information.
  # after the neigbouring is done, the grid should be considered inoperative.

  sub _convert {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my $v    = $self->_read( $x, $y );
      my $n    = MatrixNode->new(
          x_position => $x,
          y_position => $y,
          value      => $v,
      );
      $self->_write( $x, $y, $n );
      return $n;
  }

# go through the rows/collums presently available and freeze them into objects.

  sub _build_cells {
      my $self = shift;
      my @out  = ();
      my @rows = @{ $self->{rows} };
      for my $x ( 0 .. $#rows ) {
          next unless defined $self->{rows}->[$x];
          my @col = @{ $self->{rows}->[$x] };
          for my $y ( 0 .. $#col ) {
              next unless defined $self->{rows}->[$x]->[$y];
              Push @out, $self->_convert( $x, $y );
          }
      }
      for my $c (@out) {
          for my $n ( $self->_neighbours( $c->x_position, $c->y_position ) ) {
              $c->add_sibling( $self->{rows}->[ $n->[0] ]->[ $n->[1] ] );
          }
      }
      return \@out;
  }

  # given x,y , return array of points that refer to valid neighbours.
  sub _neighbours {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my @out  = ();
      for my $sx ( -1, 0, 1 ) {
          next if $sx + $x < 0;
          next if not defined $self->{rows}->[ $sx + $x ];
          for my $sy ( -1, 0, 1 ) {
              next if $sx == 0 && $sy == 0;
              next if $sy + $y < 0;
              next if not defined $self->{rows}->[ $sx + $x ]->[ $sy + $y ];
              Push @out, [ $sx + $x, $sy + $y ];
          }
      }
      return @out;
  }

  sub _has_row {
      my $self = shift;
      my $x    = shift;
      return defined $self->{rows}->[$x];
  }

  sub _has_cell {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      return defined $self->{rows}->[$x]->[$y];
  }

  sub _read {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      return $self->{rows}->[$x]->[$y];
  }

  sub _write {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my $v    = shift;
      $self->{rows}->[$x]->[$y] = $v;
      return $v;
  }

  __PACKAGE__->meta->make_immutable;
}

use Tree::Trie;

sub readDict {
  my $fn = shift;
  my $re = shift;
  my $d  = Tree::Trie->new();

  # Dictionary Loading
  open my $fh, '<', $fn;
  while ( my $line = <$fh> ) {
      chomp($line);

 # Commenting the next line makes it go from 1.5 seconds to 7.5 seconds. EPIC.
      next if $line =~ $re;    # Early Filter
      $d->add( uc($line) );
  }
  return $d;
}

sub traverseGraph {
  my $d     = shift;
  my $m     = shift;
  my $min   = shift;
  my $max   = shift;
  my @words = ();

  # Inject all grid nodes into the processing queue.

  my @queue =
    grep { $d->lookup( $_->current_Word ) }
    map  { $_->to_path } @{ $m->cells };

  while (@queue) {
      my $item = shift @queue;

      # put the dictionary into "exact match" mode.

      $d->deepsearch('exact');

      my $cword = $item->current_Word;
      my $l     = length($cword);

      if ( $l >= $min && $d->lookup($cword) ) {
          Push @words,
            $item;    # Push current path into "words" if it exactly matches.
      }
      next if $l > $max;

      # put the dictionary into "is-a-prefix" mode.
      $d->deepsearch('boolean');

    siblingloop: foreach my $sibling ( @{ $item->tail->siblings } ) {
          foreach my $visited ( @{ $item->{path} } ) {
              next siblingloop if $sibling == $visited;
          }

          # given path y , iterate for all its end points
          my $subpath = $item->child($sibling);

          # create a new path for each end-point
          if ( $d->lookup( $subpath->current_Word ) ) {

             # if the new path is a prefix, add it to the bottom of the queue.
              Push @queue, $subpath;
          }
      }
  }
  return \@words;
}

sub setup_predetermined { 
  my $m = shift; 
  my $gameNo = shift;
  if( $gameNo == 0 ){
      $m->add_row(qw( F X I E ));
      $m->add_row(qw( A M L O ));
      $m->add_row(qw( E W B X ));
      $m->add_row(qw( A S T U ));
      return $m;
  }
  if( $gameNo == 1 ){
      $m->add_row(qw( D G H I ));
      $m->add_row(qw( K L P S ));
      $m->add_row(qw( Y E U T ));
      $m->add_row(qw( E O R N ));
      return $m;
  }
}
sub setup_random { 
  my $m = shift; 
  my $seed = shift;
  srand $seed;
  my @letters = 'A' .. 'Z' ; 
  for( 1 .. 4 ){ 
      my @r = ();
      for( 1 .. 4 ){
          Push @r , $letters[int(Rand(25))];
      }
      $m->add_row( @r );
  }
}

# Here is where the real work starts.

my $m = Matrix->new();
setup_predetermined( $m, 0 );
#setup_random( $m, 5 );

my $d = readDict( 'dict.txt', $m->regex );
my $c = scalar @{ $m->cells };    # get the max, as per spec

print join ",\n", map { $_->pp } @{
  traverseGraph( $d, $m, 3, $c ) ;
};

Arch/Execution Info zum Vergleich:

model name      : Intel(R) Core(TM)2 Duo CPU     T9300  @ 2.50GHz
cache size      : 6144 KB
Memory usage summary: heap total: 77057577, heap peak: 11446200, stack peak: 26448
       total calls   total memory   failed calls
 malloc|     947212       68763684              0
realloc|      11191        1045641              0  (nomove:9063, dec:4731, free:0)
 calloc|     121001        7248252              0
   free|     973159       65854762

Histogram for block sizes:
  0-15         392633  36% ==================================================
 16-31          43530   4% =====
 32-47          50048   4% ======
 48-63          70701   6% =========
 64-79          18831   1% ==
 80-95          19271   1% ==
 96-111        238398  22% ==============================
112-127          3007  <1% 
128-143        236727  21% ==============================

Mehr Murren über diese Regex-Optimierung

Die von mir verwendete Regex-Optimierung ist für Wörterbücher mit mehreren Auflösungen nutzlos. Für Wörterbücher mit mehreren Auflösungen benötigen Sie ein vollständiges und kein vorab zugeschnittenes Wörterbuch.

Für einmalige Lösungen ist dies jedoch sehr schnell. (Perl Regex sind in C! :))

Hier sind einige abweichende Code-Ergänzungen:

sub readDict_nofilter {
  my $fn = shift;
  my $re = shift;
  my $d  = Tree::Trie->new();

  # Dictionary Loading
  open my $fh, '<', $fn;
  while ( my $line = <$fh> ) {
      chomp($line);
      $d->add( uc($line) );
  }
  return $d;
}

sub benchmark_io { 
  use Benchmark qw( cmpthese :hireswallclock );
   # generate a random 16 character string 
   # to simulate there being an input grid. 
  my $regexen = sub { 
      my @letters = 'A' .. 'Z' ; 
      my @lo = ();
      for( 1..16 ){ 
          Push @lo , $_ ; 
      }
      my $c  = join '', @lo;
      $c = "[^$c]";
      return qr/$c/i;
  };
  cmpthese( 200 , { 
      filtered => sub { 
          readDict('dict.txt', $regexen->() );
      }, 
      unfiltered => sub {
          readDict_nofilter('dict.txt');
      }
  });
}
 s/iter ungefiltert gefiltert 
 ungefiltert 8,16 - -94% 
 gefiltert 0,464 1658% - 

ps: 8,16 * 200 = 27 Minuten.

39
Kent Fredric

Sie könnten das Problem in zwei Teile aufteilen:

  1. Eine Art Suchalgorithmus, der mögliche Zeichenfolgen im Raster auflistet.
  2. Eine Möglichkeit zum Testen, ob eine Zeichenfolge ein gültiges Word ist.

Idealerweise sollte (2) auch eine Möglichkeit enthalten, zu testen, ob eine Zeichenfolge ein Präfix eines gültigen Words ist. Auf diese Weise können Sie Ihre Suche verkürzen und eine Menge Zeit sparen.

Adam Rosenfields Trie ist eine Lösung zu (2). Es ist elegant und wahrscheinlich das, was Ihr Algorithmus-Spezialist vorziehen würde, aber mit modernen Sprachen und modernen Computern können wir etwas fauler sein. Wie Kent vorschlägt, können wir auch die Größe des Wörterbuchs reduzieren, indem Wörter, deren Buchstaben nicht im Raster vorhanden sind, verworfen werden. Hier ist etwas Python:

def make_lookups(grid, fn='dict.txt'):
    # Make set of valid characters.
    chars = set()
    for Word in grid:
        chars.update(Word)

    words = set(x.strip() for x in open(fn) if set(x.strip()) <= chars)
    prefixes = set()
    for w in words:
        for i in range(len(w)+1):
            prefixes.add(w[:i])

    return words, prefixes

Beeindruckend; Konstantzeit-Präfixprüfung. Es dauert einige Sekunden, um das verknüpfte Wörterbuch zu laden, aber nur ein paar :-) (Beachten Sie, dass words <= prefixes)

Nun, für Teil (1), neige ich dazu, in Form von Diagrammen zu denken. Also werde ich ein Wörterbuch erstellen, das ungefähr so ​​aussieht:

graph = { (x, y):set([(x0,y0), (x1,y1), (x2,y2)]), }

das heißt graph[(x, y)] ist die Menge von Koordinaten, die Sie von Position (x, y) aus erreichen können. Ich füge auch einen Dummy-Knoten None hinzu, der sich mit allem verbindet.

Das Bauen ist etwas ungeschickt, denn es gibt 8 mögliche Positionen und Sie müssen Grenzen überprüfen. Hier ist ein entsprechend unbeholfener Python-Code:

def make_graph(grid):
    root = None
    graph = { root:set() }
    chardict = { root:'' }

    for i, row in enumerate(grid):
        for j, char in enumerate(row):
            chardict[(i, j)] = char
            node = (i, j)
            children = set()
            graph[node] = children
            graph[root].add(node)
            add_children(node, children, grid)

    return graph, chardict

def add_children(node, children, grid):
    x0, y0 = node
    for i in [-1,0,1]:
        x = x0 + i
        if not (0 <= x < len(grid)):
            continue
        for j in [-1,0,1]:
            y = y0 + j
            if not (0 <= y < len(grid[0])) or (i == j == 0):
                continue

            children.add((x,y))

Dieser Code baut auch ein Wörterbuch auf, das (x,y) dem entsprechenden Zeichen zuordnet. So kann ich eine Liste von Positionen in ein Wort umwandeln:

def to_Word(chardict, pos_list):
    return ''.join(chardict[x] for x in pos_list)

Schließlich führen wir eine Tiefensuche durch. Das grundlegende Verfahren ist:

  1. Die Suche kommt an einem bestimmten Knoten an.
  2. Prüfen Sie, ob der Pfad bisher Teil eines Wortes sein könnte. Wenn nicht, erforsche diesen Zweig nicht weiter.
  3. Prüfen Sie, ob der Pfad bisher ein Wort ist. Wenn ja, fügen Sie die Liste der Ergebnisse hinzu.
  4. Erkunde alle Kinder, die bisher noch nicht Teil des Pfads waren.

Python:

def find_words(graph, chardict, position, prefix, results, words, prefixes):
    """ Arguments:
      graph :: mapping (x,y) to set of reachable positions
      chardict :: mapping (x,y) to character
      position :: current position (x,y) -- equals prefix[-1]
      prefix :: list of positions in current string
      results :: set of words found
      words :: set of valid words in the dictionary
      prefixes :: set of valid words or prefixes thereof
    """
    Word = to_Word(chardict, prefix)

    if Word not in prefixes:
        return

    if Word in words:
        results.add(Word)

    for child in graph[position]:
        if child not in prefix:
            find_words(graph, chardict, child, prefix+[child], results, words, prefixes)

Führen Sie den Code aus als:

grid = ['fxie', 'amlo', 'ewbx', 'astu']
g, c = make_graph(grid)
w, p = make_lookups(grid)
res = set()
find_words(g, c, None, [], res, w, p)

und prüfen Sie res, um die Antworten zu sehen. Hier finden Sie eine Liste der gefundenen Wörter für Ihr Beispiel, sortiert nach Größe:

 ['a', 'b', 'e', 'f', 'i', 'l', 'm', 'o', 's', 't',
 'u', 'w', 'x', 'ae', 'am', 'as', 'aw', 'ax', 'bo',
 'bu', 'ea', 'el', 'em', 'es', 'fa', 'ie', 'io', 'li',
 'lo', 'ma', 'me', 'mi', 'oe', 'ox', 'sa', 'se', 'st',
 'tu', 'ut', 'wa', 'we', 'xi', 'aes', 'ame', 'AMI',
 'ase', 'ast', 'awa', 'awe', 'awl', 'blo', 'but', 'elb',
 'Elm', 'fae', 'fam', 'lei', 'lie', 'lim', 'lob', 'lox',
 'mae', 'maw', 'mew', 'mil', 'mix', 'oil', 'olm', 'saw',
 'sea', 'sew', 'swa', 'tub', 'Tux', 'twa', 'wae', 'was',
 'wax', 'wem', 'ambo', 'amil', 'amli', 'asem', 'axil',
 'axle', 'bleo', 'boil', 'bole', 'east', 'fame', 'limb',
 'Lime', 'mesa', 'mewl', 'mile', 'milo', 'oime', 'sawt',
 'seam', 'seax', 'semi', 'stub', 'swam', 'twae', 'twas',
 'wame', 'wase', 'wast', 'weam', 'west', 'amble', 'awest',
 'axile', 'embox', 'limbo', 'limes', 'swami', 'embole',
 'famble', 'semble', 'wamble']

Der Code benötigt (buchstäblich) einige Sekunden, um das Wörterbuch zu laden, aber der Rest ist sofort auf meinem Computer.

33
John Fouhy

Ich denke, Sie werden wahrscheinlich die meiste Zeit damit verbringen, nach Wörtern zu suchen, die mit Ihrem Buchstabenraster unmöglich erstellt werden können. Das erste, was ich tun würde, ist zu versuchen, diesen Schritt zu beschleunigen, und das sollte Sie den größten Teil des Weges dorthin bringen.

Zu diesem Zweck würde ich das Raster als Tabelle möglicher "Züge" wiedergeben, die Sie anhand des betrachteten Buchstabenübergangs indizieren.

Beginnen Sie, indem Sie jedem Buchstaben eine Zahl aus Ihrem gesamten Alphabet zuweisen (A = 0, B = 1, C = 2, ... usw.).

Nehmen wir folgendes Beispiel:

h b c d
e e g h
l l k l
m o f p

Verwenden wir zunächst das Alphabet der Buchstaben, die wir haben (normalerweise möchten Sie wahrscheinlich jedes Mal das gleiche Alphabet verwenden):

 b | c | d | e | f | g | h | k | l | m |  o |  p
---+---+---+---+---+---+---+---+---+---+----+----
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

Dann erstellen Sie ein boolesches 2D-Array, das angibt, ob ein bestimmter Buchstabenübergang verfügbar ist:

     |  0  1  2  3  4  5  6  7  8  9 10 11  <- from letter
     |  b  c  d  e  f  g  h  k  l  m  o  p
-----+--------------------------------------
 0 b |     T     T     T  T     
 1 c |  T     T  T     T  T
 2 d |     T           T  T
 3 e |  T  T     T     T  T  T  T
 4 f |                       T  T     T  T
 5 g |  T  T  T  T        T  T  T
 6 h |  T  T  T  T     T     T  T
 7 k |           T  T  T  T     T     T  T
 8 l |           T  T  T  T  T  T  T  T  T
 9 m |                          T     T
10 o |              T        T  T  T
11 p |              T        T  T
 ^
 to letter

Gehen Sie nun Ihre Wortliste durch und konvertieren Sie die Wörter in Übergänge:

hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10

Überprüfen Sie dann, ob diese Übergänge zulässig sind, indem Sie sie in Ihrer Tabelle nachschlagen:

[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T

Wenn sie alle erlaubt sind, besteht die Möglichkeit, dass dieses Wort gefunden wird.

Beispielsweise kann das Wort "Helm" beim 4. Übergang (m zu e: helMEt) ausgeschlossen werden, da dieser Eintrag in Ihrer Tabelle falsch ist.

Und der Word-Hamster kann ausgeschlossen werden, da der erste Übergang (h zu a) nicht zulässig ist (nicht einmal in Ihrer Tabelle vorhanden).

Versuchen Sie nun, die wahrscheinlich sehr wenigen verbleibenden Wörter, die Sie nicht eliminiert haben, so im Raster zu finden, wie Sie es jetzt tun, oder wie in einigen anderen Antworten hier vorgeschlagen. Dies dient dazu, Fehlalarme zu vermeiden, die durch Sprünge zwischen identischen Buchstaben in Ihrem Raster entstehen. Beispielsweise ist das Wort "help" in der Tabelle zulässig, nicht jedoch im Raster.

Einige weitere Tipps zur Leistungsverbesserung zu dieser Idee:

  1. Verwenden Sie anstelle eines 2D-Arrays ein 1D-Array und berechnen Sie den Index des zweiten Buchstabens einfach selbst. Erstellen Sie also anstelle eines 12x12-Arrays wie oben ein 1D-Array mit der Länge 144. Wenn Sie dann immer dasselbe Alphabet verwenden (dh ein 26x26 = 676x1-Array für das englische Standardalphabet), auch wenn nicht alle Buchstaben in Ihrem Raster angezeigt werden können Sie die Indizes in diesem 1D-Array vorberechnen, die Sie testen müssen, um sie mit Ihren Wörterbuchwörtern abzugleichen. Zum Beispiel wären die Indizes für 'Hallo' im obigen Beispiel

    hello (6, 3, 8, 8, 10):
    42 (from 6 + 3x12), 99, 104, 128
    -> "hello" will be stored as 42, 99, 104, 128 in the dictionary
    
  2. Erweitern Sie die Idee auf eine 3D-Tabelle (ausgedrückt als 1D-Array), d. H. Alle zulässigen Kombinationen aus drei Buchstaben. Auf diese Weise können Sie noch mehr Wörter sofort entfernen und die Anzahl der Array-Lookups für jedes Wort um 1 verringern: Für 'Hallo' benötigen Sie nur 3 Array-Lookups: hel, ell, llo. Es wird übrigens sehr schnell gehen, diese Tabelle zu erstellen, da Ihr Raster nur 400 mögliche 3-Buchstaben-Züge enthält.

  3. Berechnen Sie vorab die Indizes der Züge in Ihrem Raster, die Sie in Ihre Tabelle aufnehmen müssen. Für das obige Beispiel müssen Sie die folgenden Einträge auf 'True' setzen:

    (0,0) (0,1) -> here: h, b : [6][0]
    (0,0) (1,0) -> here: h, e : [6][3]
    (0,0) (1,1) -> here: h, e : [6][3]
    (0,1) (0,0) -> here: b, h : [0][6]
    (0,1) (0,2) -> here: b, c : [0][1]
    .
    :
    
  4. Stellen Sie Ihr Spielraster auch in einem 1-D-Array mit 16 Einträgen dar und lassen Sie die Tabelle in 3 vorberechnen. Enthalten Sie die Indizes in diesem Array.

Ich bin sicher, wenn Sie diesen Ansatz verwenden, kann Ihr Code wahnsinnig schnell ausgeführt werden, wenn Sie das Wörterbuch vorberechnet und bereits in den Speicher geladen haben.

Übrigens: Wenn Sie ein Spiel erstellen, können Sie diese Dinge auch sofort im Hintergrund ausführen. Beginnen Sie mit dem Generieren und Lösen des ersten Spiels, während der Benutzer noch auf den Titelbildschirm Ihrer App blickt und seinen Finger in Position bringt, um "Play" zu drücken. Generieren und lösen Sie dann das nächste Spiel, während der Benutzer das vorherige Spiel spielt. Das sollte Ihnen viel Zeit geben, um Ihren Code auszuführen.

(Ich mag dieses Problem, daher werde ich wahrscheinlich versucht sein, meinen Vorschlag in den nächsten Tagen in Java umzusetzen, um zu sehen, wie er tatsächlich ablaufen würde ... Ich werde den Code hier veröffentlichen, sobald ich das tue .)

UPDATE:

Ok, ich hatte heute etwas Zeit und habe diese Idee in Java umgesetzt:

class DictionaryEntry {
  public int[] letters;
  public int[] triplets;
}

class BoggleSolver {

  // Constants
  final int ALPHABET_SIZE = 5;  // up to 2^5 = 32 letters
  final int BOARD_SIZE    = 4;  // 4x4 board
  final int[] moves = {-BOARD_SIZE-1, -BOARD_SIZE, -BOARD_SIZE+1, 
                                  -1,                         +1,
                       +BOARD_SIZE-1, +BOARD_SIZE, +BOARD_SIZE+1};


  // Technically constant (calculated here for flexibility, but should be fixed)
  DictionaryEntry[] dictionary; // Processed Word list
  int maxWordLength = 0;
  int[] boardTripletIndices; // List of all 3-letter moves in board coordinates

  DictionaryEntry[] buildDictionary(String fileName) throws IOException {
    BufferedReader fileReader = new BufferedReader(new FileReader(fileName));
    String Word = fileReader.readLine();
    ArrayList<DictionaryEntry> result = new ArrayList<DictionaryEntry>();
    while (Word!=null) {
      if (Word.length()>=3) {
        Word = Word.toUpperCase();
        if (Word.length()>maxWordLength) maxWordLength = Word.length();
        DictionaryEntry entry = new DictionaryEntry();
        entry.letters  = new int[Word.length()  ];
        entry.triplets = new int[Word.length()-2];
        int i=0;
        for (char letter: Word.toCharArray()) {
          entry.letters[i] = (byte) letter - 65; // Convert ASCII to 0..25
          if (i>=2)
            entry.triplets[i-2] = (((entry.letters[i-2]  << ALPHABET_SIZE) +
                                     entry.letters[i-1]) << ALPHABET_SIZE) +
                                     entry.letters[i];
          i++;
        }
        result.add(entry);
      }
      Word = fileReader.readLine();
    }
    return result.toArray(new DictionaryEntry[result.size()]);
  }

  boolean isWrap(int a, int b) { // Checks if move a->b wraps board Edge (like 3->4)
    return Math.abs(a%BOARD_SIZE-b%BOARD_SIZE)>1;
  }

  int[] buildTripletIndices() {
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int a=0; a<BOARD_SIZE*BOARD_SIZE; a++)
      for (int bm: moves) {
        int b=a+bm;
        if ((b>=0) && (b<board.length) && !isWrap(a, b))
          for (int cm: moves) {
            int c=b+cm;
            if ((c>=0) && (c<board.length) && (c!=a) && !isWrap(b, c)) {
              result.add(a);
              result.add(b);
              result.add(c);
            }
          }
      }
    int[] result2 = new int[result.size()];
    int i=0;
    for (Integer r: result) result2[i++] = r;
    return result2;
  }


  // Variables that depend on the actual game layout
  int[] board = new int[BOARD_SIZE*BOARD_SIZE]; // Letters in board
  boolean[] possibleTriplets = new boolean[1 << (ALPHABET_SIZE*3)];

  DictionaryEntry[] candidateWords;
  int candidateCount;

  int[] usedBoardPositions;

  DictionaryEntry[] foundWords;
  int foundCount;

  void initializeBoard(String[] letters) {
    for (int row=0; row<BOARD_SIZE; row++)
      for (int col=0; col<BOARD_SIZE; col++)
        board[row*BOARD_SIZE + col] = (byte) letters[row].charAt(col) - 65;
  }

  void setPossibleTriplets() {
    Arrays.fill(possibleTriplets, false); // Reset list
    int i=0;
    while (i<boardTripletIndices.length) {
      int triplet = (((board[boardTripletIndices[i++]]  << ALPHABET_SIZE) +
                       board[boardTripletIndices[i++]]) << ALPHABET_SIZE) +
                       board[boardTripletIndices[i++]];
      possibleTriplets[triplet] = true; 
    }
  }

  void checkWordTriplets() {
    candidateCount = 0;
    for (DictionaryEntry entry: dictionary) {
      boolean ok = true;
      int len = entry.triplets.length;
      for (int t=0; (t<len) && ok; t++)
        ok = possibleTriplets[entry.triplets[t]];
      if (ok) candidateWords[candidateCount++] = entry;
    }
  }

  void checkWords() { // Can probably be optimized a lot
    foundCount = 0;
    for (int i=0; i<candidateCount; i++) {
      DictionaryEntry candidate = candidateWords[i];
      for (int j=0; j<board.length; j++)
        if (board[j]==candidate.letters[0]) { 
          usedBoardPositions[0] = j;
          if (checkNextLetters(candidate, 1, j)) {
            foundWords[foundCount++] = candidate;
            break;
          }
        }
    }
  }

  boolean checkNextLetters(DictionaryEntry candidate, int letter, int pos) {
    if (letter==candidate.letters.length) return true;
    int match = candidate.letters[letter];
    for (int move: moves) {
      int next=pos+move;
      if ((next>=0) && (next<board.length) && (board[next]==match) && !isWrap(pos, next)) {
        boolean ok = true;
        for (int i=0; (i<letter) && ok; i++)
          ok = usedBoardPositions[i]!=next;
        if (ok) {
          usedBoardPositions[letter] = next;
          if (checkNextLetters(candidate, letter+1, next)) return true;
        }
      }
    }   
    return false;
  }


  // Just some helper functions
  String formatTime(long start, long end, long repetitions) {
    long time = (end-start)/repetitions;
    return time/1000000 + "." + (time/100000) % 10 + "" + (time/10000) % 10 + "ms";
  }

  String getWord(DictionaryEntry entry) {
    char[] result = new char[entry.letters.length];
    int i=0;
    for (int letter: entry.letters)
      result[i++] = (char) (letter+97);
    return new String(result);
  }

  void run() throws IOException {
    long start = System.nanoTime();

    // The following can be pre-computed and should be replaced by constants
    dictionary = buildDictionary("C:/TWL06.txt");
    boardTripletIndices = buildTripletIndices();
    long precomputed = System.nanoTime();


    // The following only needs to run once at the beginning of the program
    candidateWords     = new DictionaryEntry[dictionary.length]; // WAAAY too generous
    foundWords         = new DictionaryEntry[dictionary.length]; // WAAAY too generous
    usedBoardPositions = new int[maxWordLength];
    long initialized = System.nanoTime(); 

    for (int n=1; n<=100; n++) {
      // The following needs to run again for every new board
      initializeBoard(new String[] {"DGHI",
                                    "KLPS",
                                    "YEUT",
                                    "EORN"});
      setPossibleTriplets();
      checkWordTriplets();
      checkWords();
    }
    long solved = System.nanoTime();


    // Print out result and statistics
    System.out.println("Precomputation finished in " + formatTime(start, precomputed, 1)+":");
    System.out.println("  Words in the dictionary: "+dictionary.length);
    System.out.println("  Longest Word:            "+maxWordLength+" letters");
    System.out.println("  Number of triplet-moves: "+boardTripletIndices.length/3);
    System.out.println();

    System.out.println("Initialization finished in " + formatTime(precomputed, initialized, 1));
    System.out.println();

    System.out.println("Board solved in "+formatTime(initialized, solved, 100)+":");
    System.out.println("  Number of candidates: "+candidateCount);
    System.out.println("  Number of actual words: "+foundCount);
    System.out.println();

    System.out.println("Words found:");
    int w=0;
    System.out.print("  ");
    for (int i=0; i<foundCount; i++) {
      System.out.print(getWord(foundWords[i]));
      w++;
      if (w==10) {
        w=0;
        System.out.println(); System.out.print("  ");
      } else
        if (i<foundCount-1) System.out.print(", ");
    }
    System.out.println();
  }

  public static void main(String[] args) throws IOException {
    new BoggleSolver().run();
  }
}

Hier sind einige Ergebnisse:

Für das Raster aus dem Bild in der ursprünglichen Frage (DGHI ...):

Precomputation finished in 239.59ms:
  Words in the dictionary: 178590
  Longest Word:            15 letters
  Number of triplet-moves: 408

Initialization finished in 0.22ms

Board solved in 3.70ms:
  Number of candidates: 230
  Number of actual words: 163 

Words found:
  eek, eel, eely, eld, elhi, elk, ern, erupt, erupts, euro
  eye, eyer, ghi, ghis, glee, gley, glue, gluer, gluey, glut
  gluts, hip, hiply, hips, his, hist, kelp, kelps, kep, kepi
  kepis, keps, kept, kern, key, kye, lee, lek, lept, leu
  ley, lunt, lunts, lure, lush, lust, lustre, lye, nus, nut
  nuts, ore, ort, orts, ouph, ouphs, our, oust, out, outre
  outs, oyer, pee, per, pert, phi, phis, pis, pish, plus
  plush, ply, plyer, psi, pst, pul, pule, puler, pun, punt
  punts, pur, pure, puree, purely, pus, Push, put, puts, ree
  rely, rep, reply, reps, roe, roue, roup, roups, roust, rout
  routs, rue, rule, ruly, run, runt, runts, rupee, Rush, Rust
  rut, ruts, ship, shlep, sip, sipe, spue, spun, spur, spurn
  spurt, strep, stroy, stun, stupe, sue, suer, sulk, sulker, sulky
  Sun, sup, supe, super, sure, surely, tree, trek, trey, troupe
  troy, true, truly, tule, tun, tup, tups, turn, tush, ups
  urn, uts, yeld, yelk, Yelp, yelps, yep, yeps, yore, you
  your, yourn, yous

Für die in der ursprünglichen Frage als Beispiel angegebenen Buchstaben (FXIE ...)

Precomputation finished in 239.68ms:
  Words in the dictionary: 178590
  Longest Word:            15 letters
  Number of triplet-moves: 408

Initialization finished in 0.21ms

Board solved in 3.69ms:
  Number of candidates: 87
  Number of actual words: 76

Words found:
  amble, ambo, AMI, amie, asea, awa, awe, awes, awl, axil
  axile, axle, boil, bole, box, but, buts, east, Elm, emboli
  fame, fames, fax, lei, lie, lima, limb, limbo, limbs, Lime
  limes, lob, lobs, lox, mae, maes, maw, maws, max, maxi
  mesa, mew, mewl, mews, mil, mile, milo, mix, oil, ole
  sae, saw, sea, seam, semi, sew, stub, swam, swami, tub
  tubs, Tux, twa, twae, twaes, twas, uts, wae, waes, wamble
  wame, wames, was, wast, wax, west

Für das folgende 5x5-Raster:

R P R I T
A H H L N
I E T E P
Z R Y S G
O G W E Y

es gibt dies:

Precomputation finished in 240.39ms:
  Words in the dictionary: 178590
  Longest Word:            15 letters
  Number of triplet-moves: 768

Initialization finished in 0.23ms

Board solved in 3.85ms:
  Number of candidates: 331
  Number of actual words: 240

Words found:
  aero, aery, ahi, air, airt, airth, airts, airy, ear, egest
  elhi, elint, erg, ergo, ester, eth, ether, eye, eyen, eyer
  eyes, eyre, eyrie, gel, gelt, gelts, gen, gent, gentil, gest
  geste, get, gets, gey, gor, gore, gory, grey, greyest, greys
  gyre, gyri, gyro, hae, haet, haets, hair, hairy, hap, harp
  heap, hear, heh, heir, help, helps, hen, hent, hep, her
  hero, hes, hest, het, hetero, heth, hets, hey, hie, hilt
  hilts, hin, hint, hire, hit, inlet, inlets, ire, leg, leges
  legs, lehr, lent, les, lest, let, lethe, lets, ley, leys
  lin, line, lines, liney, lint, lit, neg, negs, nest, nester
  net, nether, nets, nil, nit, ogre, ore, orgy, ort, orts
  pah, pair, par, peg, pegs, peh, pelt, pelter, peltry, pelts
  pen, pent, pes, pest, pester, pesty, pet, peter, pets, phi
  philter, philtre, phiz, pht, print, pst, rah, rai, rap, raphe
  raphes, reap, rear, rei, ret, rete, rets, rhaphe, rhaphes, rhea
  ria, rile, riles, riley, rin, rye, ryes, seg, sel, sen
  sent, senti, set, sew, spelt, spelter, spent, splent, spline, splint
  split, stent, step, stey, stria, striae, sty, stye, tea, tear
  teg, tegs, tel, ten, tent, thae, the, their, then, these
  thesp, they, thin, thine, thir, thirl, til, tile, tiles, tilt
  tilter, tilth, tilts, tin, tine, tines, tirl, trey, treys, trog
  try, tye, tyer, tyes, tyre, tyro, west, wester, wry, wryest
  wye, wyes, wyte, wytes, yea, yeah, year, yeh, Yelp, yelps
  yen, yep, yeps, yes, yester, yet, yew, yews, zero, zori

Dafür habe ich die TWL06 Tournament Scrabble Word List verwendet, da der Link in der ursprünglichen Frage nicht mehr funktioniert. Diese Datei ist 1,85 MB groß und daher etwas kürzer. Und die Funktion buildDictionary gibt alle Wörter mit weniger als 3 Buchstaben aus.

Hier einige Beobachtungen zur Leistung:

  • Es ist ungefähr 10-mal langsamer als die gemeldete Leistung der OCaml-Implementierung von Victor Nicollet. Unabhängig davon, ob dies durch den unterschiedlichen Algorithmus, das kürzere Wörterbuch, das sein Code kompiliert wurde und meins in einer Java virtuellen Maschine ausgeführt wird, oder durch die Leistung unserer Computer (meins ist ein Intel Q6600 @) verursacht wird. 2.4MHz unter WinXP), ich weiß es nicht. Es ist jedoch viel schneller als die Ergebnisse für die anderen Implementierungen, die am Ende der ursprünglichen Frage aufgeführt sind. Ob dieser Algorithmus dem Trie-Wörterbuch überlegen ist oder nicht, weiß ich zum jetzigen Zeitpunkt nicht.

  • Die in checkWordTriplets() verwendete Tabellenmethode liefert eine sehr gute Annäherung an die tatsächlichen Antworten. Nur 1 von 3 bis 5 Wörtern, die übergeben wurden, besteht den Test checkWords() nicht (Siehe Anzahl der Kandidaten vs. Anzahl der tatsächlichen Wörter über).

  • Was Sie oben nicht sehen können: Die Funktion checkWordTriplets() benötigt ca. 3,65 ms und ist daher im Suchprozess voll dominant. Die Funktion checkWords() nimmt die verbleibenden 0,05-0,20 ms ein.

  • Die Ausführungszeit der Funktion checkWordTriplets() hängt linear von der Dictionary-Größe ab und ist praktisch unabhängig von der Board-Größe!

  • Die Ausführungszeit von checkWords() hängt von der Kartengröße und der Anzahl der Wörter ab, die von checkWordTriplets() nicht ausgeschlossen werden.

  • Die checkWords() -Implementierung oben ist die dümmste erste Version, die ich mir ausgedacht habe. Es ist grundsätzlich überhaupt nicht optimiert. Aber im Vergleich zu checkWordTriplets() ist es für die Gesamtleistung der Anwendung irrelevant, daher habe ich mir darüber keine Sorgen gemacht. Aber , wenn das Board größer wird, wird diese Funktion immer langsamer und wird irgendwann von Bedeutung sein. Dann müsste es auch optimiert werden.

  • Eine nette Sache an diesem Code ist seine Flexibilität:

    • Sie können die Kartengröße einfach ändern: Aktualisieren Sie Zeile 10 und das an initializeBoard() übergebene String-Array.
    • Es unterstützt größere/unterschiedliche Alphabete und kann Dinge wie das Behandeln von 'Qu' als ein Buchstabe ohne Leistungsaufwand handhaben. Dazu müssten Zeile 9 und die Stellen, an denen Zeichen in Zahlen umgewandelt werden, aktualisiert werden (derzeit einfach durch Subtrahieren von 65 vom ASCII -Wert).

Ok, aber ich denke, dass dieser Beitrag jetzt lange genug ist. Ich kann definitiv alle Fragen beantworten, die Sie haben, aber lassen Sie uns das zu den Kommentaren bewegen.

23
Markus A.

Mein Versuch in Java. Es dauert etwa 2 s, um die Datei zu lesen und einen Trie zu erstellen, und etwa 50 ms, um das Rätsel zu lösen. Ich habe das in der Frage verlinkte Wörterbuch verwendet (es enthält einige Wörter, von denen ich nicht wusste, dass sie auf Englisch existieren, wie fae, ima)

0 [main] INFO gineer.bogglesolver.util.Util  - Reading the dictionary
2234 [main] INFO gineer.bogglesolver.util.Util  - Finish reading the dictionary
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAM
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAME
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAMBLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: IMA
2234 [main] INFO gineer.bogglesolver.Solver  - Found: ELI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: Elm
2234 [main] INFO gineer.bogglesolver.Solver  - Found: ELB
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXIL
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXILE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMIL
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMLI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AME
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMBLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMBO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MIX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MILE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MILO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MEW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MEWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MESA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: Lime
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMBO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMBU
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LEI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LEO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LOB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LOX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OIME
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OLM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMBOLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMBOX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EAST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAF
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAME
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAMBLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAS
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WASE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BLEO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BLO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BOIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BOLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BUT
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: ASE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: ASEM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEMI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEMBLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWAMI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SAW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SAWT
2250 [main] INFO gineer.bogglesolver.Solver  - Found: STU
2250 [main] INFO gineer.bogglesolver.Solver  - Found: STUB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAS
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TUB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: Tux

Der Quellcode besteht aus 6 Klassen. Ich werde sie unten posten (falls dies nicht die richtige Vorgehensweise für StackOverflow ist, bitte sagen Sie es mir).

gineer.bogglesolver.Main

package gineer.bogglesolver;

import org.Apache.log4j.BasicConfigurator;
import org.Apache.log4j.Logger;

public class Main
{
    private final static Logger logger = Logger.getLogger(Main.class);

    public static void main(String[] args)
    {
        BasicConfigurator.configure();

        Solver solver = new Solver(4,
                        "FXIE" +
                        "AMLO" +
                        "EWBX" +
                        "ASTU");
        solver.solve();

    }
}

gineer.bogglesolver.Solver

package gineer.bogglesolver;

import gineer.bogglesolver.trie.Trie;
import gineer.bogglesolver.util.Constants;
import gineer.bogglesolver.util.Util;
import org.Apache.log4j.Logger;

public class Solver
{
    private char[] puzzle;
    private int maxSize;

    private boolean[] used;
    private StringBuilder stringSoFar;

    private boolean[][] matrix;
    private Trie trie;

    private final static Logger logger = Logger.getLogger(Solver.class);

    public Solver(int size, String puzzle)
    {
        trie = Util.getTrie(size);
        matrix = Util.connectivityMatrix(size);

        maxSize = size * size;
        stringSoFar = new StringBuilder(maxSize);
        used = new boolean[maxSize];

        if (puzzle.length() == maxSize)
        {
            this.puzzle = puzzle.toCharArray();
        }
        else
        {
            logger.error("The puzzle size does not match the size specified: " + puzzle.length());
            this.puzzle = puzzle.substring(0, maxSize).toCharArray();
        }
    }

    public void solve()
    {
        for (int i = 0; i < maxSize; i++)
        {
            traverseAt(i);
        }
    }

    private void traverseAt(int Origin)
    {
        stringSoFar.append(puzzle[Origin]);
        used[Origin] = true;

        //Check if we have a valid Word
        if ((stringSoFar.length() >= Constants.MINIMUM_Word_LENGTH) && (trie.containKey(stringSoFar.toString())))
        {
            logger.info("Found: " + stringSoFar.toString());
        }

        //Find where to go next
        for (int destination = 0; destination < maxSize; destination++)
        {
            if (matrix[Origin][destination] && !used[destination] && trie.containPrefix(stringSoFar.toString() + puzzle[destination]))
            {
                traverseAt(destination);
            }
        }

        used[Origin] = false;
        stringSoFar.deleteCharAt(stringSoFar.length() - 1);
    }

}

gineer.bogglesolver.trie.Node

package gineer.bogglesolver.trie;

import gineer.bogglesolver.util.Constants;

class Node
{
    Node[] children;
    boolean isKey;

    public Node()
    {
        isKey = false;
        children = new Node[Constants.NUMBER_LETTERS_IN_ALPHABET];
    }

    public Node(boolean key)
    {
        isKey = key;
        children = new Node[Constants.NUMBER_LETTERS_IN_ALPHABET];
    }

    /**
     Method to insert a string to Node and its children

     @param key the string to insert (the string is assumed to be uppercase)
     @return true if the node or one of its children is changed, false otherwise
     */
    public boolean insert(String key)
    {
        //If the key is empty, this node is a key
        if (key.length() == 0)
        {
            if (isKey)
                return false;
            else
            {
                isKey = true;
                return true;
            }
        }
        else
        {//otherwise, insert in one of its child

            int childNodePosition = key.charAt(0) - Constants.LETTER_A;
            if (children[childNodePosition] == null)
            {
                children[childNodePosition] = new Node();
                children[childNodePosition].insert(key.substring(1));
                return true;
            }
            else
            {
                return children[childNodePosition].insert(key.substring(1));
            }
        }
    }

    /**
     Returns whether key is a valid prefix for certain key in this trie.
     For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell", "hello" return true

     @param prefix the prefix to check
     @return true if the prefix is valid, false otherwise
     */
    public boolean containPrefix(String prefix)
    {
        //If the prefix is empty, return true
        if (prefix.length() == 0)
        {
            return true;
        }
        else
        {//otherwise, check in one of its child
            int childNodePosition = prefix.charAt(0) - Constants.LETTER_A;
            return children[childNodePosition] != null && children[childNodePosition].containPrefix(prefix.substring(1));
        }
    }

    /**
     Returns whether key is a valid key in this trie.
     For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell" return false

     @param key the key to check
     @return true if the key is valid, false otherwise
     */
    public boolean containKey(String key)
    {
        //If the prefix is empty, return true
        if (key.length() == 0)
        {
            return isKey;
        }
        else
        {//otherwise, check in one of its child
            int childNodePosition = key.charAt(0) - Constants.LETTER_A;
            return children[childNodePosition] != null && children[childNodePosition].containKey(key.substring(1));
        }
    }

    public boolean isKey()
    {
        return isKey;
    }

    public void setKey(boolean key)
    {
        isKey = key;
    }
}

gineer.bogglesolver.trie.Trie

package gineer.bogglesolver.trie;

public class Trie
{
    Node root;

    public Trie()
    {
        this.root = new Node();
    }

    /**
     Method to insert a string to Node and its children

     @param key the string to insert (the string is assumed to be uppercase)
     @return true if the node or one of its children is changed, false otherwise
     */
    public boolean insert(String key)
    {
        return root.insert(key.toUpperCase());
    }

    /**
     Returns whether key is a valid prefix for certain key in this trie.
     For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell", "hello" return true

     @param prefix the prefix to check
     @return true if the prefix is valid, false otherwise
     */
    public boolean containPrefix(String prefix)
    {
        return root.containPrefix(prefix.toUpperCase());
    }

    /**
     Returns whether key is a valid key in this trie.
     For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell" return false

     @param key the key to check
     @return true if the key is valid, false otherwise
     */
    public boolean containKey(String key)
    {
        return root.containKey(key.toUpperCase());
    }


}

gineer.bogglesolver.util.Constants

package gineer.bogglesolver.util;

public class Constants
{

    public static final int NUMBER_LETTERS_IN_ALPHABET = 26;
    public static final char LETTER_A = 'A';
    public static final int MINIMUM_Word_LENGTH = 3;
    public static final int DEFAULT_PUZZLE_SIZE = 4;
}

gineer.bogglesolver.util.Bis

package gineer.bogglesolver.util;

import gineer.bogglesolver.trie.Trie;
import org.Apache.log4j.Logger;

import Java.io.File;
import Java.io.FileNotFoundException;
import Java.util.Scanner;

public class Util
{
    private final static Logger logger = Logger.getLogger(Util.class);
    private static Trie trie;
    private static int size = Constants.DEFAULT_PUZZLE_SIZE;

    /**
     Returns the trie built from the dictionary.  The size is used to eliminate words that are too long.

     @param size the size of puzzle.  The maximum lenght of words in the returned trie is (size * size)
     @return the trie that can be used for puzzle of that size
     */
    public static Trie getTrie(int size)
    {
        if ((trie != null) && size == Util.size)
            return trie;

        trie = new Trie();
        Util.size = size;

        logger.info("Reading the dictionary");
        final File file = new File("dictionary.txt");
        try
        {
            Scanner scanner = new Scanner(file);
            final int maxSize = size * size;
            while (scanner.hasNext())
            {
                String line = scanner.nextLine().replaceAll("[^\\p{Alpha}]", "");

                if (line.length() <= maxSize)
                    trie.insert(line);
            }
        }
        catch (FileNotFoundException e)
        {
            logger.error("Cannot open file", e);
        }

        logger.info("Finish reading the dictionary");
        return trie;
    }

    static boolean[] connectivityRow(int x, int y, int size)
    {
        boolean[] squares = new boolean[size * size];
        for (int offsetX = -1; offsetX <= 1; offsetX++)
        {
            for (int offsetY = -1; offsetY <= 1; offsetY++)
            {
                final int calX = x + offsetX;
                final int calY = y + offsetY;
                if ((calX >= 0) && (calX < size) && (calY >= 0) && (calY < size))
                    squares[calY * size + calX] = true;
            }
        }

        squares[y * size + x] = false;//the current x, y is false

        return squares;
    }

    /**
     Returns the matrix of connectivity between two points.  Point i can go to point j iff matrix[i][j] is true
     Square (x, y) is equivalent to point (size * y + x).  For example, square (1,1) is point 5 in a puzzle of size 4

     @param size the size of the puzzle
     @return the connectivity matrix
     */
    public static boolean[][] connectivityMatrix(int size)
    {
        boolean[][] matrix = new boolean[size * size][];
        for (int x = 0; x < size; x++)
        {
            for (int y = 0; y < size; y++)
            {
                matrix[y * size + x] = connectivityRow(x, y, size);
            }
        }
        return matrix;
    }
}
23
gineer

Überraschenderweise versuchte niemand eine PHP -Version davon.

Dies ist eine funktionierende PHP Version von John Fouhys Python-Lösung.

Obwohl ich einige Hinweise aus den Antworten aller anderen genommen habe, werden diese größtenteils von John kopiert. 

$boggle = "fxie
           amlo
           ewbx
           astu";

$alphabet = str_split(str_replace(array("\n", " ", "\r"), "", strtolower($boggle)));
$rows = array_map('trim', explode("\n", $boggle));
$dictionary = file("C:/dict.txt");
$prefixes = array(''=>'');
$words = array();
$regex = '/[' . implode('', $alphabet) . ']{3,}$/S';
foreach($dictionary as $k=>$value) {
    $value = trim(strtolower($value));
    $length = strlen($value);
    if(preg_match($regex, $value)) {
        for($x = 0; $x < $length; $x++) {
            $letter = substr($value, 0, $x+1);
            if($letter == $value) {
                $words[$value] = 1;
            } else {
                $prefixes[$letter] = 1;
            }
        }
    }
}

$graph = array();
$chardict = array();
$positions = array();
$c = count($rows);
for($i = 0; $i < $c; $i++) {
    $l = strlen($rows[$i]);
    for($j = 0; $j < $l; $j++) {
        $chardict[$i.','.$j] = $rows[$i][$j];
        $children = array();
        $pos = array(-1,0,1);
        foreach($pos as $z) {
            $xCoord = $z + $i;
            if($xCoord < 0 || $xCoord >= count($rows)) {
                continue;
            }
            $len = strlen($rows[0]);
            foreach($pos as $w) {
                $yCoord = $j + $w;
                if(($yCoord < 0 || $yCoord >= $len) || ($z == 0 && $w == 0)) {
                    continue;
                }
                $children[] = array($xCoord, $yCoord);
            }
        }
        $graph['None'][] = array($i, $j);
        $graph[$i.','.$j] = $children;
    }
}

function to_Word($chardict, $prefix) {
    $Word = array();
    foreach($prefix as $v) {
        $Word[] = $chardict[$v[0].','.$v[1]];
    }
    return implode("", $Word);
}

function find_words($graph, $chardict, $position, $prefix, $prefixes, &$results, $words) {
    $Word = to_Word($chardict, $prefix);
    if(!isset($prefixes[$Word])) return false;

    if(isset($words[$Word])) {
        $results[] = $Word;
    }

    foreach($graph[$position] as $child) {
        if(!in_array($child, $prefix)) {
            $newprefix = $prefix;
            $newprefix[] = $child;
            find_words($graph, $chardict, $child[0].','.$child[1], $newprefix, $prefixes, $results, $words);
        }
    }
}

$solution = array();
find_words($graph, $chardict, 'None', array(), $prefixes, $solution);
print_r($solution);

Hier ist ein Live Link wenn Sie es ausprobieren möchten. Obwohl es auf meinem lokalen Rechner ~ 2s dauert, dauert es auf meinem Webserver ~ 5s. In beiden Fällen ist es nicht sehr schnell. Trotzdem ist es ziemlich abscheulich, so dass ich mir vorstellen kann, dass die Zeit deutlich reduziert werden kann. Alle Hinweise, wie dies zu erreichen ist, werden geschätzt. Das Fehlen von Tupeln von PHP machte die Koordinaten seltsam zum Arbeiten, und meine Unfähigkeit, zu verstehen, was zum Teufel vor sich geht, half überhaupt nicht.

EDIT: Ein paar Korrekturen erfordern lokal weniger als 1s.

19

Kein Interesse an VB? :) Ich konnte nicht widerstehen. Ich habe das anders gelöst als viele der hier vorgestellten Lösungen.

Meine Zeiten sind:

  • Laden des Wörterbuchs und der Word-Präfixe in eine Hashtabelle: 0,5 bis 1 Sekunden.
  • Wörter finden: Durchschnitt unter 10 Millisekunden.

BEARBEITEN: Die Ladezeiten der Wörterbücher auf dem Webhostserver laufen etwa 1 bis 1,5 Sekunden länger als bei meinem Heimcomputer.

Ich weiß nicht, wie stark sich die Zeiten mit einer Belastung des Servers verschlechtern werden.

Ich habe meine Lösung als Webseite in .Net geschrieben. myvrad.com/boggle

Ich verwende das Wörterbuch, auf das in der ursprünglichen Frage verwiesen wurde.

Buchstaben werden in einem Wort nicht wiederverwendet. Es werden nur Wörter mit 3 Zeichen oder mehr gefunden.

Ich verwende eine Hashtabelle aller eindeutigen Word-Präfixe und Wörter anstelle eines Tries. Ich wusste nichts von Tries, also habe ich dort etwas gelernt. Die Idee, eine Liste von Präfixen von Wörtern zusätzlich zu den vollständigen Wörtern zu erstellen, hat meine Zeiten schließlich auf eine respektable Anzahl gebracht.

Lesen Sie die Code-Kommentare für weitere Details.

Hier ist der Code:

Imports System.Collections.Generic
Imports System.IO

Partial Class boggle_Default

    'Bob Archer, 4/15/2009

    'To avoid using a 2 dimensional array in VB I'm not using typical X,Y
    'coordinate iteration to find paths.
    '
    'I have locked the code into a 4 by 4 grid laid out like so:
    ' abcd
    ' efgh
    ' ijkl
    ' mnop
    ' 
    'To find paths the code starts with a letter from a to p then
    'explores the paths available around it. If a neighboring letter
    'already exists in the path then we don't go there.
    '
    'Neighboring letters (grid points) are hard coded into
    'a Generic.Dictionary below.



    'Paths is a list of only valid Paths found. 
    'If a Word prefix or Word is not found the path is not
    'added and extending that path is terminated.
    Dim Paths As New Generic.List(Of String)

    'NeighborsOf. The keys are the letters a to p.
    'The value is a string of letters representing neighboring letters.
    'The string of neighboring letters is split and iterated later.
    Dim NeigborsOf As New Generic.Dictionary(Of String, String)

    'BoggleLetters. The keys are mapped to the lettered grid of a to p.
    'The values are what the user inputs on the page.
    Dim BoggleLetters As New Generic.Dictionary(Of String, String)

    'Used to store last postition of path. This will be a letter
    'from a to p.
    Dim LastPositionOfPath As String = ""

    'I found a HashTable was by far faster than a Generic.Dictionary 
    ' - about 10 times faster. This stores prefixes of words and words.
    'I determined 792773 was the number of words and unique prefixes that
    'will be generated from the dictionary file. This is a max number and
    'the final hashtable will not have that many.
    Dim HashTableOfPrefixesAndWords As New Hashtable(792773)

    'Stores words that are found.
    Dim FoundWords As New Generic.List(Of String)

    'Just to validate what the user enters in the grid.
    Dim ErrorFoundWithSubmittedLetters As Boolean = False

    Public Sub BuildAndTestPathsAndFindWords(ByVal ThisPath As String)
        'Word is the Word correlating to the ThisPath parameter.
        'This path would be a series of letters from a to p.
        Dim Word As String = ""

        'The path is iterated through and a Word based on the actual
        'letters in the Boggle grid is assembled.
        For i As Integer = 0 To ThisPath.Length - 1
            Word += Me.BoggleLetters(ThisPath.Substring(i, 1))
        Next

        'If my hashtable of Word prefixes and words doesn't contain this Word
        'Then this isn't a Word and any further extension of ThisPath will not
        'yield any words either. So exit sub to terminate exploring this path.
        If Not HashTableOfPrefixesAndWords.ContainsKey(Word) Then Exit Sub

        'The value of my hashtable is a boolean representing if the key if a Word (true) or
        'just a prefix (false). If true and at least 3 letters long then yay! Word found.
        If HashTableOfPrefixesAndWords(Word) AndAlso Word.Length > 2 Then Me.FoundWords.Add(Word)

        'If my List of Paths doesn't contain ThisPath then add it.
        'Remember only valid paths will make it this far. Paths not found
        'in the HashTableOfPrefixesAndWords cause this sub to exit above.
        If Not Paths.Contains(ThisPath) Then Paths.Add(ThisPath)

        'Examine the last letter of ThisPath. We are looking to extend the path
        'to our neighboring letters if any are still available.
        LastPositionOfPath = ThisPath.Substring(ThisPath.Length - 1, 1)

        'Loop through my list of neighboring letters (representing grid points).
        For Each Neighbor As String In Me.NeigborsOf(LastPositionOfPath).ToCharArray()
            'If I find a neighboring grid point that I haven't already used
            'in ThisPath then extend ThisPath and feed the new path into
            'this recursive function. (see recursive.)
            If Not ThisPath.Contains(Neighbor) Then Me.BuildAndTestPathsAndFindWords(ThisPath & Neighbor)
        Next
    End Sub

    Protected Sub ButtonBoggle_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles ButtonBoggle.Click

        'User has entered the 16 letters and clicked the go button.

        'Set up my Generic.Dictionary of grid points, I'm using letters a to p -
        'not an x,y grid system.  The values are neighboring points.
        NeigborsOf.Add("a", "bfe")
        NeigborsOf.Add("b", "cgfea")
        NeigborsOf.Add("c", "dhgfb")
        NeigborsOf.Add("d", "hgc")
        NeigborsOf.Add("e", "abfji")
        NeigborsOf.Add("f", "abcgkjie")
        NeigborsOf.Add("g", "bcdhlkjf")
        NeigborsOf.Add("h", "cdlkg")
        NeigborsOf.Add("i", "efjnm")
        NeigborsOf.Add("j", "efgkonmi")
        NeigborsOf.Add("k", "fghlponj")
        NeigborsOf.Add("l", "ghpok")
        NeigborsOf.Add("m", "ijn")
        NeigborsOf.Add("n", "ijkom")
        NeigborsOf.Add("o", "jklpn")
        NeigborsOf.Add("p", "klo")

        'Retrieve letters the user entered.
        BoggleLetters.Add("a", Me.TextBox1.Text.ToLower.Trim())
        BoggleLetters.Add("b", Me.TextBox2.Text.ToLower.Trim())
        BoggleLetters.Add("c", Me.TextBox3.Text.ToLower.Trim())
        BoggleLetters.Add("d", Me.TextBox4.Text.ToLower.Trim())
        BoggleLetters.Add("e", Me.TextBox5.Text.ToLower.Trim())
        BoggleLetters.Add("f", Me.TextBox6.Text.ToLower.Trim())
        BoggleLetters.Add("g", Me.TextBox7.Text.ToLower.Trim())
        BoggleLetters.Add("h", Me.TextBox8.Text.ToLower.Trim())
        BoggleLetters.Add("i", Me.TextBox9.Text.ToLower.Trim())
        BoggleLetters.Add("j", Me.TextBox10.Text.ToLower.Trim())
        BoggleLetters.Add("k", Me.TextBox11.Text.ToLower.Trim())
        BoggleLetters.Add("l", Me.TextBox12.Text.ToLower.Trim())
        BoggleLetters.Add("m", Me.TextBox13.Text.ToLower.Trim())
        BoggleLetters.Add("n", Me.TextBox14.Text.ToLower.Trim())
        BoggleLetters.Add("o", Me.TextBox15.Text.ToLower.Trim())
        BoggleLetters.Add("p", Me.TextBox16.Text.ToLower.Trim())

        'Validate user entered something with a length of 1 for all 16 textboxes.
        For Each S As String In BoggleLetters.Keys
            If BoggleLetters(S).Length <> 1 Then
                ErrorFoundWithSubmittedLetters = True
                Exit For
            End If
        Next

        'If input is not valid then...
        If ErrorFoundWithSubmittedLetters Then
            'Present error message.
        Else
            'Else assume we have 16 letters to work with and start finding words.
            Dim SB As New StringBuilder

            Dim Time As String = String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString())

            Dim NumOfLetters As Integer = 0
            Dim Word As String = ""
            Dim TempWord As String = ""
            Dim Letter As String = ""
            Dim fr As StreamReader = Nothing
            fr = New System.IO.StreamReader(HttpContext.Current.Request.MapPath("~/boggle/dic.txt"))

            'First fill my hashtable with Word prefixes and words.
            'HashTable(PrefixOrWordString, BooleanTrueIfWordFalseIfPrefix)
            While fr.Peek <> -1
                Word = fr.ReadLine.Trim()
                TempWord = ""
                For i As Integer = 0 To Word.Length - 1
                    Letter = Word.Substring(i, 1)
                    'This optimization helped quite a bit. Words in the dictionary that begin
                    'with letters that the user did not enter in the grid shouldn't go in my hashtable.
                    '
                    'I realize most of the solutions went with a Trie. I'd never heard of that before,
                    'which is one of the neat things about SO, seeing how others approach challenges
                    'and learning some best practices.
                    '
                    'However, I didn't code a Trie in my solution. I just have a hashtable with 
                    'all words in the dicitonary file and all possible prefixes for those words.
                    'A Trie might be faster but I'm not coding it now. I'm getting good times with this.
                    If i = 0 AndAlso Not BoggleLetters.ContainsValue(Letter) Then Continue While
                    TempWord += Letter
                    If Not HashTableOfPrefixesAndWords.ContainsKey(TempWord) Then
                        HashTableOfPrefixesAndWords.Add(TempWord, TempWord = Word)
                    End If
                Next
            End While

            SB.Append("Number of Word Prefixes and Words in Hashtable: " & HashTableOfPrefixesAndWords.Count.ToString())
            SB.Append("<br />")

            SB.Append("Loading Dictionary: " & Time & " - " & String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString()))
            SB.Append("<br />")

            Time = String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString())

            'This starts a path at each point on the grid an builds a path until 
            'the string of letters correlating to the path is not found in the hashtable
            'of Word prefixes and words.
            Me.BuildAndTestPathsAndFindWords("a")
            Me.BuildAndTestPathsAndFindWords("b")
            Me.BuildAndTestPathsAndFindWords("c")
            Me.BuildAndTestPathsAndFindWords("d")
            Me.BuildAndTestPathsAndFindWords("e")
            Me.BuildAndTestPathsAndFindWords("f")
            Me.BuildAndTestPathsAndFindWords("g")
            Me.BuildAndTestPathsAndFindWords("h")
            Me.BuildAndTestPathsAndFindWords("i")
            Me.BuildAndTestPathsAndFindWords("j")
            Me.BuildAndTestPathsAndFindWords("k")
            Me.BuildAndTestPathsAndFindWords("l")
            Me.BuildAndTestPathsAndFindWords("m")
            Me.BuildAndTestPathsAndFindWords("n")
            Me.BuildAndTestPathsAndFindWords("o")
            Me.BuildAndTestPathsAndFindWords("p")

            SB.Append("Finding Words: " & Time & " - " & String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString()))
            SB.Append("<br />")

            SB.Append("Num of words found: " & FoundWords.Count.ToString())
            SB.Append("<br />")
            SB.Append("<br />")

            FoundWords.Sort()
            SB.Append(String.Join("<br />", FoundWords.ToArray()))

            'Output results.
            Me.LiteralBoggleResults.Text = SB.ToString()
            Me.PanelBoggleResults.Visible = True

        End If

    End Sub

End Class
16
rvarcher

Sobald ich die Problemstellung gesehen hatte, dachte ich an "Trie". Aber da mehrere andere Poster von diesem Ansatz Gebrauch machten, suchte ich nach einem anderen Ansatz, nur um anders zu sein. Leider ist der Trie-Ansatz besser. Ich habe Kent's Perl-Lösung auf meinem Rechner ausgeführt und es dauerte 0,31 Sekunden, nachdem ich die Wörterbuchdatei verwendet hatte. Meine eigene Perl-Implementierung benötigt 0,54 Sekunden zum Ausführen. 

Das war mein Ansatz:

  1. Erstellen Sie einen Übergangshash, um die rechtlichen Übergänge zu modellieren.

  2. Durchlaufe alle 16 ^ 3 möglichen drei Buchstabenkombinationen.

    • Schließen Sie in der Schleife illegale Übergänge aus und wiederholen Sie Besuche auf demselben Platz Bilden Sie alle legalen 3-Buchstaben-Sequenzen und speichern Sie sie in einem Hash.
  3. Führen Sie dann alle Wörter im Wörterbuch durch.

    • Schließen Sie Wörter aus, die zu lang oder zu kurz sind
    • Schieben Sie ein Fenster mit 3 Buchstaben über jedes Wort und sehen Sie, ob es sich in Schritt 3 für die 3-Buchstaben-Kombos befindet. Schließen Sie die fehlgeschlagenen Wörter aus. Dadurch werden die meisten Nichtübereinstimmungen eliminiert.
    • Wenn noch nicht beseitigt, verwenden Sie einen rekursiven Algorithmus, um zu sehen, ob das Wort gebildet werden kann, indem Sie Pfade durch das Rätsel machen. (Dieser Teil ist langsam, wird aber selten aufgerufen.)
  4. Drucken Sie die gefundenen Wörter aus.

    Ich habe 3-Buchstaben- und 4-Buchstaben-Sequenzen ausprobiert, aber 4-Buchstaben-Sequenzen haben das Programm verlangsamt.

In meinem Code verwende ich/usr/share/dict/words für mein Wörterbuch. Es ist Standard für MAC OS X und viele Unix-Systeme. Sie können eine andere Datei verwenden, wenn Sie möchten. Um ein anderes Puzzle zu knacken, ändere einfach die Variable @puzzle. Dies ist für größere Matrizen leicht anpassbar. Sie müssen lediglich den Hashwert% transitions und den% legalTransitions-Hashwert ändern. 

Die Stärke dieser Lösung ist, dass der Code kurz ist und die Datenstrukturen einfach sind.

Hier ist der Perl-Code (der zu viele globale Variablen verwendet, weiß ich):

#!/usr/bin/Perl
use Time::HiRes  qw{ time };

sub readFile($);
sub findAllPrefixes($);
sub isWordTraceable($);
sub findWordsInPuzzle(@);

my $startTime = time;

# Puzzle to solve

my @puzzle = ( 
    F, X, I, E,
    A, M, L, O,
    E, W, B, X,
    A, S, T, U
);

my $minimumWordLength = 3;
my $maximumPrefixLength = 3; # I tried four and it slowed down.

# Slurp the Word list.
my $wordlistFile = "/usr/share/dict/words";

my @words = split(/\n/, uc(readFile($wordlistFile)));
print "Words loaded from Word list: " . scalar @words . "\n";

print "Word file load time: " . (time - $startTime) . "\n";
my $postLoad = time;

# Define the legal transitions from one letter position to another. 
# Positions are numbered 0-15.
#     0  1  2  3
#     4  5  6  7
#     8  9 10 11
#    12 13 14 15
my %transitions = ( 
   -1 => [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
    0 => [1,4,5], 
    1 => [0,2,4,5,6],
    2 => [1,3,5,6,7],
    3 => [2,6,7],
    4 => [0,1,5,8,9],
    5 => [0,1,2,4,6,8,9,10],
    6 => [1,2,3,5,7,9,10,11],
    7 => [2,3,6,10,11],
    8 => [4,5,9,12,13],
    9 => [4,5,6,8,10,12,13,14],
    10 => [5,6,7,9,11,13,14,15],
    11 => [6,7,10,14,15],
    12 => [8,9,13],
    13 => [8,9,10,12,14],
    14 => [9,10,11,13,15],
    15 => [10,11,14]
);

# Convert the transition matrix into a hash for easy access.
my %legalTransitions = ();
foreach my $start (keys %transitions) {
    my $legalRef = $transitions{$start};
    foreach my $stop (@$legalRef) {
        my $index = ($start + 1) * (scalar @puzzle) + ($stop + 1);
        $legalTransitions{$index} = 1;
    }
}

my %prefixesInPuzzle = findAllPrefixes($maximumPrefixLength);

print "Find prefixes time: " . (time - $postLoad) . "\n";
my $postPrefix = time;

my @wordsFoundInPuzzle = findWordsInPuzzle(@words);

print "Find words in puzzle time: " . (time - $postPrefix) . "\n";

print "Unique prefixes found: " . (scalar keys %prefixesInPuzzle) . "\n";
print "Words found (" . (scalar @wordsFoundInPuzzle) . ") :\n    " . join("\n    ", @wordsFoundInPuzzle) . "\n";

print "Total Elapsed time: " . (time - $startTime) . "\n";

###########################################

sub readFile($) {
    my ($filename) = @_;
    my $contents;
    if (-e $filename) {
        # This is magic: it opens and reads a file into a scalar in one line of code. 
        # See http://www.Perl.com/pub/a/2003/11/21/Slurp.html
        $contents = do { local( @ARGV, $/ ) = $filename ; <> } ; 
    }
    else {
        $contents = '';
    }
    return $contents;
}

# Is it legal to move from the first position to the second? They must be adjacent.
sub isLegalTransition($$) {
    my ($pos1,$pos2) = @_;
    my $index = ($pos1 + 1) * (scalar @puzzle) + ($pos2 + 1);
    return $legalTransitions{$index};
}

# Find all prefixes where $minimumWordLength <= length <= $maxPrefixLength
#
#   $maxPrefixLength ... Maximum length of prefix we will store. Three gives best performance. 
sub findAllPrefixes($) {
    my ($maxPrefixLength) = @_;
    my %prefixes = ();
    my $puzzleSize = scalar @puzzle;

    # Every possible N-letter combination of the letters in the puzzle 
    # can be represented as an integer, though many of those combinations
    # involve illegal transitions, duplicated letters, etc.
    # Iterate through all those possibilities and eliminate the illegal ones.
    my $maxIndex = $puzzleSize ** $maxPrefixLength;

    for (my $i = 0; $i < $maxIndex; $i++) {
        my @path;
        my $remainder = $i;
        my $prevPosition = -1;
        my $prefix = '';
        my %usedPositions = ();
        for (my $prefixLength = 1; $prefixLength <= $maxPrefixLength; $prefixLength++) {
            my $position = $remainder % $puzzleSize;

            # Is this a valid step?
            #  a. Is the transition legal (to an adjacent square)?
            if (! isLegalTransition($prevPosition, $position)) {
                last;
            }

            #  b. Have we repeated a square?
            if ($usedPositions{$position}) {
                last;
            }
            else {
                $usedPositions{$position} = 1;
            }

            # Record this prefix if length >= $minimumWordLength.
            $prefix .= $puzzle[$position];
            if ($prefixLength >= $minimumWordLength) {
                $prefixes{$prefix} = 1;
            }

            Push @path, $position;
            $remainder -= $position;
            $remainder /= $puzzleSize;
            $prevPosition = $position;
        } # end inner for
    } # end outer for
    return %prefixes;
}

# Loop through all words in dictionary, looking for ones that are in the puzzle.
sub findWordsInPuzzle(@) {
    my @allWords = @_;
    my @wordsFound = ();
    my $puzzleSize = scalar @puzzle;
Word: foreach my $Word (@allWords) {
        my $wordLength = length($Word);
        if ($wordLength > $puzzleSize || $wordLength < $minimumWordLength) {
            # Reject Word as too short or too long.
        }
        elsif ($wordLength <= $maximumPrefixLength ) {
            # Word should be in the prefix hash.
            if ($prefixesInPuzzle{$Word}) {
                Push @wordsFound, $Word;
            }
        }
        else {
            # Scan through the Word using a window of length $maximumPrefixLength, looking for any strings not in our prefix list.
            # If any are found that are not in the list, this Word is not possible.
            # If no non-matches are found, we have more work to do.
            my $limit = $wordLength - $maximumPrefixLength + 1;
            for (my $startIndex = 0; $startIndex < $limit; $startIndex ++) {
                if (! $prefixesInPuzzle{substr($Word, $startIndex, $maximumPrefixLength)}) {
                    next Word;
                }
            }
            if (isWordTraceable($Word)) {
                # Additional test necessary: see if we can form this Word by following legal transitions
                Push @wordsFound, $Word;
            }
        }

    }
    return @wordsFound;
}

# Is it possible to trace out the Word using only legal transitions?
sub isWordTraceable($) {
    my $Word = shift;
    return traverse([split(//, $Word)], [-1]); # Start at special square -1, which may transition to any square in the puzzle.
}

# Recursively look for a path through the puzzle that matches the Word.
sub traverse($$) {
    my ($lettersRef, $pathRef) = @_;
    my $index = scalar @$pathRef - 1;
    my $position = $pathRef->[$index];
    my $letter = $lettersRef->[$index];
    my $branchesRef =  $transitions{$position};
BRANCH: foreach my $branch (@$branchesRef) {
            if ($puzzle[$branch] eq $letter) {
                # Have we used this position yet?
                foreach my $usedBranch (@$pathRef) {
                    if ($usedBranch == $branch) {
                        next BRANCH;
                    }
                }
                if (scalar @$lettersRef == $index + 1) {
                    return 1; # End of Word and success.
                }
                Push @$pathRef, $branch;
                if (traverse($lettersRef, $pathRef)) {
                    return 1; # Recursive success.
                }
                else {
                    pop @$pathRef;
                }
            }
        }
    return 0; # No path found. Failed.
}
11
Paul Chernoch

Ich weiß, ich bin super spät, aber ich habe vor einiger Zeit eine davon in PHP gemacht - nur zum Spaß ...

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Es wurden 75 Wörter (133 Punkte) in 0,90108 Sekunden gefunden.

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

Gibt einen Hinweis darauf, was das Programm tatsächlich macht - jeder Buchstabe ist der Ort, an dem er durch die Muster schaut, während jedes "." zeigt einen Weg, den es versucht hat. Je mehr '.' Je weiter es gesucht hat.

Lass es mich wissen, wenn du den Code willst ... es ist eine schreckliche Mischung aus PHP und HTML, die niemals das Licht der Welt erblicken sollte, daher wage ich es nicht, sie hier zu posten: P

9
Danny

Ich habe 3 Monate lang an einer Lösung für das 10 beste Punktdichte 5x5 Boggle-Board-Problem gearbeitet.

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

Der Kartenanalysealgorithmus verwendet einen expliziten Stapel, um die Kartenquadrate pseudo-rekursiv durch ein direktes azyklisches Wortdiagramm mit direkten untergeordneten Informationen und einem Zeitstempel-Verfolgungsmechanismus zu durchlaufen. Dies könnte die weltweit fortschrittlichste Datenstruktur von Lexicon sein.

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

Übergeordnete Webseite:

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

Komponenten-Webseiten:

Optimales Anzeiger - http://www.pathcom.com/~vadco/binary.html

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

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

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

Diese umfassende Arbeit wird nur eine Person interessieren, die das Beste verlangt.

9

Lesen Sie zuerst, wie einer der Entwickler der C # -Sprache ein verwandtes Problem gelöst hat: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the- sultana-analyst.aspx .

Wie bei ihm können Sie mit einem Wörterbuch beginnen und die Wörter kanonisieren, indem Sie ein Wörterbuch aus einem Buchstabenfeld erstellen, das alphabetisch zu einer Liste von Wörtern sortiert ist, die aus diesen Buchstaben buchstabiert werden können. 

Als Nächstes erstellen Sie die möglichen Wörter aus der Tafel und suchen nach ihnen. Ich vermute, das wird dich ziemlich weit bringen, aber es gibt sicherlich mehr Tricks, die die Dinge beschleunigen könnten. 

4
RossFabricant

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

Bei der Suche oben gibt es beispielsweise nur 13 Buchstaben, mit denen Ihre Wörter beginnen können (effektiv auf die Hälfte der Anfangsbuchstaben reduzieren).

Wenn Sie weitere Buchstabenvariationen hinzufügen, werden die verfügbaren Word-Sätze weiter reduziert, wodurch die Suche verringert wird.

Ich würde dort anfangen.

4
jerebear

Ich müsste mich mehr mit einer Komplettlösung beschäftigen, aber als praktische Optimierung frage ich mich, ob es sich lohnt, eine Tabelle mit Häufigkeiten von Digrammen und Trigrammen (Kombinationen aus zwei und drei Buchstaben) auf der Grundlage aller Berechnungen zu berechnen Wörter aus Ihrem Wörterbuch und verwenden Sie diese, um Ihre Suche zu priorisieren. Ich würde mit den Anfangsbuchstaben der Wörter gehen. Wenn Ihr Wörterbuch also die Wörter "Indien", "Wasser", "Extrem" und "Außerordentlich" enthält, könnte Ihre vorberechnete Tabelle Folgendes sein:

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

Suchen Sie dann nach diesen Digrammen in der Reihenfolge der Gemeinsamkeit (zuerst EX, dann WA/IN)

4
Smashery

Ich schlage vor, aus Buchstaben einen Buchstabenbaum zu machen. Der Baum würde aus Buchstabenstrukturen bestehen, wie folgt:

letter: char
isWord: boolean

Dann bauen Sie den Baum auf, wobei jede Tiefe einen neuen Buchstaben hinzufügt. Mit anderen Worten, auf der ersten Ebene würde es das Alphabet geben; Dann werden von jedem dieser Bäume weitere 26 Einträge usw. angezeigt, bis Sie alle Wörter buchstabiert haben. Hänge dich an diesen geparkten Baum, und es werden alle möglichen Antworten schneller gefunden, um nachzuschlagen.

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

BEGIN: 
    For each letter:
        if the struct representing it on the current depth has isWord == true, enter it as an answer.
        Cycle through all its neighbors; if there is a child of the current node corresponding to the letter, recursively call BEGIN on it.

Dies könnte mit etwas dynamischer Programmierung beschleunigt werden. In Ihrem Beispiel sind die beiden 'A' neben einem 'E' und einem 'W', die (ab dem Zeitpunkt, an dem sie getroffen wurden) identisch wären. Ich habe nicht genug Zeit, um den Code dafür wirklich zu buchstabieren, aber ich denke, Sie können die Idee sammeln.

Ich bin mir sicher, dass Sie andere Lösungen finden werden, wenn Sie Google für "Boggle Solver" verwenden.

4
Daniel Lew

Aus Spaß habe ich eine in bash implementiert. Es ist nicht super schnell, aber vernünftig. 

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

4
Kyle

Ich habe meinen Löser in C++ geschrieben. Ich habe eine benutzerdefinierte Baumstruktur implementiert. Ich bin nicht sicher, ob es ein Trie ist, aber es ist ähnlich. Jeder Knoten hat 26 Zweige, 1 für jeden Buchstaben des Alphabets. Ich durchquere die Äste der Bordwand parallel zu den Ästen meines Wörterbuchs. Wenn der Zweig nicht im Wörterbuch vorhanden ist, höre ich mit der Suche auf der Boggle-Tafel auf. Ich wandle alle Buchstaben auf der Tafel in ints um. 'A' = 0. Da es sich nur um Arrays handelt, wird immer nach O (1) gesucht. Jeder Knoten speichert, wenn er ein Wort vervollständigt und wie viele Wörter in seinen untergeordneten Elementen vorhanden sind. Der Baum wird beschnitten, da Wörter gefunden werden, um das wiederholte Suchen nach denselben Wörtern zu reduzieren. Ich glaube, das Beschneiden ist auch O (1).

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

Lädt ein Wörterbuch mit 178.590 Wörtern in <1 Sekunde.
Löscht 100 x 100 Boggle (boggle.txt) in 4 Sekunden. ~ 44.000 Wörter gefunden.
Das Lösen einer 4x4-Boggle ist zu schnell, um einen aussagekräftigen Maßstab zu setzen. :)

Fast Boggle Solver GitHub Repo

3
Will

Urkomisch Ich habe vor ein paar Tagen beinahe die gleiche Frage gestellt, wegen dem gleichen verdammten Spiel! Ich habe aber nicht gerade gesucht, weil Google nach boggle solver python gesucht hat - und alle Antworten bekommen, die ich wollte.

3
physicsmichael

Ich weiß, dass die Zeit dieser Frage gekommen und vergangen ist, aber da ich selbst an einem Löser gearbeitet habe und beim Googeln hier gestolpert bin, dachte ich, ich sollte einen Hinweis auf meine posten, da er sich von den anderen etwas unterscheidet.

Ich entschied mich für ein flaches Array für das Spielbrett und rekursive Jagden von jedem Buchstaben auf dem Spielbrett, wobei ich mich von einem gültigen Nachbarn zu einem gültigen Nachbarn bewege und die Suche fortsetze, wenn die aktuelle Buchstabenliste ein gültiges Präfix in einem Index enthält. Während der Begriff des aktuellen Wortes durchlaufen wird, ist dies eine Liste von Indizes in die Tafel, nicht Buchstaben, aus denen ein Wort besteht. Bei der Überprüfung des Index werden die Indizes in Buchstaben übersetzt und die Überprüfung erfolgt.

Der Index ist ein Brute-Force-Wörterbuch, das ein bisschen wie ein Trie ist, aber Pythonic-Abfragen des Index zulässt. Wenn die Wörter "cat" und "cater" in der Liste enthalten sind, wird dies im Wörterbuch angezeigt:

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

Wenn current_Word also 'ca' ist, wissen Sie, dass es sich um ein gültiges Präfix handelt, da 'ca' in d True zurückgibt (fahren Sie also mit dem Board-Traversal fort). Und wenn das aktuelle_Wort 'cat' ist, wissen Sie, dass es ein gültiges Word ist, da es ein gültiges Präfix ist und 'cat' in d['cat'] ebenfalls True zurückgibt.

Wenn man sich so anfühlt, könnte das lesbaren Code nicht zu langsam sein. Wie bei allen anderen ist das Lesen/Aufbauen des Indexes die Kosten in diesem System. Das Board zu lösen ist ziemlich laut.

Der Code befindet sich unter http://Gist.github.com/268079 . Es ist absichtlich vertikal und naiv mit viel expliziter Gültigkeitsprüfung, weil ich das Problem verstehen wollte, ohne es mit einer Menge Magie oder Unklarheiten zu verkrüppeln.

3
cdent

Angenommen, ein Boggle-Board mit N Zeilen und M Spalten, nehmen wir Folgendes an:

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

Unter diesen Voraussetzungen ist die Komplexität dieser Lösung O (N * M).

Ich denke, dass ein Vergleich der Laufzeiten für dieses eine Beispiel-Board in vieler Hinsicht den Punkt verfehlt, aber der Vollständigkeit halber wird diese Lösung auf meinem modernen MacBook Pro in weniger als 0,2 Sekunden komplettiert.

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

#!/usr/bin/env Ruby
# Example usage: ./boggle-solver --board "fxie amlo ewbx astu"

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

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

# Functions

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

# Script

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

  opts.on('--board BOARD', String, 'The board (e.g. "fxi aml ewb ast")') do |b|
    options[:board] = b
  end

  opts.on('--corpus CORPUS_PATH', String, 'Corpus file path') do |c|
    options[:corpus_path] = c
  end

  opts.on_tail('-h', '--help', 'Shows usage') 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 "No corpus exists - #{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}"
2
mon4goos

Ich habe eine Lösung in OCaml implementiert . Es kompiliert ein Wörterbuch als Trie vorab und verwendet Sequenzfrequenzen aus zwei Buchstaben, um Kanten zu entfernen, die niemals in einem Word vorkommen könnten, um die Verarbeitung zu beschleunigen. 

Es löst Ihre Beispielplatine in 0,35 ms (mit einer zusätzlichen Anlaufzeit von 6 ms, die hauptsächlich mit dem Laden des Tries in den Speicher zusammenhängt). 

Die gefundenen Lösungen: 

["swami"; "emile"; "limbs"; "limbo"; "limes"; "amble"; "tubs"; "stub";
 "swam"; "semi"; "seam"; "awes"; "buts"; "bole"; "boil"; "west"; "east";
 "emil"; "lobs"; "limb"; "Lime"; "lima"; "mesa"; "mews"; "mewl"; "maws";
 "milo"; "mile"; "awes"; "amie"; "axle"; "elma"; "fame"; "ubs"; "Tux"; "tub";
 "twa"; "twa"; "stu"; "saw"; "sea"; "sew"; "sea"; "awe"; "awl"; "but"; "btu";
 "box"; "bmw"; "was"; "wax"; "oil"; "lox"; "lob"; "leo"; "lei"; "lie"; "mes";
 "mew"; "mae"; "maw"; "max"; "mil"; "mix"; "awe"; "awl"; "Elm"; "eli"; "fax"]
1
Victor Nicollet

Ich wollte also eine andere PHP - Methode zur Lösung dieses Problems hinzufügen, da jeder PHP liebt . Es gibt ein bisschen Refactoring, das ich gerne machen würde, beispielsweise einen Regex-Abgleich mit der Wörterbuchdatei, aber jetzt habe ich Ich lade nur die gesamte Wörterbuchdatei in eine Wortliste.

Ich habe dies mit einer Linklisten-Idee gemacht. Jeder Knoten hat einen Zeichenwert, einen Standortwert und einen nächsten Zeiger.

Der Standortwert ist, wie ich herausgefunden habe, ob zwei Knoten verbunden sind.

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

Ich weiß also, dass zwei Knoten miteinander verbunden sind, wenn die Position des ersten Knotens der Position des zweiten Knotens +/- 1 für dieselbe Zeile entspricht, +/- 9, 10, 11 für die Zeile darüber und darunter.

Ich verwende Rekursion für die Hauptsuche. Es nimmt ein Wort aus der Wortliste, findet alle möglichen Startpunkte und rekursiv die nächste mögliche Verbindung, wobei es daran erinnert wird, dass es nicht an einen Ort gehen kann, den es bereits verwendet (weshalb ich $ notInLoc hinzufüge).

Wie auch immer, ich weiß, dass es etwas Refactoring braucht und würde gerne Gedanken darüber hören, wie man es sauberer machen kann, aber es liefert die richtigen 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, sobald ich das Wörterbuch preg_match ergebe, sich dies erheblich verringern wird.

<?php
    ini_set('xdebug.var_display_max_depth', 20);
    ini_set('xdebug.var_display_max_children', 1024);
    ini_set('xdebug.var_display_max_data', 1024);

    class Node {
        var $loc;

        function __construct($value) {
            $this->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) {
            // Takes in a board string and creates all the nodes
            $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;
            }
            // Load in a dictionary file
            // Use regexp to elimate all the words that could never appear and load the 
            // rest of the words into wordList
            $handle = fopen("dict.txt", "r");
            if ($handle) {
                while (($line = fgets($handle)) !== false) {
                    // process the line read.
                    $line = trim($line);
                    if (strlen($line) > 2) {
                        $this->wordList[] = trim($line);
                    }
                }
                fclose($handle);
            } else {
                // error opening the file.
                echo "Problem with the file.";
            } 
        }

        function isConnected($node1, $node2) {
        // Determines if 2 nodes are connected on the boggle board

            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 = []) {
            // Returns a node with the value that isn't in a location
            $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) {
            // Returns an array of nodes with a specific value
            $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 = []) {
            // Returns an array of nodes that are connected to a specific node and 
            // contain a specific value and are not in a certain location
            $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 . "<br />";
                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);

    ?>
1
Nate

Hier ist die Lösung Verwenden Sie vordefinierte Wörter in NLTK-Toolkit NLTK enthält das nltk.corpus-Paket, in dem wir Pakete enthalten, die als Wörter bezeichnet werden und mehr als 2 Lakhs englische Wörter enthalten, die Sie einfach in Ihrem Programm verwenden können.

Sobald Sie Ihre Matrix erstellt haben, wandeln Sie sie in ein Zeichenfeld um und führen Sie diesen Code aus

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

def possibleWords(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: #its depends if you want only length more than 5 use this otherwise remove that one. 
            print(Word)


nltk.download('words')
Word_list = words.words()
# prints 236736
print(len(Word_list))
charSet = ['h', 'e', 'l', 'o', 'n', 'v', 't']
possibleWords(Word_list, charSet)

Ausgabe:

eleven
eleventh
elevon
entente
entone
ethene
ethenol
evolve
evolvent
hellhole
helvell
hooven
letten
looten
nettle
nonene
nonent
nonlevel
notelet
novelet
novelette
novene
teenet
teethe
teevee
telethon
tellee
tenent
tentlet
theelol
toetoe
tonlet
toothlet
tootle
tottle
vellon
velvet
velveteen
venene
vennel
venthole
voeten
volent
volvelle
volvent
voteen

Ich hoffe du verstehst es.

1
lava kumar

Eine JavaScript-Lösung von Node.JS. Berechnet alle 100 eindeutigen Wörter in weniger als einer Sekunde, darunter das Lesen der Wörterbuchdatei (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", "ABER "," BLO "," WAR "," WAE "," WEA "," LEI "," LEO "," LOB "," LOX "," WEM "," ÖL "," OLM "," WEA ", "WAE", "WAX", "WAF", "MILO", "EAST", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST" "," TWAE "," LIMB "," WASE "," WAST "," BLEO "," STUB "," BOIL "," BOLE "," Lime "," 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) {
    // Expects 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 = []

    // Replace board with 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)) {
                // Create a new path if on board and we haven't visited this node yet.
                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) {
    // Binary search
    return this.search_prefix(prefix, 0, this.dict_array.length)
}

Dict.prototype.contains_exact = function(exact) {
    // Binary search
    return this.search_exact(exact, 0, this.dict_array.length)
}

Dict.prototype.search_prefix = function(prefix, start, end) {
    if (start >= end) {
        // If no more place to search, return no matter what.
        return this.dict_array[start].indexOf(prefix) > -1
    }

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

    if (this.dict_array[middle].indexOf(prefix) > -1) {
        // If we prefix exists, return true.
        return true
    } else {
        // Recurse
        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) {
        // If no more place to search, return no matter what.
        return this.dict_array[start] === exact
    }

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

    if (this.dict_array[middle] === exact) {
        // If we prefix exists, return true.
        return true
    } else {
        // Recurse
        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
})))
1

Ich weiß, dass ich auf der Party wirklich spät bin, aber ich habe als Codierungsübung einen Fehlerlöser in mehreren Programmiersprachen (C++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) und implementiert Ich dachte, dass sich jemand für diese interessieren könnte, also lasse ich den Link hier: https://github.com/AmokHuginnsson/boggle-solvers

0
AmokHuginnsson

Wie wäre es mit einem einfachen Sortieren und Verwenden der binary-Suche im Wörterbuch?

Gibt die gesamte Liste in 0,35 sec zurück und kann weiter optimiert werden (z. B. Entfernen von Wörtern mit nicht verwendeten Buchstaben usw.).

from bisect import bisect_left

f = open("dict.txt")
D.extend([line.strip() for line in f.readlines()])
D = sorted(D)

def neibs(M,x,y):
    n = len(M)
    for i in xrange(-1,2):
        for j in xrange(-1,2):
            if (i == 0 and j == 0) or (x + i < 0 or x + i >= n or y + j < 0 or y + j >= n):
                continue
            yield (x + i, y + j)

def findWords(M,D,x,y,prefix):
    prefix = prefix + M[x][y]

    # find Word in dict by binary search
    found = bisect_left(D,prefix)

    # if found then yield
    if D[found] == prefix: 
        yield prefix

    # if what we found is not even a prefix then return
    # (there is no point in going further)
    if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
        return

    # recourse
    for neib in neibs(M,x,y):
        for Word in findWords(M,D,neib[0], neib[1], prefix):
            yield Word

def solve(M,D):
    # check each starting point
    for x in xrange(0,len(M)):
        for y in xrange(0,len(M)):
            for Word in findWords(M,D,x,y,""):
                yield Word

grid = "fxie amlo ewbx astu".split()
print [x for x in solve(grid,D)]
0

Ich habe das in c gelöst. Es dauert etwa 48 ms, um auf meinem Computer zu laufen (etwa 98% der Zeit, um das Wörterbuch von der Festplatte zu laden und den Trie zu erstellen). Das Wörterbuch ist/usr/share/dict/american-english mit 62886 Wörtern.

Quellcode

0
matzahboy

Diese Lösung gibt auch die Richtung an, in der das Board gesucht werden soll

Algo:

1. Uses trie to save all the Word in the english to fasten the search
2. The uses DFS to search the words in Boggle

Ausgabe:

Found "pic" directions from (4,0)(p) go  → →
Found "pick" directions from (4,0)(p) go  → → ↑
Found "pickman" directions from (4,0)(p) go  → → ↑ ↑ ↖ ↑
Found "picket" directions from (4,0)(p) go  → → ↑ ↗ ↖
Found "picked" directions from (4,0)(p) go  → → ↑ ↗ ↘
Found "pickle" directions from (4,0)(p) go  → → ↑ ↘ →

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()

# If you wan to remove stop words
# 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']
]

# Instead of X and Y co-ordinates
# better to use Row and column
lenc = len(boggle[0])
lenr = len(boggle)

# Initialize trie datastructure
trie_node = {'valid': False, 'next': {}}

# lets get the delta to find all the nighbors
neighbors_delta = [
    (-1,-1, "↖"),
    (-1, 0, "↑"),
    (-1, 1, "↗"),
    (0, -1, "←"),
    (0,  1, "→"),
    (1, -1, "↙"),
    (1,  0, "↓"),
    (1,  1, "↘"),
]


def gen_trie(Word, node):
    """udpates the trie datastructure using the given Word"""
    if not Word:
        return

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

    # recursively build trie
    gen_trie(Word[1:], node[Word[0]])


def build_trie(words, trie):
    """Builds trie data structure from the list of words given"""
    for Word in words:
        gen_trie(Word, trie)
    return trie


def get_neighbors(r, c):
    """Returns the neighbors for a given co-ordinates"""
    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):
    """Scan the graph using 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):
    """Initiate the search for words in boggle"""
    trie_node = build_trie(english_words, trie_node)

    # print the board
    print("Given board")
    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, '', 'directions from ({},{})({}) go '.format(r, c, letter))


if __== '__main__':
    main(trie_node)
0
naren

Ich habe das perfekt und sehr schnell gelöst. Ich habe es in eine Android-App gestellt. Sehen Sie sich das Video im Play Store-Link an, um es in Aktion zu sehen. 

Word Cheats ist eine App, die jedes Word-Spiel im Matrix-Stil "knackt". Diese App wurde erstellt, um mir zu helfen, Word-Scrambler zu betrügen. Es kann für Word-Suchen, Ruzzle, Wörter, Word Finder, Word Crack, Fackeln und mehr verwendet werden!

Sie können es hier sehen https://play.google.com/store/apps/details?id=com.harris.wordcracker

Sehen Sie sich die App in Aktion im Video an https://www.youtube.com/watch?v=DL2974WmNAI

0
Josh Harris

Das habe ich auch mit Java gelöst. Meine Implementierung ist 269 Zeilen lang und ziemlich einfach zu bedienen. Zuerst müssen Sie eine neue Instanz der Boggler-Klasse erstellen und dann die Auflösungsfunktion mit dem Raster als Parameter aufrufen. Es dauert etwa 100 ms, um das Wörterbuch mit 50 000 Wörtern auf meinem Computer zu laden, und die Wörter werden in etwa 10 bis 20 ms gefunden. Die gefundenen Wörter werden in einer ArrayList, foundWords, gespeichert.

import Java.io.BufferedReader;
import Java.io.File;
import Java.io.FileInputStream;
import Java.io.FileNotFoundException;
import Java.io.IOException;
import Java.io.InputStreamReader;
import Java.net.URISyntaxException;
import Java.net.URL;
import Java.util.ArrayList;
import Java.util.Arrays;
import Java.util.Comparator;

public class Boggler {
    private ArrayList<String> words = new ArrayList<String>();      
    private ArrayList<String> roundWords = new ArrayList<String>(); 
    private ArrayList<Word> foundWords = new ArrayList<Word>();     
    private char[][] letterGrid = new char[4][4];                   
    private String letters;                                         

    public Boggler() throws FileNotFoundException, IOException, URISyntaxException {
        long startTime = System.currentTimeMillis();

        URL path = GUI.class.getResource("words.txt");
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(path.toURI()).getAbsolutePath()), "iso-8859-1"));
        String line;
        while((line = br.readLine()) != null) {
            if(line.length() < 3 || line.length() > 10) {
                continue;
            }

            this.words.add(line);
        }
    }

    public ArrayList<Word> getWords() {
        return this.foundWords;
    }

    public void solve(String letters) {
        this.letters = "";
        this.foundWords = new ArrayList<Word>();

        for(int i = 0; i < letters.length(); i++) {
            if(!this.letters.contains(letters.substring(i, i + 1))) {
                this.letters += letters.substring(i, i + 1);
            }
        }

        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                this.letterGrid[i][j] = letters.charAt(i * 4 + j);
            }
        }

        System.out.println(Arrays.deepToString(this.letterGrid));               

        this.roundWords = new ArrayList<String>();      
        String pattern = "[" + this.letters + "]+";     

        for(int i = 0; i < this.words.size(); i++) {

            if(this.words.get(i).matches(pattern)) {
                this.roundWords.add(this.words.get(i));
            }
        }

        for(int i = 0; i < this.roundWords.size(); i++) {
            Word word = checkForWord(this.roundWords.get(i));

            if(Word != null) {
                System.out.println(Word);
                this.foundWords.add(Word);
            }
        }       
    }

    private Word checkForWord(String Word) {
        char initial = Word.charAt(0);
        ArrayList<LetterCoord> startPoints = new ArrayList<LetterCoord>();

        int x = 0;  
        int y = 0;
        for(char[] row: this.letterGrid) {
            x = 0;

            for(char letter: row) {
                if(initial == letter) {
                    startPoints.add(new LetterCoord(x, y));
                }

                x++;
            }

            y++;
        }

        ArrayList<LetterCoord> letterCoords = null;
        for(int initialTry = 0; initialTry < startPoints.size(); initialTry++) {
            letterCoords = new ArrayList<LetterCoord>();    

            x = startPoints.get(initialTry).getX(); 
            y = startPoints.get(initialTry).getY();

            LetterCoord initialCoord = new LetterCoord(x, y);
            letterCoords.add(initialCoord);

            letterLoop: for(int letterIndex = 1; letterIndex < Word.length(); letterIndex++) {
                LetterCoord lastCoord = letterCoords.get(letterCoords.size() - 1);  
                char currentChar = Word.charAt(letterIndex);                        

                ArrayList<LetterCoord> letterLocations = getNeighbours(currentChar, lastCoord.getX(), lastCoord.getY());

                if(letterLocations == null) {
                    return null;    
                }       

                for(int foundIndex = 0; foundIndex < letterLocations.size(); foundIndex++) {
                    if(letterIndex != Word.length() - 1 && true == false) {
                        char nextChar = Word.charAt(letterIndex + 1);
                        int lastX = letterCoords.get(letterCoords.size() - 1).getX();
                        int lastY = letterCoords.get(letterCoords.size() - 1).getY();

                        ArrayList<LetterCoord> possibleIndex = getNeighbours(nextChar, lastX, lastY);
                        if(possibleIndex != null) {
                            if(!letterCoords.contains(letterLocations.get(foundIndex))) {
                                letterCoords.add(letterLocations.get(foundIndex));
                            }
                            continue letterLoop;
                        } else {
                            return null;
                        }
                    } else {
                        if(!letterCoords.contains(letterLocations.get(foundIndex))) {
                            letterCoords.add(letterLocations.get(foundIndex));

                            continue letterLoop;
                        }
                    }
                }
            }

            if(letterCoords != null) {
                if(letterCoords.size() == Word.length()) {
                    Word w = new Word(word);
                    w.addList(letterCoords);
                    return w;
                } else {
                    return null;
                }
            }
        }

        if(letterCoords != null) {
            Word foundWord = new Word(word);
            foundWord.addList(letterCoords);

            return foundWord;
        }

        return null;
    }

    public ArrayList<LetterCoord> getNeighbours(char letterToSearch, int x, int y) {
        ArrayList<LetterCoord> neighbours = new ArrayList<LetterCoord>();

        for(int _y = y - 1; _y <= y + 1; _y++) {
            for(int _x = x - 1; _x <= x + 1; _x++) {
                if(_x < 0 || _y < 0 || (_x == x && _y == y) || _y > 3 || _x > 3) {
                    continue;
                }

                if(this.letterGrid[_y][_x] == letterToSearch && !neighbours.contains(new LetterCoord(_x, _y))) {
                    neighbours.add(new LetterCoord(_x, _y));
                }
            }
        }

        if(neighbours.isEmpty()) {
            return null;
        } else {
            return neighbours;
        }
    }
}

class Word {
    private String Word;    
    private ArrayList<LetterCoord> letterCoords = new ArrayList<LetterCoord>();

    public Word(String Word) {
        this.Word = Word;
    }

    public boolean addCoords(int x, int y) {
        LetterCoord lc = new LetterCoord(x, y);

        if(!this.letterCoords.contains(lc)) {
            this.letterCoords.add(lc);

            return true;
        }

        return false;
    }

    public void addList(ArrayList<LetterCoord> letterCoords) {
        this.letterCoords = letterCoords;
    } 

    @Override
    public String toString() {
        String outputString = this.Word + " ";
        for(int i = 0; i < letterCoords.size(); i++) {
            outputString += "(" + letterCoords.get(i).getX() + ", " + letterCoords.get(i).getY() + ") ";
        }

        return outputString;
    }

    public String getWord() {
        return this.Word;
    }

    public ArrayList<LetterCoord> getList() {
        return this.letterCoords;
    }
}

class LetterCoord extends ArrayList {
    private int x;          
    private int y;          

    public LetterCoord(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }

    @Override
    public boolean equals(Object o) {
        if(!(o instanceof LetterCoord)) {
            return false;
        }

        LetterCoord lc = (LetterCoord) o;

        if(this.x == lc.getX() &&
                this.y == lc.getY()) {
            return true;
        }

        return false;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 29 * hash + this.x;
        hash = 24 * hash + this.y;
        return hash;
    }
}
0
MikkoP
    package ProblemSolving;

import Java.util.HashSet;
import Java.util.Set;

/**
 * Given a 2-dimensional array of characters and a
 * dictionary in which a Word can be searched in O(1) time.
 * Need to print all the words from array which are present
 * in dictionary. Word can be formed in any direction but
 * has to end at any Edge of array.
 * (Need not worry much about the dictionary)
 */
public class DictionaryWord {
    private static char[][] matrix = new char[][]{
            {'a', 'f', 'h', 'u', 'n'},
            {'e', 't', 'a', 'i', 'r'},
            {'a', 'e', 'g', 'g', 'o'},
            {'t', 'r', 'm', 'l', 'p'}
    };
    private static int dim_x = matrix.length;
    private static int dim_y = matrix[matrix.length -1].length;
    private static Set<String> wordSet = new HashSet<String>();

    public static void main(String[] args) {
        //dictionary
        wordSet.add("after");
        wordSet.add("hate");
        wordSet.add("hair");
        wordSet.add("air");
        wordSet.add("eat");
        wordSet.add("tea");

        for (int x = 0; x < dim_x; x++) {
            for (int y = 0; y < dim_y; y++) {
                checkAndPrint(matrix[x][y] + "");
                int[][] visitedMap = new int[dim_x][dim_y];
                visitedMap[x][y] = 1;
                recursion(matrix[x][y] + "", visitedMap, x, y);
            }
        }
    }

    private static void checkAndPrint(String Word) {
        if (wordSet.contains(Word)) {
            System.out.println(Word);
        }
    }

    private static void recursion(String Word, int[][] visitedMap, int x, int y) {
        for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
            for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
                if (visitedMap[i][j] == 1) {
                    continue;
                } else {
                    int[][] newVisitedMap = new int[dim_x][dim_y];
                    for (int p = 0; p < dim_x; p++) {
                        for (int q = 0; q < dim_y; q++) {
                           newVisitedMap[p][q] = visitedMap[p][q];
                        }
                    }
                    newVisitedMap[i][j] = 1;
                    checkAndPrint(Word + matrix[i][j]);
                    recursion(Word + matrix[i][j], newVisitedMap, i, j);
                }
            }
        }
    }

}
0
Dheeraj Sachan
import Java.util.HashSet;
import Java.util.Set;

/**
 * @author Sujeet Kumar ([email protected]) It prints out all strings that can
 *         be formed by moving left, right, up, down, or diagonally and exist in
 *         a given dictionary , without repeating any cell. Assumes words are
 *         comprised of lower case letters. Currently prints words as many times
 *         as they appear, not just once. *
 */

public class BoggleGame 
{
  /* A sample 4X4 board/2D matrix */
  private static char[][] board = { { 's', 'a', 's', 'g' },
                                  { 'a', 'u', 't', 'h' }, 
                                  { 'r', 't', 'j', 'e' },
                                  { 'k', 'a', 'h', 'e' }
};

/* A sample dictionary which contains unique collection of words */
private static Set<String> dictionary = new HashSet<String>();

private static boolean[][] visited = new boolean[board.length][board[0].length];

public static void main(String[] arg) {
    dictionary.add("sujeet");
    dictionary.add("sarthak");
    findWords();

}

// show all words, starting from each possible starting place
private static void findWords() {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            StringBuffer buffer = new StringBuffer();
            dfs(i, j, buffer);
        }

    }

}

// run depth first search starting at cell (i, j)
private static void dfs(int i, int j, StringBuffer buffer) {
    /*
     * base case: just return in recursive call when index goes out of the
     * size of matrix dimension
     */
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
        return;
    }

    /*
     * base case: to return in recursive call when given cell is already
     * visited in a given string of Word
     */
    if (visited[i][j] == true) { // can't visit a cell more than once
        return;
    }

    // not to allow a cell to reuse
    visited[i][j] = true;

    // combining cell character with other visited cells characters to form
    // Word a potential Word which may exist in dictionary
    buffer.append(board[i][j]);

    // found a Word in dictionary. Print it.
    if (dictionary.contains(buffer.toString())) {
        System.out.println(buffer);
    }

    /*
     * consider all neighbors.For a given cell considering all adjacent
     * cells in horizontal, vertical and diagonal direction
     */
    for (int k = i - 1; k <= i + 1; k++) {
        for (int l = j - 1; l <= j + 1; l++) {
            dfs(k, l, buffer);

        }

    }
    buffer.deleteCharAt(buffer.length() - 1);
    visited[i][j] = false;
  }
}
0
Sujeet

Ich habe dieses Problem in C # gelöst und dabei einen DFA-Algorithmus verwendet. Sie können meinen Code unter

https://github.com/attilabicsko/wordshuffler/

Neben dem Finden von Wörtern in einer Matrix speichert mein Algorithmus die tatsächlichen Pfade für die Wörter. Wenn Sie also ein Word Finder-Spiel entwerfen, können Sie überprüfen, ob sich ein Wort auf einem tatsächlichen Pfad befindet. 

0
Attila Bicskó

Hier ist meine Java-Implementierung: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.Java

Der Trie-Build dauerte 0 Stunden, 0 Minuten, 1 Sekunden und 532 Millisekunden
Die Wortsuche dauerte 0 Stunden, 0 Minuten, 0 Sekunden, 92 Millisekunden

eel eeler eely eer eke eker eld eleut elk ell 
elle epee epihippus ere erept err error erupt eurus eye 
eyer eyey hip hipe hiper hippish hipple hippus his hish 
hiss hist hler hsi ihi iphis isis issue issuer ist 
isurus kee keek keeker keel keeler keep keeper keld kele 
kelek kelep kelk kell kelly kelp kelper kep kepi kept 
ker kerel kern keup keuper key kyl kyle lee leek 
leeky leep leer lek leo leper leptus lepus ler leu 
ley lleu lue lull luller lulu lunn lunt lunule luo 
lupe lupis lupulus lupus lur lure lurer lush lushly lust 
lustrous lut lye nul null nun nupe nurture nurturer nut 
oer ore ort ouphish our oust out outpeep outpeer outpipe 
outpull outpush output outre outrun outrush outspell outspue outspurn outspurt 
outstrut outstunt outsulk outturn outusure oyer pee peek peel peele 
peeler peeoy peep peeper peepeye peer pele peleus pell peller 
pelu pep peplus pepper pepperer pepsis per pern pert pertussis 
peru perule perun peul phi pip pipe piper pipi pipistrel 
pipistrelle pipistrellus pipper pish piss pist plup plus plush ply 
plyer psi pst puerer pul pule puler pulk pull puller 
pulley pullus pulp pulper pulu puly pun punt pup puppis 
pur pure puree purely purer purr purre purree purrel purrer 
puru purupuru pus Push puss pustule put putt puture ree 
reek reeker reeky reel reeler reeper rel rely reoutput rep 
repel repeller repipe reply repp reps reree rereel rerun reuel 
roe roer roey roue rouelle roun roup rouper roust rout 
roy rue ruelle ruer rule ruler rull ruller run runt 
rupee rupert rupture ruru rus Rush russ Rust rustre rut 
shi shih ship shipper shish shlu sip sipe siper sipper 
sis sish sisi siss sissu sist sistrurus speel speer spelk 
spell speller splurt spun spur spurn spurrer spurt sput ssi 
ssu stre stree streek streel streeler streep streke streperous strepsis 
strey stroup stroy stroyer strue strunt strut stu stue stull 
stuller stun stunt stupe stupeous stupp sturnus sturt stuss stut 
sue suer suerre suld sulk sulker sulky sull sully sulu 
Sun sunn sunt sunup sup supe super superoutput supper supple 
supplely supply sur sure surely surrey sus susi susu susurr 
susurrous susurrus sutu suture suu tree treey trek trekker trey 
troupe trouper trout troy true truer trull truller truly trun 
trush truss trust tshi tst tsun tsutsutsi tue tule tulle 
tulu tun tunu tup tupek tupi tur turn turnup turr 
turus tush tussis tussur tut tuts tutu tutulus ule ull 
uller ulu ululu unreel unrule unruly unrun unrust untrue untruly 
untruss untrust unturn unurn upper upperer uppish uppishly uppull uppush 
upspurt upsun upsup uptree uptruss upturn ure urn uro uru 
urus urushi ush ust usun usure usurer utu yee yeel 
yeld yelk yell yeller Yelp yelper yeo yep yer yere 
yern yoe yor yore you youl youp your yourn yoy 

Note: Ich habe das Wörterbuch und die Zeichenmatrix am Anfang dieses Threads verwendet. Der Code wurde auf meinem MacBookPro ausgeführt. Nachfolgend finden Sie einige Informationen zum Computer. 

Modellname: MacBook Pro
Modellkennung: MacBookPro8,1
Prozessorname: Intel Core i5
Prozessorgeschwindigkeit: 2,3 GHz
Anzahl der Prozessoren: 1
Gesamtzahl der Kerne: 2
L2-Cache (pro Kern): 256 KB
L3-Cache: 3 MB
Speicher: 4 GB
Booten Sie ROM Version: MBP81.0047.B0E
SMC Version (System): 1.68f96

0
Zhile Zou

Dies ist die Lösung, die ich für die Lösung des schwerwiegenden Problems gefunden habe. Ich denke, es ist die "Pythonic" -Methode, um Dinge zu tun:

from itertools import combinations
from itertools import izip
from math import fabs

def isAllowedStep(current,step,length,doubleLength):
            # for step == length -1 not to be 0 => trivial solutions are not allowed
    return length > 1 and \
           current + step < doubleLength and current - step > 0 and \
           ( step == 1 or step == -1 or step <= length+1 or step >= length - 1)

def getPairwiseList(someList):
    iterableList = iter(someList)
    return izip(iterableList, iterableList)

def isCombinationAllowed(combination,length,doubleLength):

    for (first,second) in  getPairwiseList(combination):
        _, firstCoordinate = first
        _, secondCoordinate = second
        if not isAllowedStep(firstCoordinate, fabs(secondCoordinate-firstCoordinate),length,doubleLength):
            return False
    return True

def extractSolution(combinations):
    return ["".join([x[0] for x in combinationTuple]) for combinationTuple in combinations]


length = 4
text = Tuple("".join("fxie amlo ewbx astu".split()))
textIndices = Tuple(range(len(text)))
coordinates = Zip(text,textIndices)

validCombinations = [combination for combination in combinations(coordinates,length) if isCombinationAllowed(combination,length,length*length)]
solution = extractSolution(validCombinations)

Diesen Teil empfehle ich Ihnen, nicht für alle möglichen Übereinstimmungen zu verwenden aber es würde tatsächlich die Möglichkeit bieten, zu prüfen, ob die von Ihnen erzeugten Wörter tatsächlich gültige Wörter darstellen:

import mechanize
def checkWord(Word):
    url = "https://en.oxforddictionaries.com/search?filter=dictionary&query="+Word
    br = mechanize.Browser()
    br.set_handle_robots(False)
    response = br.open(url)
    text = response.read()
    return "no exact matches"  not in text.lower()

print [valid for valid in solution[:10] if checkWord(valid)]