Como encontrar a lista de possíveis palavras de uma matriz de letras [Boggle Solver]

Ultimamente, tenho jogado um jogo no meu iPhone chamado Scramble. Alguns de vocês podem conhecer este jogo como Boggle. Essencialmente, quando o jogo começa, você obtém uma matriz de letras da seguinte forma:

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

O objetivo do jogo é encontrar o maior número possível de palavras que possam ser formadas encadeando letras. Você pode começar com qualquer letra e todas as letras que a cercam são justas e, depois de passar para a próxima letra, todas as letras que cercam essa letra são justas, exceto as letras usadas anteriormente . Então na grade acima, por exemplo, eu poderia vir acima com as palavras LOB, TUX, SEA, FAME, etc. As palavras devem ter no mínimo 3 caracteres e um máximo de caracteres NxN, o que seria 16 neste jogo, mas pode variar em algumas implementações . Embora este jogo seja divertido e viciante, aparentemente eu não sou muito bom nisso e queria trapacear um pouco, criando um programa que me desse as melhores palavras possíveis (quanto mais longa a palavra, mais pontos você ganha).

_{(fonte: boggled.org )}

Infelizmente, não sou muito bom com algoritmos ou suas eficiências e assim por diante. Minha primeira tentativa usa um dicionário como este (~ 2,3 MB) e faz uma pesquisa linear tentando combinar combinações com entradas do dicionário. Demora muito tempo para encontrar as palavras possíveis e, como você recebe apenas 2 minutos por rodada, isso simplesmente não é adequado.

Estou interessado em ver se algum Stackoverflowers pode apresentar soluções mais eficientes. Estou procurando principalmente soluções usando os Big 3 Ps: Python, PHP e Perl, embora qualquer coisa com Java ou C ++ seja legal também, pois a velocidade é essencial.

SOLUÇÕES ATUAIS :

• Adam Rosenfield, Python, ~ 20 anos
• John Fouhy, Python, ~ 3s
• Kent Fredric, Perl, ~ 1s
• Darius Bacon, Python, ~ 1s
• rvarcher, VB.NET (link ao vivo) , ~ 1s
• Paolo Bergantino, PHP (link ao vivo) , ~ 5s (~ 2s localmente)

Minha resposta funciona como as outras aqui, mas vou publicá-la porque parece um pouco mais rápida do que as outras soluções Python, de configurar o dicionário mais rapidamente. (Verifiquei isso com a solução de John Fouhy.) Após a instalação, o tempo para resolver é baixo no barulho.

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)

Uso da amostra:

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

Editar: filtrar palavras com menos de 3 letras.

Edit 2: Fiquei curioso por que a solução Perl de Kent Fredric era mais rápida; ela usa correspondência de expressão regular em vez de um conjunto de caracteres. Fazer o mesmo em Python duplica a velocidade.

A solução mais rápida que você obterá provavelmente envolverá o armazenamento do seu dicionário em três tentativas . Em seguida, crie uma fila de trigêmeos ( x , y , s ), em que cada elemento na fila corresponde a um prefixo s de uma palavra que pode ser escrita na grade, terminando no local ( x , y ). Inicialize a fila com N x N elementos (onde N é o tamanho da sua grade), um elemento para cada quadrado na grade. Em seguida, o algoritmo prossegue da seguinte maneira:

Enquanto a fila não estiver vazia:
  Retirar da fila uma tripla (x, y, s)
  Para cada quadrado (x ', y') com a letra c adjacente a (x, y):
    Se s + c é uma palavra, produza s + c
    Se s + c for o prefixo de uma palavra, insira (x ', y', s + c) na fila

Se você armazena seu dicionário em uma tentativa, é possível testar se s + c é uma palavra ou um prefixo de uma palavra em tempo constante (desde que você também mantenha alguns metadados extras em cada dado da fila, como um ponteiro para o nó atual no experimento), então o tempo de execução desse algoritmo é O (número de palavras que podem ser escritas).

[Editar] Aqui está uma implementação em Python que acabei de codificar:

#!/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

Exemplo de uso:

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

Resultado:

['fa', 'xi', 'ie', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', 'eu', ' lo ',' li ',' oe ',' boi ',' em ',' ea ',' ea ',' es ',' wa ',' nós ',' wa ',' bo ',' bu ' , 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli', ' elm ',' elb ',' ami ',' ama ',' ame ',' aes ',' awl ',' wake ',' incrédulo ',' wake ',' mix ',' mim ',' mil ' , 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei ',' leo ',' mentira ',' lim ',' óleo ',' olm ',' ovelha ',' eme ',' cera ',' waf ',' wae ',' waw ',' wem ' , 'wea', 'wea', 'was', 'waw', 'wae', 'bob', 'blo', 'bub', 'but', 'ast', 'ase', 'asa', ' awl ',' wake ',' incrédulo ',' wake ',' aes ',' swa ',' swa ',' costurar ',' mar ',' mar ',' serra ',' tux ',' banheira ' , 'tut', 'twa', 'twa', 'tst', 'utu', 'fama', 'fama', 'ixil', 'imam', 'amli', 'amil', 'ambo', ' axil ',' axle ',' mimi ',' mima ',' mime ',' milo ','milha ',' mewl ',' mese ',' mesa ',' lolo ',' lobo ',' lima ',' lime ',' limb ',' lile ',' oime ',' oleo ',' olio ' , 'oboé', 'obol', 'emim', 'emil', 'leste', 'facilidade', 'wame', 'wawa', 'wawa', 'weam', 'west', 'wese', ' wast ',' wase ',' wawa ',' wawa ',' boil ',' bolo ',' bole ',' bobo ',' blob ',' bleo ',' bubo ',' asem ',' stub ' , 'stut', 'swam', 'semi', 'seme', 'costura', '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 ' ]sawbwa ']sawbwa ']

Notas: Este programa não gera palavras de uma letra ou filtra de acordo com o tamanho da palavra. É fácil adicionar, mas não é realmente relevante para o problema. Também gera algumas palavras várias vezes, se puderem ser escritas de várias maneiras. Se uma determinada palavra puder ser escrita de várias maneiras diferentes (na pior das hipóteses: todas as letras da grade são iguais (por exemplo, 'A') e uma palavra como 'aaaaaaaaaa' está no seu dicionário), o tempo de execução ficará terrivelmente exponencial . A filtragem de duplicatas e a classificação são triviais devido ao término do algoritmo.

Para uma aceleração de dicionário, há uma transformação / processo geral que você pode fazer para reduzir bastante as comparações de dicionário com antecedência.

Dado que a grade acima contém apenas 16 caracteres, alguns deles duplicados, você pode reduzir bastante o número total de chaves no seu dicionário, simplesmente filtrando as entradas que possuem caracteres inatingíveis.

Eu pensei que essa era a otimização óbvia, mas vendo que ninguém fez isso, estou mencionando.

Isso me reduziu de um dicionário de 200.000 chaves para apenas 2.000 chaves simplesmente durante o passe de entrada. Isso reduz, no mínimo, a sobrecarga da memória, e é certo que é mapeado para um aumento de velocidade em algum lugar, pois a memória não é infinitamente rápida.

Implementação Perl

Minha implementação é um pouco pesada, porque enfatizei a capacidade de saber o caminho exato de cada string extraída, não apenas a validade nela.

Também tenho algumas adaptações que teoricamente permitiriam que uma grade com furos funcionasse e grades com linhas de tamanhos diferentes (supondo que você tenha a entrada correta e ela se alinha de alguma forma).

O filtro inicial é de longe o gargalo mais significativo no meu aplicativo, como suspeito anteriormente, comentando que a linha incha de 1,5s para 7,5s.

Após a execução, parece que todos os dígitos estão com suas próprias palavras válidas, mas tenho certeza de que é devido ao modo como o arquivo do dicionário funciona.

Está um pouco inchado, mas pelo menos eu reutilizo o Tree :: Trie do cpan

Parte disso foi inspirada parcialmente pelas implementações existentes, algumas das quais eu já tinha em mente.

Críticas construtivas e formas de melhorar as boas-vindas (/ me observa que ele nunca procurou no CPAN um solucionador de problemas , mas isso era mais divertido de resolver)

atualizado para novos critérios

#!/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 ) ;
};

Informações de arco / execução para comparação:

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% ==============================

Mais resmungos nessa otimização Regex

A otimização de regex que uso é inútil para dicionários com várias resoluções, e para várias resoluções, você desejará um dicionário completo, não um pré-aparado.

No entanto, dito isso, para soluções pontuais, é realmente rápido. (Regex Perl estão em C! :))

Aqui estão algumas adições de código variadas:

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 não filtrado
não filtrado 8,16 - -94%
filtrada 0,464 1658% -

_{ps: 8,16 * 200 = 27 minutos.}

Você pode dividir o problema em duas partes:

1. Algum tipo de algoritmo de pesquisa que enumerará possíveis sequências na grade.
2. Uma maneira de testar se uma string é uma palavra válida.

Idealmente, (2) também deve incluir uma maneira de testar se uma sequência de caracteres é o prefixo de uma palavra válida - isso permitirá que você faça uma busca na sua pesquisa e economize bastante tempo.

Trie de Adam Rosenfield é uma solução para (2). É elegante e provavelmente o que seu especialista em algoritmos preferiria, mas com linguagens modernas e computadores modernos, podemos ser um pouco mais preguiçosos. Além disso, como Kent sugere, podemos reduzir o tamanho do dicionário descartando palavras com letras que não estão presentes na grade. Aqui está um 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

Uau; teste de prefixo em tempo constante. Demora alguns segundos para carregar o dicionário que você vinculou, mas apenas alguns :-) (observe isso words <= prefixes)

Agora, para a parte (1), estou inclinado a pensar em termos de gráficos. Então, eu vou construir um dicionário que se parece com isso:

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

ou seja, graph[(x, y)]é o conjunto de coordenadas que você pode alcançar da posição (x, y). Também adicionarei um nó fictício Noneque se conectará a tudo.

Construir é um pouco desajeitado, porque há 8 posições possíveis e você precisa fazer uma verificação de limites. Aqui está um código python correspondentemente desajeitado:

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

Esse código também cria um mapeamento de dicionário (x,y)para o caractere correspondente. Isso me permite transformar uma lista de posições em uma palavra:

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

Por fim, fazemos uma pesquisa profunda. O procedimento básico é:

1. A pesquisa chega em um nó específico.
2. Verifique se o caminho até agora pode fazer parte de uma palavra. Caso contrário, não explore mais esse ramo.
3. Verifique se o caminho até agora é uma palavra. Nesse caso, adicione à lista de resultados.
4. Explore todas as crianças que não fazem parte do caminho até agora.

Pitão:

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)

Execute o código como:

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)

e inspecione respara ver as respostas. Aqui está uma lista de palavras encontradas para o seu exemplo, classificadas por tamanho:

 ['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']

O código leva (literalmente) alguns segundos para carregar o dicionário, mas o resto é instantâneo na minha máquina.

Minha tentativa em Java. Demora cerca de 2 s para ler o arquivo e criar trie, e cerca de 50 ms para resolver o quebra-cabeça. Eu usei o dicionário vinculado na pergunta (há algumas palavras que eu não sabia existir em inglês, como 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

O código fonte consiste em 6 classes. Vou publicá-las abaixo (se essa não é a prática correta no StackOverflow, por favor me diga).

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.Util

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;
    }
}

Acho que você provavelmente passará a maior parte do tempo tentando combinar palavras que não podem ser construídas pela grade de letras. Então, a primeira coisa que eu faria é tentar acelerar essa etapa e isso deve levá-lo até lá.

Para isso, eu expressaria novamente a grade como uma tabela de possíveis "movimentos" que você indexa pela transição de letras que está observando.

Comece atribuindo a cada letra um número do alfabeto inteiro (A = 0, B = 1, C = 2, ... e assim por diante).

Vamos pegar este exemplo:

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

E, por enquanto, vamos usar o alfabeto das letras que temos (normalmente você provavelmente desejaria usar o mesmo alfabeto todo o tempo):

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

Em seguida, você cria uma matriz booleana 2D que informa se você tem uma certa transição de letra disponível:

     |  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

Agora passe pela sua lista de palavras e converta as palavras em transições:

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

Em seguida, verifique se essas transições são permitidas procurando-as na sua tabela:

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

Se todos forem permitidos, é possível que essa palavra seja encontrada.

Por exemplo, a palavra "capacete" pode ser descartada na quarta transição (m para e: helMEt), pois essa entrada na sua tabela é falsa.

E a palavra hamster pode ser descartada, uma vez que a primeira transição (h para a) não é permitida (nem existe na sua tabela).

Agora, para as provavelmente poucas palavras restantes que você não eliminou, tente encontrá-las na grade da maneira que você está fazendo agora ou como sugerido em algumas das outras respostas aqui. Isso evita falsos positivos resultantes de saltos entre letras idênticas em sua grade. Por exemplo, a palavra "ajuda" é permitida pela tabela, mas não pela grade.

Mais algumas dicas de melhoria de desempenho sobre essa ideia:

1. Em vez de usar uma matriz 2D, use uma matriz 1D e simplesmente calcule o índice da segunda letra. Portanto, em vez de uma matriz de 12x12 como acima, faça uma matriz 1D de comprimento 144. Se você sempre usar o mesmo alfabeto (ou seja, uma matriz 26x26 = 676x1 para o alfabeto inglês padrão), mesmo que nem todas as letras apareçam na sua grade , você pode pré-calcular os índices nessa matriz 1D que precisa testar para corresponder às palavras do seu dicionário. Por exemplo, os índices para 'olá' no exemplo acima seriam

   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. Estenda a ideia a uma tabela 3D (expressa como uma matriz 1D), ou seja, todas as combinações de 3 letras permitidas. Dessa forma, você pode eliminar ainda mais palavras imediatamente e reduzir o número de pesquisas de matriz para cada palavra em 1: Para 'hello', você precisa apenas de 3 pesquisas de matriz: hel, ell, llo. A propósito, será muito rápido criar esta tabela, pois existem apenas 400 movimentos possíveis de três letras em sua grade.

3. Pré-calcule os índices dos movimentos na sua grade que você precisa incluir na sua tabela. Para o exemplo acima, você precisa definir as seguintes entradas como 'True':

   (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. Também represente sua grade de jogo em uma matriz 1-D com 16 entradas e faça com que a tabela pré-calculada em 3. contenha os índices nessa matriz.

Tenho certeza de que, se você usar essa abordagem, poderá fazer com que seu código funcione incrivelmente rápido, se você tiver o dicionário pré-calculado e já carregado na memória.

BTW: Outra coisa legal a se fazer, se você estiver criando um jogo, é executar esse tipo de coisa imediatamente em segundo plano. Comece a gerar e resolver o primeiro jogo enquanto o usuário ainda estiver olhando para a tela de título do seu aplicativo e colocando o dedo na posição para pressionar "Play". Em seguida, gere e resolva o próximo jogo conforme o usuário joga o anterior. Isso deve lhe dar muito tempo para executar seu código.

(Eu gosto desse problema, provavelmente terei a tentação de implementar minha proposta em Java nos próximos dias para ver como ela realmente funcionaria ... Eu publicarei o código aqui assim que o fizer.)

ATUALIZAR:

Ok, eu tive algum tempo hoje e implementei essa idéia em Java:

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

Aqui estão alguns resultados:

Para a grade da imagem postada na pergunta original (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

Para as cartas postadas como exemplo na pergunta original (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

Para a seguinte grade 5x5:

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

dá o seguinte:

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

Para isso, usei a Lista de Palavras Scrabble do Torneio TWL06 , já que o link na pergunta original não funciona mais. Este arquivo tem 1,85 MB, por isso é um pouco mais curto. E a buildDictionaryfunção lança todas as palavras com menos de 3 letras.

Aqui estão algumas observações sobre o desempenho disso:

• É cerca de 10 vezes mais lento que o desempenho relatado da implementação do OCaml de Victor Nicollet. Se isso é causado pelo algoritmo diferente, pelo dicionário mais curto que ele usou, pelo fato de seu código ser compilado e o meu ser executado em uma máquina virtual Java ou pelo desempenho de nossos computadores (o meu é um Intel Q6600 @ 2.4MHz executando o WinXP), Eu não sei. Mas é muito mais rápido que os resultados das outras implementações citadas no final da pergunta original. Portanto, se esse algoritmo é superior ao dicionário trie ou não, não sei neste momento.

• O método de tabela usado em checkWordTriplets()produz uma aproximação muito boa às respostas reais. Somente 1 em 3 a 5 palavras aprovadas serão reprovadas no checkWords()teste (consulte o número de candidatos versus o número de palavras reais acima).

• Algo que você não pode ver acima: a checkWordTriplets()função leva cerca de 3,65 ms e, portanto, é totalmente dominante no processo de busca. A checkWords()função ocupa praticamente os restantes 0,05-0,20 ms.

• O tempo de execução da checkWordTriplets()função depende linearmente do tamanho do dicionário e é praticamente independente do tamanho da placa!

• O tempo de execução checkWords()depende do tamanho do quadro e do número de palavras não descartadas checkWordTriplets().

• A checkWords()implementação acima é a primeira versão mais idiota que eu criei. Basicamente, não é otimizado. Mas, comparado a checkWordTriplets()isso, é irrelevante para o desempenho total do aplicativo, então não me preocupei. Porém , se o tamanho da placa aumentar, essa função ficará cada vez mais lenta e, eventualmente, começará a importar. Então, precisaria ser otimizado também.

• Uma coisa legal desse código é sua flexibilidade:

  • Você pode alterar facilmente o tamanho da placa: Atualize a linha 10 e a matriz String transmitida para initializeBoard().
  • Ele suporta alfabetos maiores / diferentes e pode lidar com coisas como tratar 'Qu' como uma letra sem sobrecarga de desempenho. Para fazer isso, seria necessário atualizar a linha 9 e o par de lugares em que os caracteres são convertidos em números (atualmente simplesmente subtraindo 65 do valor ASCII)

Ok, mas acho que até agora este post está bom o suficiente. Definitivamente, posso responder a quaisquer perguntas que você possa ter, mas vamos passar para os comentários.

Surpreendentemente, ninguém tentou uma versão PHP disso.

Esta é uma versão PHP funcional da solução Python de John Fouhy.

Embora eu tenha tomado algumas dicas das respostas de todos os outros, isso é principalmente copiado de John.

$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);

Aqui está um link ao vivo, se você quiser experimentá-lo. Embora demore ~ ​​2s na minha máquina local, demore ~ ​​5s no meu servidor web. Em ambos os casos, não é muito rápido. Ainda assim, é bastante hediondo, portanto, posso imaginar que o tempo possa ser reduzido significativamente. Qualquer indicação de como fazer isso seria apreciada. A falta de tuplas do PHP tornou as coordenadas estranhas de se trabalhar e a minha incapacidade de compreender exatamente o que diabos está acontecendo não ajudou em nada.

EDIT : algumas correções levam menos de 1s localmente.

Não está interessado em VB? :) Eu não pude resistir. Resolvi isso de maneira diferente do que muitas das soluções apresentadas aqui.

Meus horários são:

• Carregando o dicionário e os prefixos de palavras em uma hashtable: 0,5 a 1 segundos.
• Encontrando as palavras: média de 10 milissegundos.

EDIT: Os tempos de carregamento do dicionário no servidor host estão em execução de 1 a 1,5 segundos a mais que o meu computador doméstico.

Não sei o quanto os tempos se deteriorarão com a carga no servidor.

Eu escrevi minha solução como uma página da web em .Net. myvrad.com/boggle

Estou usando o dicionário referenciado na pergunta original.

As letras não são reutilizadas em uma palavra. Somente palavras com 3 caracteres ou mais são encontradas.

Estou usando uma hashtable de todos os prefixos e palavras exclusivas em vez de um trie. Eu não sabia sobre a Trie, então aprendi algo lá. A idéia de criar uma lista de prefixos de palavras além das palavras completas é o que finalmente reduziu meus tempos a um número respeitável.

Leia os comentários do código para obter detalhes adicionais.

Aqui está o código:

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

Assim que vi a declaração do problema, pensei em "Trie". Mas, como vários outros pôsteres fizeram uso dessa abordagem, procurei outra abordagem apenas para ser diferente. Infelizmente, a abordagem Trie tem melhor desempenho. Executei a solução Perl de Kent na minha máquina e demorou 0,31 segundos para executar, depois de adaptá-la para usar meu arquivo de dicionário. Minha própria implementação perl levou 0,54 segundos para ser executada.

Esta foi a minha abordagem:

1. Crie um hash de transição para modelar as transições legais.

2. Repita todas as 16 ^ 3 combinações possíveis de três letras.

   • No loop, exclua transições ilegais e repita visitas à mesma praça. Forme todas as seqüências legais de 3 letras e armazene-as em um hash.

3. Em seguida, percorra todas as palavras do dicionário.

   • Excluir palavras muito longas ou curtas
   • Deslize uma janela de três letras por cada palavra e veja se ela está entre os combos de três letras da etapa 2. Exclua as palavras que falham. Isso elimina a maioria das não correspondências.
   • Se ainda não for eliminado, use um algoritmo recursivo para ver se a palavra pode ser formada fazendo caminhos através do quebra-cabeça. (Esta parte é lenta, mas é chamada com pouca frequência.)

4. Imprima as palavras que encontrei.

   Tentei sequências de 3 e 4 letras, mas as sequências de 4 letras atrasaram o programa.

No meu código, eu uso / usr / share / dict / words no meu dicionário. Ele é padrão no MAC OS X e em muitos sistemas Unix. Você pode usar outro arquivo, se quiser. Para quebrar um quebra-cabeça diferente, basta alterar a variável @puzzle. Isso seria fácil de adaptar para matrizes maiores. Você só precisa alterar o hash% transitions e o hash% legalTransitions.

A força dessa solução é que o código é curto e a estrutura de dados simples.

Aqui está o código Perl (que usa muitas variáveis ​​globais, eu sei):

#!/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.
}

Eu sei que estou super atrasado, mas eu fiz um desses há um tempo atrás em PHP - apenas por diversão também ...

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Encontradas 75 palavras (133 pts) em 0,90108 segundos

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

Dá alguma indicação do que o programa está realmente fazendo - cada letra é onde começa a examinar os padrões enquanto cada '.' mostra um caminho que ele tentou seguir. O mais '.' há quanto mais ele procurou.

Deixe-me saber se você quer o código ... é uma mistura horrível de PHP e HTML que nunca foi feita para ver a luz do dia, então não ouso postá-lo aqui: P

Passei 3 meses trabalhando em uma solução para o problema dos 10 melhores pontos densos 5x5 Boggle boards.

O problema agora está resolvido e apresentado com a divulgação completa em 5 páginas da web. Por favor entre em contato em caso de duvidas.

O algoritmo de análise da placa usa uma pilha explícita para percorrer pseudo-recursivamente os quadrados da placa através de um Gráfico de Palavras Acíclicas Dirigidas com informações diretas sobre filhos e um mecanismo de rastreamento de carimbo de data / hora. Essa pode ser a estrutura de dados de léxico mais avançada do mundo.

O esquema avalia cerca de 10.000 placas muito boas por segundo em um núcleo quádruplo. (9500+ pontos)

Página da Web pai:

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

Páginas da Web de componentes:

Painel de avaliação ideal - http://www.pathcom.com/~vadco/binary.html

Estrutura avançada do léxico - http://www.pathcom.com/~vadco/adtdawg.html

Algoritmo de análise de placa http://www.pathcom.com/~vadco/guns.html

Processamento em lote paralelo - http://www.pathcom.com/~vadco/parallel.html

- Esse conjunto abrangente de trabalho interessará apenas uma pessoa que exige o melhor.

Seu algoritmo de pesquisa diminui continuamente a lista de palavras à medida que sua pesquisa continua?

Por exemplo, na pesquisa acima, existem apenas 13 letras nas quais suas palavras podem começar (reduzindo efetivamente para a metade o número de letras iniciais).

À medida que você adiciona mais permutações de letras, isso diminui ainda mais os conjuntos de palavras disponíveis, diminuindo a pesquisa necessária.

Eu começaria por aí.

Eu teria que pensar mais em uma solução completa, mas como uma otimização útil, pergunto-me se vale a pena pré-calcular uma tabela de frequências de digramas e trigramas (combinações de 2 e 3 letras) com base em todas as palavras do seu dicionário e use-o para priorizar sua pesquisa. Eu iria com as letras iniciais das palavras. Portanto, se o seu dicionário contiver as palavras "Índia", "Água", "Extremo" e "Extraordinário", sua tabela pré-calculada poderá ser:

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

Em seguida, procure esses digramas na ordem de semelhança (primeiro EX, depois WA / IN)

Primeiro, leia como um dos designers de linguagem C # resolveu um problema relacionado: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .

Assim como ele, você pode começar com um dicionário e o canonacalize palavras criando um dicionário a partir de uma matriz de letras classificadas em ordem alfabética para uma lista de palavras que podem ser escritas a partir dessas letras.

Em seguida, comece a criar as possíveis palavras do quadro e procure-as. Suspeito que isso o levará muito longe, mas certamente existem mais truques que podem acelerar as coisas.

Sugiro fazer uma árvore de letras com base em palavras. A árvore seria composta de estruturas de letras, assim:

letter: char
isWord: boolean

Então você constrói a árvore, com cada profundidade adicionando uma nova letra. Em outras palavras, no primeiro nível, haveria o alfabeto; então, de cada uma dessas árvores, haveria outras 26 entradas, e assim por diante, até que você soletrasse todas as palavras. Segure-se nessa árvore analisada, e todas as respostas possíveis serão mais rápidas para procurar.

Com essa árvore analisada, você pode encontrar soluções rapidamente. Aqui está o pseudo-código:

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.

Isso pode ser acelerado com um pouco de programação dinâmica. Por exemplo, na sua amostra, os dois 'A's estão ao lado de um' E 'e um' W ', que (a partir do momento em que eles os atingem) seriam idênticos. Não tenho tempo suficiente para realmente explicar o código para isso, mas acho que você pode entender a ideia.

Além disso, tenho certeza de que você encontrará outras soluções se pesquisar no Google para "Boggle solver".

Apenas por diversão, eu implementei um no bash. Não é super rápido, mas razoável.

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

Hilário. Eu quase postei a mesma pergunta há alguns dias devido ao mesmo jogo! No entanto, não o fiz, porque apenas pesquisei no Google por python boggle solver e obtive todas as respostas que eu poderia desejar.

Percebo que o tempo dessa pergunta chegou e se foi, mas desde que eu estava trabalhando em um solucionador e me deparei com isso enquanto pesquisava no Google, pensei em publicar uma referência à minha, pois parece um pouco diferente de outras.

Eu escolhi ir com uma matriz plana para o tabuleiro de jogo e fazer caçadas recursivas de cada letra no tabuleiro, atravessando de vizinho válido para vizinho válido, estendendo a busca se a lista atual de letras se um prefixo válido em um índice. Ao percorrer a noção da palavra atual, há uma lista de índices no quadro, não letras que compõem uma palavra. Ao verificar o índice, os índices são convertidos em letras e a verificação é feita.

O índice é um dicionário de força bruta que se parece um pouco com um trie, mas permite consultas Pythonic ao índice. Se as palavras 'gato' e 'atender' estiverem na lista, você poderá obter isso no dicionário:

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

Portanto, se a current_word for 'ca', você saberá que é um prefixo válido porque 'ca' in dretorna True (continue a travessia do quadro). E se a palavra atual for 'cat', você saberá que é uma palavra válida porque é um prefixo válido e'cat' in d['cat'] retorna True também.

Se você sentir isso, é permitido um código legível que não parece muito lento. Como todo mundo, a despesa neste sistema é a leitura / construção do índice. Resolver a placa é praticamente barulho.

O código está em http://gist.github.com/268079 . É intencionalmente vertical e ingênuo, com muita verificação explícita de validade, porque eu queria entender o problema sem criá-lo com um monte de magia ou obscuridade.

Eu escrevi meu solucionador em C ++. Eu implementei uma estrutura de árvore personalizada. Não tenho certeza se pode ser considerado um trie, mas é semelhante. Cada nó possui 26 ramificações, 1 para cada letra do alfabeto. Atravesso os galhos do painel de boggle em paralelo com os galhos do meu dicionário. Se o ramo não existir no dicionário, paro de procurá-lo no quadro do Boggle. Eu converto todas as letras do quadro para ints. Então 'A' = 0. Como são apenas matrizes, a pesquisa é sempre O (1). Cada nó armazena se completa uma palavra e quantas palavras existem em seus filhos. A árvore é podada à medida que as palavras reduzem a busca repetida pelas mesmas palavras. Eu acredito que a poda também é O (1).

CPU: Pentium SU2700 1.3GHz
RAM: 3gb

Carrega dicionário de 178.590 palavras em <1 segundo.
Resolve Boggle 100x100 (boggle.txt) em 4 segundos. ~ 44.000 palavras encontradas.
A resolução de um Boggle 4x4 é muito rápida para fornecer uma referência significativa. :)

Fast Boggle Solver Repositório GitHub

Dado um quadro Boggle com N linhas e colunas M, vamos assumir o seguinte:

• N * M é substancialmente maior que o número de palavras possíveis
• N * M é substancialmente maior que a palavra mais longa possível

Sob essas suposições, a complexidade desta solução é O (N * M).

Penso que comparar os tempos de execução deste quadro de exemplo de muitas maneiras erra o objetivo, mas, por uma questão de perfeição, esta solução é concluída em <0,2s no meu moderno MacBook Pro.

Esta solução encontrará todos os caminhos possíveis para cada palavra no corpus.

#!/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}"

Esta solução também fornece instruções para pesquisar no quadro especificado

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

Resultado:

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  → → ↑ ↘ →

Código:

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 __name__ == '__main__':
    main(trie_node)

Eu implementei uma solução no OCaml . Ele pré-compila um dicionário como um trie e usa frequências de seqüência de duas letras para eliminar bordas que nunca poderiam aparecer em uma palavra para acelerar ainda mais o processamento.

Ele resolve seu quadro de exemplo em 0,35 ms (com um tempo de inicialização adicional de 6 ms, relacionado principalmente ao carregamento do teste na memória).

As soluções encontradas:

["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"]

Uma solução JavaScript Node.JS. Calcula todas as 100 palavras exclusivas em menos de um segundo, incluindo a leitura do arquivo do dicionário (MBA 2012).

Resultado:
["FAM", "TUX", "TUB", "FAE", "ELI", "ELM", "ELB", "TWA", "TWA", "SERRA", "AMI", "SWA" , "SWA", "AME", "MAR", "SEW", "AES", "AWL", "AWE", "MAR", "AWA", "MIX", "MIL", "AST", " ASE "," MAX "," MAE "," MAW "," MEW "," AWE "," MES "," AWL "," MENTIRA "," LIM "," AWA "," AES "," MAS " , "BLO", "WAS", "WAE", "WEA", "LEI", "LEO", "LOB", "LOX", "MAE", "ÓLEO", "OLM", "WEA", " WAE "," WAX "," WAF ","MILO", "ORIENTE", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "MEMBRO", "WASE" "," WAST "," BLEO "," STUB "," BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME ", "ASEM", "MILE", "AMIL", "SEAX", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST" "," AWEST "," LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LESTE "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," MEMBRO "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]LESTE "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," MEMBRO "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "Membro", "WASE", "WAST", "BLEO", "STUB", "BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "Membro", "WASE", "WAST", "BLEO", "STUB", "BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE "," FAMBLE "]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 "]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 "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]

Código:

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

Então, eu queria adicionar outra maneira PHP de resolver isso, já que todo mundo adora PHP. Gostaria de fazer um pouco de refatoração, como usar uma correspondência de expressão expressa no arquivo do dicionário, mas agora estou carregando o arquivo inteiro do dicionário em uma lista de palavras.

Eu fiz isso usando uma ideia de lista vinculada. Cada nó tem um valor de caractere, um valor de localização e um próximo ponteiro.

O valor da localização é como descobri se dois nós estão conectados.

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

Portanto, usando essa grade, eu sei que dois nós estão conectados se a localização do primeiro nó for igual à localização dos segundos nós +/- 1 para a mesma linha, +/- 9, 10, 11 para a linha acima e abaixo.

Eu uso recursão para a pesquisa principal. Retira uma palavra da wordList, localiza todos os pontos de partida possíveis e, em seguida, localiza recursivamente a próxima conexão possível, lembrando que ela não pode ir para um local que já está usando (e é por isso que adiciono $ notInLoc).

De qualquer forma, eu sei que ele precisa de refatoração e gostaria de ouvir pensamentos sobre como torná-lo mais limpo, mas produz os resultados corretos com base no arquivo de dicionário que estou usando. Dependendo do número de vogais e combinações no tabuleiro, leva de 3 a 6 segundos. Eu sei que uma vez que eu pregar os resultados do dicionário, isso reduzirá significativamente.

<?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);

    ?>

Sei que estou muito atrasado na festa, mas implementei, como exercício de codificação, um solucionador de problemas em várias linguagens de programação (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) e Eu pensei que alguém poderia estar interessado naqueles, então deixo o link aqui: https://github.com/AmokHuginnsson/boggle-solvers

Aqui está a solução Usando palavras predefinidas no kit de ferramentas NLTK O NLTK possui o pacote nltk.corpus, no qual temos um pacote chamado words e ele contém mais de 2Lakhs palavras em inglês que você pode simplesmente usar no seu programa.

Depois de criar sua matriz, converta-a em uma matriz de caracteres e execute este código

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)

Resultado:

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

Espero que consiga.

Aqui está minha implementação em java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

A criação da tentativa levou 0 horas, 0 minutos, 1 segundos, 532 milissegundos A
pesquisa de palavras levou 0 horas, 0 minutos, 0 segundos, 92 milissegundos

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 

Nota: Eu usei o dicionário e a matriz de caracteres no início deste tópico. O código foi executado no meu MacBookPro, abaixo estão algumas informações sobre a máquina.

Nome do modelo: MacBook Pro
Identificador do modelo: MacBookPro8,1
Nome do processador: Intel Core i5
Velocidade do processador: 2,3 GHz
Número de processadores: 1
Número total de núcleos: 2
Cache L2 (por núcleo): 256 KB
Cache L3: 3 MB
Memória: 4
Versão da ROM de inicialização do GB : MBP81.0047.B0E
Versão SMC (sistema): 1.68f96

Eu também resolvi isso com Java. Minha implementação tem 269 linhas e é muito fácil de usar. Primeiro, você precisa criar uma nova instância da classe Boggler e depois chamar a função de resolução com a grade como parâmetro. Demora cerca de 100 ms para carregar o dicionário de 50 000 palavras no meu computador e encontra as palavras em 10 a 20 ms. As palavras encontradas são armazenadas em um ArrayList foundWords,.

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;
    }
}

Eu resolvi isso em c. Demora cerca de 48 ms para rodar na minha máquina (com cerca de 98% do tempo gasto carregando o dicionário do disco e criando o trie). O dicionário é / usr / share / dict / american-english que possui 62886 palavras.

Código fonte

Eu resolvi isso perfeitamente e muito rápido. Coloquei-o em um aplicativo Android. Veja o vídeo no link da Play Store para vê-lo em ação.

O Word Cheats é um aplicativo que "quebra" qualquer jogo de palavras no estilo matriz. Este aplicativo foi desenvolvido para me ajudar a trapacear no misturador de palavras. Ele pode ser usado para pesquisas de palavras, quebra-cabeças, palavras, busca de palavras, quebra de palavras, boggle e muito mais!

Pode ser visto aqui https://play.google.com/store/apps/details?id=com.harris.wordcracker

Veja o aplicativo em ação no vídeo https://www.youtube.com/watch?v=DL2974WmNAI