Cara menemukan daftar kata-kata yang mungkin dari matriks huruf [Boggle Solver]

Akhir-akhir ini saya telah memainkan game di iPhone saya yang disebut Scramble. Beberapa dari Anda mungkin tahu game ini sebagai Boggle. Intinya, saat permainan dimulai Anda mendapatkan matriks huruf-huruf seperti:

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

Tujuan permainan ini adalah untuk menemukan kata-kata sebanyak yang Anda bisa yang dapat dibentuk dengan merantai surat bersama. Anda bisa mulai dengan huruf apa saja, dan semua huruf yang mengelilinginya adalah permainan yang adil, dan kemudian setelah Anda beralih ke huruf berikutnya, semua huruf yang mengelilingi huruf itu adalah permainan yang adil, kecuali untuk huruf yang sebelumnya digunakan . Jadi dalam grid di atas, misalnya, saya bisa datang dengan kata-kata LOB, TUX, SEA, FAME, dll Kata-kata harus minimal 3 karakter, dan tidak lebih dari karakter NxN, yang akan 16 dalam game ini tetapi dapat bervariasi dalam beberapa implementasi . Meskipun permainan ini menyenangkan dan membuat ketagihan, saya tampaknya tidak terlalu ahli dalam hal itu dan saya ingin sedikit curang dengan membuat program yang akan memberi saya kata-kata terbaik (semakin lama kata semakin banyak poin yang Anda dapatkan).

_{(sumber: boggled.org )}

Sayangnya, saya tidak terlalu bagus dengan algoritma atau efisiensinya dan sebagainya. Upaya pertama saya menggunakan kamus seperti ini (~ 2.3MB) dan melakukan pencarian linier yang mencoba mencocokkan kombinasi dengan entri kamus. Ini membutuhkan waktu yang sangat lama untuk menemukan kata-kata yang mungkin, dan karena Anda hanya mendapatkan 2 menit per putaran, itu sama sekali tidak memadai.

Saya tertarik untuk melihat apakah ada Stackoverflowers dapat datang dengan solusi yang lebih efisien. Saya kebanyakan mencari solusi menggunakan Big 3 Ps: Python, PHP, dan Perl, meskipun apa pun dengan Java atau C ++ juga keren, karena kecepatan sangat penting.

SOLUSI SAAT INI :

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

Jawaban saya berfungsi seperti yang lain di sini, tetapi saya akan mempostingnya karena terlihat sedikit lebih cepat daripada solusi Python lainnya, dari mengatur kamus lebih cepat. (Saya memeriksa ini terhadap solusi John Fouhy.) Setelah pengaturan, waktu untuk menyelesaikannya turun dalam kebisingan.

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)

Penggunaan sampel:

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

Sunting: Saring kata-kata yang panjangnya kurang dari 3 huruf.

Sunting 2: Saya ingin tahu mengapa solusi Perl Kent Fredric lebih cepat; ternyata menggunakan pencocokan ekspresi reguler alih-alih sekumpulan karakter. Melakukan hal yang sama dengan Python tentang menggandakan kecepatan.

Solusi tercepat yang akan Anda dapatkan mungkin melibatkan penyimpanan kamus Anda dalam sebuah trie . Kemudian, buat antrian triplet ( x , y , s ), di mana setiap elemen dalam antrian sesuai dengan awalan s kata yang bisa dieja dalam kisi, berakhir di lokasi ( x , y ). Inisialisasi antrian dengan N x N elemen (di mana N adalah ukuran kotak Anda), satu elemen untuk setiap kotak di kisi. Kemudian, algoritma melanjutkan sebagai berikut:

Sementara antrian tidak kosong:
  Membagi tiga (x, y, s)
  Untuk setiap kotak (x ', y') dengan huruf c berdekatan dengan (x, y):
    Jika s + c adalah sebuah kata, keluaran s + c
    Jika s + c adalah awalan suatu kata, masukkan (x ', y', s + c) ke dalam antrian

Jika Anda menyimpan kamus Anda dalam sebuah trie, menguji apakah s + c adalah sebuah kata atau awalan kata dapat dilakukan dalam waktu yang konstan (asalkan Anda juga menyimpan beberapa metadata tambahan di setiap datum antrian, seperti pointer ke node saat ini dalam trie), sehingga waktu berjalan dari algoritma ini adalah O (jumlah kata yang dapat dieja).

[Sunting] Berikut ini adalah implementasi dengan Python yang baru saja saya kodekan:

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

Contoh penggunaan:

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

Keluaran:

['fa', 'xi', 'yaitu', 'io', 'el', 'am', 'kapak', 'ae', 'aw', 'mi', 'ma', 'ma', 'me', ' lo ',' li ',' oe ',' ox ',' em ',' ea ',' ea ',' es ',' wa ',' we ',' wa ',' bo ',' bo ',' bu ' , 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'imi', 'eli', ' elm ',' elb ',' ami ',' ama ',' ame ',' aes ',' awl ',' awa ',' awe ',' awa ',' awa ',' mix ',' mim ',' mil ' , 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei ',' leo ',' lie ',' lim ',' minyak ',' olm ',' ewe ',' eme ',' wax ',' waf ',' wae ',' waw ',' waw ',' wem ' , 'wea', 'wea', 'was', 'waw', 'wae', 'bob', 'blo', 'bub', 'tapi', 'ast', 'ase', 'asa', 'asa', ' awl ',' awa ',' awe ',' awa ',' aes ',' swa ',' swa ',' menjahit ',' laut ',' laut ',' melihat ',' tux ',' bak ' , 'tut', 'twa', 'twa', 'tst', 'utu', 'fama', 'fame', 'ixil', 'ixil', 'imam', 'amli', 'amil', 'ambo', ' axil ',' gandar ',' mimi ',' mima ',' mime ',' milo ','mil ',' mewl ',' mese ',' mesa ',' lolo ',' lobo ',' lima ',' lime ',' limb ',' lile ',' lile ',' oime ',' oleo ',' olio ' , 'oboe', 'obol', 'emim', 'emil', 'timur', 'santai', 'wawa', 'wawa', 'wawa', 'weam', 'weam', 'west', 'wese', ' buang ',' wase ',' wawa ',' wawa ',' boil ',' bolo ',' bole ',' bobo ',' blob ',' bleo ',' bleo ',' bubo ',' asem ',' stub ' , 'stut', 'swam', 'semi', 'seme', 'seam', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', ' twae ',' ilima ',' amble ',' axile ', 'awest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax', 'limes', 'limbo', 'limbu', 'lole', 'obole', 'emesa', ' embox ',' awest ',' swami ',' famble ',' mimble ',' maxima ',' embolo ',' embole ',' wamble ',' semese ',' semble ',' sawbwa ',' sawbwa ' ]sawbwa ']sawbwa ']

Catatan: Program ini tidak menghasilkan kata 1-huruf, atau menyaring berdasarkan panjang kata sama sekali. Itu mudah ditambahkan tetapi tidak benar-benar relevan dengan masalah tersebut. Ini juga menghasilkan beberapa kata beberapa kali jika mereka dapat dieja dalam beberapa cara. Jika kata yang diberikan dapat dieja dengan berbagai cara (kasus terburuk: setiap huruf dalam kisi adalah sama (misalnya 'A') dan kata seperti 'aaaaaaaaaa' ada di kamus Anda), maka waktu yang berjalan akan menjadi eksponensial yang mengerikan . Memfilter duplikat dan pengurutan sepele karena setelah algoritma selesai.

Untuk mempercepat kamus, ada satu transformasi / proses umum yang dapat Anda lakukan untuk mengurangi perbandingan kamus sebelumnya.

Mengingat kisi di atas hanya berisi 16 karakter, beberapa di antaranya duplikat, Anda dapat sangat mengurangi jumlah kunci total dalam kamus Anda dengan hanya memfilter entri yang memiliki karakter yang tidak dapat dicapai.

Saya pikir ini adalah optimasi yang jelas tetapi melihat tidak ada yang melakukannya saya menyebutkannya.

Itu mengurangi saya dari kamus 200.000 kunci menjadi hanya 2.000 kunci hanya selama input masuk. Paling tidak ini mengurangi overhead memori, dan itu pasti akan memetakan ke peningkatan kecepatan di suatu tempat karena memori tidak terlalu cepat.

Implementasi Perl

Implementasi saya agak terlalu berat karena saya menempatkan pentingnya untuk mengetahui jalur yang tepat dari setiap string yang diekstraksi, bukan hanya validitas di dalamnya.

Saya juga punya beberapa adaptasi di sana yang secara teori akan mengizinkan sebuah grid dengan lubang di dalamnya berfungsi, dan grid dengan garis-garis berukuran berbeda (dengan asumsi Anda mendapatkan input yang benar dan berbaris entah bagaimana).

Filter awal sejauh ini merupakan hambatan paling signifikan dalam aplikasi saya, seperti yang diduga sebelumnya, mengomentari bahwa garis menggembungkannya dari 1,5s ke 7,5s.

Setelah dieksekusi tampaknya berpikir semua angka tunggal pada kata-kata mereka sendiri yang valid, tapi saya cukup yakin itu karena cara kerja file kamus.

Agak bengkak, tapi setidaknya saya menggunakan kembali Tree :: Trie from cpan

Beberapa di antaranya terinspirasi sebagian oleh implementasi yang ada, beberapa di antaranya sudah ada dalam pikiran saya.

Kritik Konstruktif dan cara-cara itu bisa diperbaiki, selamat datang (/ saya catat dia tidak pernah mencari CPAN untuk pemecah boggle , tapi ini lebih menyenangkan untuk dilakukan)

diperbarui untuk kriteria baru

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

Lengkungan / info eksekusi untuk perbandingan:

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

Mumblings lainnya tentang Regex Optimization

Optimasi regex yang saya gunakan tidak berguna untuk kamus multi-penyelesaian, dan untuk multi-pemecahan Anda ingin kamus lengkap, bukan kamus yang sudah dipangkas.

Namun demikian, untuk pemecahan sekali saja, ini sangat cepat. (Perl regex berada di C! :))

Berikut ini beberapa penambahan kode yang berbeda:

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 tanpa filter disaring
tanpa filter 8,16 - -94%
disaring 0,464 1658% -

_{ps: 8.16 * 200 = 27 menit.}

Anda dapat membagi masalah menjadi dua bagian:

1. Beberapa jenis algoritma pencarian yang akan menghitung kemungkinan string di dalam kisi.
2. Cara menguji apakah string adalah kata yang valid.

Idealnya, (2) juga harus mencakup cara menguji apakah string merupakan awalan dari kata yang valid - ini akan memungkinkan Anda untuk memangkas pencarian Anda dan menghemat banyak waktu.

Adam Rosenfield's Trie adalah solusi untuk (2). Ini elegan dan mungkin apa yang lebih disukai oleh spesialis algoritme Anda, tetapi dengan bahasa modern dan komputer modern, kami bisa sedikit lebih malas. Juga, seperti yang disarankan Kent, kita dapat mengurangi ukuran kamus kita dengan membuang kata-kata yang tidak memiliki huruf di dalam kisi. Inilah beberapa 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

Wow; pengujian awalan waktu-konstan. Butuh beberapa detik untuk memuat kamus yang Anda tautkan, tetapi hanya beberapa :-) (perhatikan itu words <= prefixes)

Sekarang, untuk bagian (1), saya cenderung berpikir dalam bentuk grafik. Jadi saya akan membuat kamus yang terlihat seperti ini:

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

yaitu graph[(x, y)]kumpulan koordinat yang dapat Anda jangkau dari posisi (x, y). Saya juga akan menambahkan simpul boneka Noneyang akan terhubung ke semuanya.

Membangunnya agak canggung, karena ada 8 posisi yang mungkin dan Anda harus melakukan pemeriksaan batas. Berikut adalah beberapa kode python yang canggung:

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

Kode ini juga membangun pemetaan kamus (x,y)ke karakter yang sesuai. Ini memungkinkan saya mengubah daftar posisi menjadi kata:

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

Akhirnya, kami melakukan pencarian mendalam-pertama. Prosedur dasarnya adalah:

1. Pencarian tiba di simpul tertentu.
2. Periksa apakah jalur sejauh ini bisa menjadi bagian dari sebuah kata. Jika tidak, jangan menjelajahi cabang ini lebih jauh.
3. Periksa apakah jalur sejauh ini adalah sebuah kata. Jika demikian, tambahkan ke daftar hasil.
4. Jelajahi semua anak yang bukan bagian dari jalan sejauh ini.

Python:

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

    if word not in prefixes:
        return

    if word in words:
        results.add(word)

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

Jalankan kode sebagai:

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)

dan periksa resuntuk melihat jawabannya. Berikut daftar kata yang ditemukan untuk contoh Anda, diurutkan berdasarkan ukuran:

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

Kode ini membutuhkan (secara harfiah) beberapa detik untuk memuat kamus, tetapi sisanya instan di mesin saya.

Usaha saya di Jawa. Dibutuhkan sekitar 2 detik untuk membaca file dan membangun trie, dan sekitar 50 ms untuk menyelesaikan teka-teki. Saya menggunakan kamus yang ditautkan dalam pertanyaan (ada beberapa kata yang saya tidak tahu ada dalam bahasa Inggris seperti 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

Kode sumber terdiri dari 6 kelas. Saya akan mempostingnya di bawah (jika ini bukan praktik yang tepat di StackOverflow, tolong beri tahu saya).

gineer.bogglesolver. Utama

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

Saya pikir Anda mungkin akan menghabiskan sebagian besar waktu Anda mencoba mencocokkan kata-kata yang tidak mungkin dibangun oleh kotak surat Anda. Jadi, hal pertama yang akan saya lakukan adalah mencoba mempercepat langkah itu dan itu akan membuat Anda mendapatkan sebagian besar perjalanan ke sana.

Untuk ini, saya akan menyatakan kembali kotak sebagai tabel kemungkinan "bergerak" yang Anda indeks dengan transisi surat yang Anda lihat.

Mulailah dengan memberi setiap huruf suatu angka dari seluruh alfabet Anda (A = 0, B = 1, C = 2, ... dan seterusnya).

Mari kita ambil contoh ini:

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

Dan untuk sekarang, mari kita gunakan alfabet dari surat-surat yang kita miliki (biasanya Anda mungkin ingin menggunakan seluruh alfabet yang sama setiap waktu):

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

Kemudian Anda membuat array boolean 2D yang memberi tahu apakah Anda memiliki transisi huruf tertentu yang tersedia:

     |  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

Sekarang, lihat daftar kata-kata Anda dan ubah kata-katanya menjadi transisi:

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

Kemudian periksa apakah transisi ini diizinkan dengan melihatnya di tabel Anda:

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

Jika mereka semua diizinkan, ada kemungkinan kata ini dapat ditemukan.

Misalnya kata "helm" dapat dikesampingkan pada transisi ke-4 (m ke e: helMEt), karena entri di tabel Anda salah.

Dan kata hamster dapat dikesampingkan, karena transisi pertama (h ke a) tidak diperbolehkan (bahkan tidak ada di meja Anda).

Sekarang, untuk kata-kata tersisa yang mungkin sangat sedikit yang tidak Anda hilangkan, cobalah untuk benar-benar menemukannya di grid seperti yang Anda lakukan sekarang atau seperti yang disarankan dalam beberapa jawaban lain di sini. Ini untuk menghindari kesalahan positif yang dihasilkan dari lompatan di antara huruf-huruf identik di kisi Anda. Misalnya kata "bantuan" diizinkan oleh tabel, tetapi tidak oleh grid.

Beberapa tips peningkatan kinerja lebih lanjut tentang ide ini:

1. Alih-alih menggunakan array 2D, gunakan array 1D dan cukup hitung sendiri indeks huruf kedua. Jadi, alih-alih array 12x12 seperti di atas, buat array 1D dengan panjang 144. Jika Anda selalu menggunakan alfabet yang sama (yaitu array 26x26 = 676x1 untuk alfabet bahasa Inggris standar), bahkan jika tidak semua huruf muncul di kisi Anda , Anda dapat melakukan pra-komputasi indeks ke dalam array 1D ini yang perlu Anda uji agar sesuai dengan kata-kata kamus Anda. Sebagai contoh, indeks untuk 'halo' pada contoh di atas adalah

   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. Perluas ide ke tabel 3D (dinyatakan sebagai array 1D), yaitu semua kombinasi 3 huruf yang diizinkan. Dengan begitu Anda dapat menghilangkan lebih banyak kata dengan segera dan Anda mengurangi jumlah pencarian array untuk setiap kata sebanyak 1: Untuk 'halo', Anda hanya perlu 3 pencarian array: hel, ell, llo. Omong-omong, ini akan sangat cepat untuk membangun tabel ini, karena hanya ada 400 kemungkinan gerakan 3 huruf di kisi Anda.

3. Pra-hitung indeks gerakan di kisi Anda yang perlu Anda sertakan dalam tabel Anda. Untuk contoh di atas, Anda perlu mengatur entri berikut ke 'Benar':

   (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. Juga mewakili kisi permainan Anda dalam larik 1-D dengan 16 entri dan memiliki tabel 3. yang dihitung sebelumnya berisi indeks ke dalam larik ini.

Saya yakin jika Anda menggunakan pendekatan ini, Anda bisa membuat kode Anda berjalan sangat cepat, jika kamus Anda sudah dihitung sebelumnya dan sudah dimuat ke dalam memori.

BTW: Hal lain yang menyenangkan untuk dilakukan, jika Anda membangun game, adalah menjalankan hal-hal semacam ini segera di latar belakang. Mulai membuat dan menyelesaikan gim pertama saat pengguna masih melihat layar judul di aplikasi Anda dan memasukkan jari ke posisi untuk menekan "Mainkan". Kemudian hasilkan dan selesaikan game berikutnya saat pengguna memainkan yang sebelumnya. Itu akan memberi Anda banyak waktu untuk menjalankan kode Anda.

(Saya suka masalah ini, jadi saya mungkin akan tergoda untuk mengimplementasikan proposal saya di Jawa suatu hari nanti untuk melihat bagaimana itu benar-benar melakukan ... Saya akan memposting kode di sini setelah saya melakukannya.)

MEMPERBARUI:

Oke, saya punya waktu hari ini dan mengimplementasikan ide ini di Jawa:

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

Berikut ini beberapa hasilnya:

Untuk kisi-kisi dari gambar yang diposting dalam pertanyaan asli (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

Untuk surat-surat yang diposting sebagai contoh dalam pertanyaan asli (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

Untuk 5x5-grid berikut:

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

ini memberikan ini:

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

Untuk ini saya menggunakan TWL06 Tournament Scrabble Word List , karena tautan dalam pertanyaan awal tidak lagi berfungsi. File ini 1.85MB, jadi sedikit lebih pendek. Dan buildDictionaryfungsinya membuang semua kata dengan kurang dari 3 huruf.

Berikut adalah beberapa pengamatan tentang kinerja ini:

• Ini sekitar 10 kali lebih lambat dari kinerja OCaml Victor Nicollet yang dilaporkan. Apakah ini disebabkan oleh algoritma yang berbeda, kamus pendek yang digunakannya, fakta bahwa kodenya dikompilasi dan milikku berjalan di mesin virtual Java, atau kinerja komputer kita (milikku adalah Intel Q6600 @ 2.4MHz yang menjalankan WinXP), Saya tidak tahu Tapi ini jauh lebih cepat daripada hasil untuk implementasi lain yang dikutip di akhir pertanyaan awal. Jadi, apakah algoritma ini lebih baik daripada kamus trie atau tidak, saya tidak tahu pada saat ini.

• Metode tabel yang digunakan dalam checkWordTriplets()menghasilkan perkiraan yang sangat baik untuk jawaban yang sebenarnya. Hanya 1 dari 3-5 kata yang dilewati akan gagal dalam checkWords()ujian (Lihat jumlah kandidat vs. jumlah kata aktual di atas)

• Sesuatu yang tidak dapat Anda lihat di atas: checkWordTriplets()Fungsi ini membutuhkan waktu sekitar 3,65 ms dan karenanya sepenuhnya dominan dalam proses pencarian. The checkWords()Fungsi memakan cukup banyak 0,05-0,20 ms tersisa.

• Waktu pelaksanaan checkWordTriplets()fungsi tergantung secara linear pada ukuran kamus dan hampir tidak tergantung pada ukuran papan!

• Waktu pelaksanaan checkWords()tergantung pada ukuran papan dan jumlah kata yang tidak dikesampingkan oleh checkWordTriplets().

• The checkWords()implementasi di atas adalah paling bodoh versi pertama saya datang dengan. Ini pada dasarnya tidak dioptimalkan sama sekali. Tetapi dibandingkan dengan checkWordTriplets()itu tidak relevan untuk kinerja total aplikasi, jadi saya tidak khawatir tentang hal itu. Tetapi , jika ukuran papan semakin besar, fungsi ini akan semakin lambat dan lambat dan pada akhirnya akan mulai berarti. Maka, itu perlu dioptimalkan juga.

• Satu hal yang menyenangkan tentang kode ini adalah fleksibilitasnya:

  • Anda dapat dengan mudah mengubah ukuran papan: Perbarui baris 10 dan array String diteruskan ke initializeBoard().
  • Ini dapat mendukung huruf yang lebih besar / berbeda dan dapat menangani hal-hal seperti memperlakukan 'Qu' sebagai satu huruf tanpa ada overhead kinerja. Untuk melakukan ini, orang perlu memperbarui baris 9 dan beberapa tempat di mana karakter dikonversi ke angka (saat ini hanya dengan mengurangi 65 dari nilai ASCII)

Ok, tapi saya pikir sekarang posting ini sudah cukup lama. Saya pasti bisa menjawab pertanyaan yang mungkin Anda miliki, tapi mari kita pindah ke komentar.

Anehnya, tidak ada yang mencoba versi PHP ini.

Ini adalah versi PHP yang berfungsi dari solusi Python John Fouhy.

Meskipun saya mengambil beberapa petunjuk dari jawaban orang lain, ini sebagian besar disalin dari 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);

Berikut ini tautan langsung jika Anda ingin mencobanya. Meskipun dibutuhkan ~ 2s di mesin lokal saya, dibutuhkan ~ 5s di server web saya. Dalam kedua kasus, itu tidak terlalu cepat. Meski begitu, itu cukup mengerikan sehingga saya bisa membayangkan waktu dapat dikurangi secara signifikan. Setiap petunjuk tentang bagaimana mencapai itu akan dihargai. Kurangnya tupel PHP membuat koordinat aneh untuk bekerja dengan dan ketidakmampuan saya untuk memahami apa yang sedang terjadi tidak membantu sama sekali.

EDIT : Beberapa perbaikan membuatnya butuh kurang dari 1s secara lokal.

Tidak tertarik dengan VB? :) Saya tidak bisa menolak. Saya telah memecahkan ini secara berbeda dari banyak solusi yang disajikan di sini.

Waktu saya adalah:

• Memuat kamus dan awalan kata ke dalam hashtable: .5 hingga 1 detik.
• Menemukan kata-kata: rata-rata di bawah 10 milidetik.

EDIT: Kamus memuat kali di server host web berjalan sekitar 1 hingga 1,5 detik lebih lama dari komputer di rumah saya.

Saya tidak tahu seberapa buruk waktu akan memburuk dengan beban di server.

Saya menulis solusi saya sebagai halaman web di .Net. myvrad.com/boggle

Saya menggunakan kamus yang dirujuk dalam pertanyaan asli.

Surat tidak digunakan kembali dalam satu kata. Hanya 3 kata atau lebih yang ditemukan.

Saya menggunakan hashtabel dari semua awalan dan kata-kata unik alih-alih sebuah trie. Saya tidak tahu tentang trie jadi saya belajar sesuatu di sana. Gagasan untuk membuat daftar awalan kata-kata di samping kata-kata lengkap adalah apa yang akhirnya membuat saya turun ke angka yang terhormat.

Baca komentar kode untuk detail tambahan.

Berikut kodenya:

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

Begitu saya melihat pernyataan masalah, saya berpikir "Trie". Tetapi melihat beberapa poster memanfaatkan pendekatan itu, saya mencari pendekatan lain hanya untuk menjadi berbeda. Sayangnya, pendekatan Trie berkinerja lebih baik. Saya menjalankan solusi Kent's Perl di mesin saya dan butuh 0,31 detik untuk berjalan, setelah mengadaptasinya untuk menggunakan file kamus saya. Implementasi perl saya sendiri membutuhkan 0,54 detik untuk berjalan.

Ini pendekatan saya:

1. Buat hash transisi untuk memodelkan transisi hukum.

2. Ulangi semua 16 ^ 3 kemungkinan kombinasi tiga huruf.

   • Dalam loop, kecualikan transisi ilegal dan ulangi kunjungan ke kotak yang sama. Bentuk semua urutan 3 huruf hukum dan simpan dalam hash.

3. Kemudian putar semua kata dalam kamus.

   • Kecualikan kata-kata yang terlalu panjang atau pendek
   • Geser jendela 3 huruf di setiap kata dan lihat apakah ada di antara kombo 3 huruf dari langkah 2. Kecualikan kata yang gagal. Ini menghilangkan sebagian besar ketidakcocokan.
   • Jika masih belum dihilangkan, gunakan algoritma rekursif untuk melihat apakah kata tersebut dapat dibentuk dengan membuat jalur melalui puzzle. (Bagian ini lambat, tetapi jarang disebut.)

4. Cetak kata-kata yang saya temukan.

   Saya mencoba urutan 3 huruf dan 4 huruf, tetapi urutan 4 huruf memperlambat program.

Dalam kode saya, saya menggunakan / usr / share / dict / kata-kata untuk kamus saya. Muncul standar pada MAC OS X dan banyak sistem Unix. Anda dapat menggunakan file lain jika diinginkan. Untuk memecahkan puzzle yang berbeda, cukup ubah variabel @puzzle. Ini akan mudah untuk beradaptasi dengan matriks yang lebih besar. Anda hanya perlu mengubah hash% transisi dan% hash transisi legal.

Kekuatan dari solusi ini adalah bahwa kodenya pendek, dan struktur datanya sederhana.

Ini kode Perl (yang saya tahu terlalu banyak variabel global):

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

Saya tahu saya sangat terlambat tapi saya membuat ini beberapa saat yang lalu di PHP - hanya untuk bersenang-senang ...

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Ditemukan 75 kata (133 poin) dalam 0,90108 detik

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

Memberikan beberapa indikasi tentang apa yang sebenarnya dilakukan program - setiap huruf adalah di mana ia mulai melihat melalui pola sementara masing-masing '.' menunjukkan jalan yang telah dicoba untuk diambil. Lebih '.' ada lebih jauh yang telah dicari.

Beri tahu saya jika Anda menginginkan kode ... itu adalah campuran mengerikan antara PHP dan HTML yang tidak pernah dimaksudkan untuk melihat hari jadi saya tidak berani mempostingnya di sini: P

Saya menghabiskan 3 bulan mengerjakan solusi untuk masalah papan Boggle 10x5 titik padat terbaik.

Masalahnya sekarang dipecahkan dan ditata dengan pengungkapan penuh pada 5 halaman web. Silakan hubungi saya dengan pertanyaan.

Algoritma analisis papan menggunakan tumpukan eksplisit untuk pseudo-rekursif melintasi kotak papan melalui Grafik Kata Acyclic Directed dengan informasi anak langsung, dan mekanisme pelacakan cap waktu. Ini mungkin merupakan struktur data leksikon paling canggih di dunia.

Skema ini mengevaluasi sekitar 10.000 papan yang sangat baik per detik pada quad core. (9500+ poin)

Halaman Web Induk:

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

Halaman Web Komponen:

Papan Skor Optimal - http://www.pathcom.com/~vadco/binary.html

Struktur Lexicon Lanjutan - http://www.pathcom.com/~vadco/adtdawg.html

Algoritma Analisis Dewan - http://www.pathcom.com/~vadco/guns.html

Pemrosesan Batch Paralel - http://www.pathcom.com/~vadco/parallel.html

- Badan kerja komprehensif ini hanya akan menarik minat seseorang yang menuntut yang terbaik.

Apakah algoritma pencarian Anda terus mengurangi daftar kata saat pencarian Anda berlanjut?

Misalnya, dalam pencarian di atas hanya ada 13 huruf yang dapat diawali dengan kata-kata Anda (secara efektif berkurang menjadi setengah dari jumlah huruf awal).

Saat Anda menambahkan permutasi huruf lagi akan semakin mengurangi set kata yang tersedia mengurangi pencarian yang diperlukan.

Saya akan mulai dari sana.

Saya harus lebih memikirkan solusi lengkap, tetapi sebagai optimisasi praktis, saya bertanya-tanya apakah mungkin ada pra-komputasi tabel frekuensi digram dan trigram (kombinasi 2 dan 3 huruf) berdasarkan semua kata-kata dari kamus Anda, dan gunakan ini untuk memprioritaskan pencarian Anda. Saya akan menggunakan huruf awal kata-kata. Jadi jika kamus Anda berisi kata-kata "India", "Air", "Ekstrim", dan "Luar Biasa", maka tabel pra-perhitungan Anda mungkin:

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

Kemudian cari digram ini dalam urutan kesamaan (EX pertama, lalu WA / IN)

Pertama, baca bagaimana salah satu perancang bahasa C # memecahkan masalah terkait: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .

Seperti dia, Anda bisa mulai dengan kamus dan kata-kata yang dikanonalkan dengan membuat kamus dari berbagai huruf yang diurutkan secara alfabetis ke daftar kata yang dapat dieja dari huruf-huruf itu.

Selanjutnya, mulailah membuat kata-kata yang mungkin dari papan tulis dan cari. Saya menduga itu akan membuat Anda cukup jauh, tetapi tentu saja ada lebih banyak trik yang dapat mempercepat.

Saya sarankan membuat pohon surat berdasarkan kata-kata. Pohon akan terdiri dari struct surat, seperti ini:

letter: char
isWord: boolean

Kemudian Anda membangun pohon, dengan setiap kedalaman menambahkan huruf baru. Dengan kata lain, pada tingkat pertama akan ada alfabet; lalu dari masing-masing pohon itu, akan ada 26 entri lagi, dan seterusnya, sampai Anda mengucapkan semua kata. Gantung ke pohon yang diurai ini, dan itu akan membuat semua jawaban yang mungkin lebih cepat untuk mencari.

Dengan pohon yang diuraikan ini, Anda dapat dengan cepat menemukan solusi. Inilah pseudo-code:

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

Ini bisa dipercepat dengan sedikit pemrograman dinamis. Misalnya, dalam sampel Anda, kedua 'A' adalah di sebelah 'E' dan 'W', yang (dari titik mereka memukulnya) akan identik. Saya tidak punya cukup waktu untuk benar-benar menguraikan kode untuk ini, tetapi saya pikir Anda dapat mengumpulkan idenya.

Juga, saya yakin Anda akan menemukan solusi lain jika Anda Google untuk "pemecah Boggle".

Hanya untuk bersenang-senang, saya menerapkannya di bash. Ini tidak super cepat, tetapi masuk akal.

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

Lucu sekali. Saya hampir memposting pertanyaan yang sama beberapa hari yang lalu karena permainan yang sama! Namun saya tidak melakukannya karena hanya mencari google untuk boggle solver python dan mendapatkan semua jawaban yang saya inginkan.

Saya menyadari waktu pertanyaan ini telah datang dan pergi, tetapi karena saya sendiri sedang mengerjakan solver, dan menemukan ini sambil mencari-cari di sekitar, saya pikir saya harus memposting referensi ke saya karena tampaknya sedikit berbeda dari beberapa yang lain.

Saya memilih untuk pergi dengan array datar untuk papan permainan, dan untuk melakukan perburuan rekursif dari setiap huruf di papan, melintasi dari tetangga yang valid ke tetangga yang valid, memperpanjang perburuan jika daftar huruf saat ini jika awalan yang valid dalam indeks. Sementara melintasi gagasan kata saat ini adalah daftar indeks ke papan tulis, bukan huruf yang membentuk kata. Saat memeriksa indeks, indeks diterjemahkan ke huruf dan pemeriksaan selesai.

Indeks adalah kamus brute force yang sedikit mirip trie, tetapi memungkinkan untuk query Pythonic dari indeks. Jika kata 'cat' dan 'cater' ada dalam daftar, Anda akan mendapatkan ini di kamus:

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

Jadi jika current_word adalah 'ca' Anda tahu bahwa itu adalah awalan yang valid karena 'ca' in dmengembalikan True (jadi teruskan board traversal). Dan jika current_word adalah 'cat' maka Anda tahu bahwa itu adalah kata yang valid karena merupakan awalan dan valid'cat' in d['cat'] mengembalikan True juga.

Jika merasa seperti ini diperbolehkan untuk beberapa kode yang dapat dibaca yang sepertinya tidak terlalu lambat. Seperti orang lain, pengeluaran dalam sistem ini adalah membaca / membangun indeks. Memecahkan papan cukup berisik.

Kode ini ada di http://gist.github.com/268079 . Itu sengaja vertikal dan naif dengan banyak pengecekan validitas eksplisit karena saya ingin memahami masalahnya tanpa merapikannya dengan sekelompok sihir atau ketidakjelasan.

Saya menulis solver saya di C ++. Saya menerapkan struktur pohon kustom. Saya tidak yakin itu bisa dianggap sebagai trie tetapi mirip. Setiap node memiliki 26 cabang, 1 untuk setiap huruf alfabet. Saya melintasi cabang-cabang papan boggle secara paralel dengan cabang-cabang kamus saya. Jika cabang tidak ada di kamus, saya berhenti mencari di papan Boggle. Saya mengubah semua huruf di papan tulis menjadi int. Jadi 'A' = 0. Karena ini hanya array, pencarian selalu O (1). Setiap node menyimpan jika ia menyelesaikan satu kata dan berapa banyak kata yang ada pada anak-anaknya. Pohon itu dipangkas karena kata-kata ditemukan berkurang berulang kali mencari kata yang sama. Saya percaya pemangkasan juga O (1).

CPU: Pentium SU2700 1.3GHz
RAM: 3gb

Memuat kamus 178.590 kata dalam <1 detik.
Memecahkan Boggle 100x100 (boggle.txt) dalam 4 detik. ~ 44.000 kata ditemukan.
Memecahkan Boggle 4x4 terlalu cepat untuk memberikan tolok ukur yang berarti. :)

Fast Boggle Solver GitHub Repo

Diberi papan Boggle dengan kolom N rows dan M, mari kita asumsikan yang berikut:

• N * M secara substansial lebih besar dari jumlah kata yang mungkin
• N * M jauh lebih besar dari kata yang paling panjang

Berdasarkan asumsi ini, kompleksitas dari solusi ini adalah O (N * M).

Saya pikir membandingkan waktu berjalan untuk papan contoh yang satu ini dalam banyak hal tidak tepat tetapi, demi kelengkapan, solusi ini selesai dalam <0,2 detik pada MacBook Pro modern saya.

Solusi ini akan menemukan semua jalur yang mungkin untuk setiap kata dalam korpus.

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

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

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

# Functions

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

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

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

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

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

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

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

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

# Script

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

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

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

  opts.on_tail('-h', '--help', 'Shows usage') do
    STDOUT.puts opts
    exit
  end
end
option_parser.parse!

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

unless File.file? options[:corpus_path]
  STDERR.puts "No corpus exists - #{options[:corpus_path]}"
  exit false
end

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

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

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

Solusi ini juga memberikan arahan untuk mencari di papan yang diberikan

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

Keluaran:

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

Kode:

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)

Saya telah mengimplementasikan solusi di OCaml . Ini pra-kompilasi kamus sebagai trie, dan menggunakan frekuensi urutan dua huruf untuk menghilangkan tepi yang tidak pernah bisa muncul dalam sebuah kata untuk lebih mempercepat pemrosesan.

Ini memecahkan papan contoh Anda dalam 0,35 ms (dengan tambahan waktu 6ms start-up yang sebagian besar terkait dengan memuat trie ke dalam memori).

Solusi yang ditemukan:

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

Solusi JavaScript Node.JS. Hitung semua 100 kata unik dalam waktu kurang dari satu detik yang termasuk membaca file kamus (MBA 2012).

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

Kode:

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

Jadi saya ingin menambahkan cara lain penyelesaian PHP, karena semua orang menyukai PHP. Ada sedikit refactoring yang ingin saya lakukan, seperti menggunakan kecocokan regexpression terhadap file kamus, tapi saat ini saya hanya memuat seluruh file kamus ke dalam wordList.

Saya melakukan ini menggunakan ide daftar tertaut. Setiap Node memiliki nilai karakter, nilai lokasi, dan penunjuk berikutnya.

Nilai lokasi adalah bagaimana saya mengetahui jika dua node terhubung.

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

Jadi menggunakan kisi itu, saya tahu dua node terhubung jika lokasi node pertama sama dengan lokasi node kedua +/- 1 untuk baris yang sama, +/- 9, 10, 11 untuk baris di atas dan di bawah.

Saya menggunakan rekursi untuk pencarian utama. Dibutuhkan satu kata dari wordList, menemukan semua titik awal yang mungkin, dan kemudian secara rekursif menemukan koneksi berikutnya yang mungkin, mengingat bahwa itu tidak dapat pergi ke lokasi yang sudah digunakan (itulah sebabnya saya menambahkan $ notInLoc).

Ngomong-ngomong, saya tahu ini memerlukan beberapa refactoring, dan akan senang mendengar pemikiran tentang cara membuatnya lebih bersih, tetapi itu menghasilkan hasil yang benar berdasarkan pada file kamus yang saya gunakan. Bergantung pada jumlah vokal dan kombinasi di papan tulis, dibutuhkan sekitar 3 hingga 6 detik. Saya tahu bahwa setelah saya preg_match hasil kamus, itu akan berkurang secara signifikan.

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

    ?>

Saya tahu saya benar-benar terlambat di pesta tetapi saya telah menerapkan, sebagai latihan pengkodean, pemecah boggle dalam beberapa bahasa pemrograman (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) dan Saya pikir seseorang mungkin tertarik pada hal itu, jadi saya meninggalkan tautan di sini: https://github.com/AmokHuginnsson/boggle-solvers

Berikut adalah solusinya Menggunakan kata-kata yang ditentukan sebelumnya di NLTK toolkit NLTK memiliki paket nltk.corpus di mana kami memiliki paket yang disebut kata-kata dan berisi lebih dari 2Lakh kata-kata bahasa Inggris yang dapat Anda gunakan dengan mudah ke dalam program Anda.

Setelah membuat matriks Anda, ubah menjadi array karakter dan lakukan kode ini

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)

Keluaran:

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

Saya harap kamu mengerti.

Berikut ini adalah implementasi java saya: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

Membangun trie membutuhkan waktu 0 jam, 0 menit, 1 detik, 532 milidetik
Pencarian kata memakan waktu 0 jam, 0 menit, 0 detik, 92 milidetik

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 

Catatan: Saya menggunakan kamus dan matriks karakter di awal utas ini. Kode dijalankan di MacBookPro saya, di bawah ini adalah beberapa informasi tentang mesin.

Nama Model: MacBook Pro
Identifier Model: MacBookPro8, 1
Nama Prosesor: Intel Core i5
Kecepatan Prosesor: 2,3 GHz
Jumlah Prosesor: 1
Jumlah
Inti : 2 L2 Cache (per inti): 256 KB
L3 Cache: 3 MB
Memori: 4 GB
Versi Boot ROM: MBP81.0047.B0E
Versi SMC (sistem): 1.68f96

Saya memecahkan ini juga, dengan Java. Implementasi saya panjangnya 269 baris dan cukup mudah digunakan. Pertama, Anda perlu membuat instance baru dari kelas Boggler dan kemudian memanggil fungsi penyelesaian dengan grid sebagai parameter. Diperlukan sekitar 100 ms untuk memuat kamus 50.000 kata di komputer saya dan ia menemukan kata-kata itu dalam sekitar 10-20 ms. Kata-kata yang ditemukan disimpan dalam 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;
    }
}

Saya memecahkan masalah ini di c. Dibutuhkan sekitar 48 ms untuk berjalan di mesin saya (dengan sekitar 98% dari waktu yang dihabiskan memuat kamus dari disk dan membuat trie). Kamusnya adalah / usr / share / dict / american-english yang memiliki 62886 kata.

Kode sumber

Saya menyelesaikan ini dengan sempurna dan sangat cepat. Saya memasukkannya ke dalam aplikasi android. Lihat video di tautan play store untuk melihatnya beraksi.

Word Cheats adalah sebuah aplikasi yang "memecahkan" setiap permainan kata gaya matriks. Aplikasi ini dibuat untuk membantu saya melakukan cheat di word scrambler. Ini dapat digunakan untuk pencarian kata, ruzzle, kata-kata, pencari kata, crack kata, merusakkan, dan banyak lagi!

Itu dapat dilihat di sini https://play.google.com/store/apps/details?id=com.harris.wordcracker

Lihat aplikasi dalam aksi di video https://www.youtube.com/watch?v=DL2974WmNAI