如何从字母矩阵中找到可能的单词列表[Boggle Solver]

像他一样，您可以从字典开始，并通过从字母排序的字母数组到可以根据这些字母拼写的单词列表创建字典来规范化单词。

接下来，开始从黑板上创建可能的单词并查找它们。我怀疑这将让你走得很远，但肯定有更多的技巧可以加快速度。

你的搜索算法是否会随着搜索的继续而不断减少单词列表?

例如，在上面的搜索中，你的单词只能以13个字母开头(有效地减少了一半的开头字母)。

当你添加更多的字母排列时，它会进一步减少可用的单词集，减少必要的搜索。

我会从这里开始。

你将得到的最快的解决方案可能涉及到将字典存储在单词查找树中。然后，创建一个三元组队列(x， y， 年代)，其中队列中的每个元素对应于一个可以在网格中拼写的单词的前缀年代，结束于location (x， y)。使用N x N元素初始化队列(其中N是网格的大小)，网格中的每个正方形对应一个元素。然后，算法进行如下:

While the queue is not empty:
Dequeue a triple (x, y, s)
For each square (x', y') with letter c adjacent to (x, y):
If s+c is a word, output s+c
If s+c is a prefix of a word, insert (x', y', s+c) into the queue

如果将字典存储在trie中，测试年代+c是否是单词或单词的前缀可以在常量时间内完成(前提是在每个队列数据中保留一些额外的元数据，例如指向trie中当前节点的指针)，因此此算法的运行时间为O(可拼写的单词数量)。

(编辑)这是我刚刚编写的Python实现:

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

使用示例:

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

输出:

“悲哀”,“鲍勃”、“车辆”,‘小家伙’,‘但是’,‘ast’,‘ase’,“亚撒”、“锥子”,“远”,“敬畏”,‘那边’,‘aes’,‘swa’,‘swa’,“缝”,“海”,“海”,“看到”、“晚礼服”,“浴缸”,“图”,“两个”,“两个”、“测试”,“utu”、“农夫”,“名声”,“ixil”、“伊玛目”,“amli”,阿米尔,“读经台”,“腋”、“轴”,“咪咪”,“米玛”、“哑剧”、“米洛”、“英里”,“低泣”,“mese”、“台面”,“罗罗语”,“大灰狼”,“利马的”,“石灰”、“肢体”,“lile”、“oime”,“人造奶油”、“杂烩”,双簧管,“欧宝”、“以”、“埃米尔”,“东”、“缓解”,“子宫”,“瓦瓦”,“瓦瓦”,“weam”、“西”,“wese”,“滚”,“瓦斯”、“瓦瓦”,“瓦瓦”,“煮”,“大刀”、“伯乐”,“波波”、“blob”,“bleo”,“腹股沟淋巴结炎”、“亚欧会议”,“存根”、“辅”,“游”,“半”,“义子”、“缝”,“seax”、“莎莎”,“sawt”、“图图”,‘啧’,‘twae’,‘twas’,‘twae’,‘ilima’,“漫步”,“中轴”、“敬畏”,“玛米”,“mambo”、“格言”,‘mease’,‘mesem’,‘limax’,‘酸橙’,‘地狱’,‘limbu’,‘obole’,‘emesa’,‘embox’,‘哦’,‘偶像’,‘famble’,‘mimble’,‘maxima’,‘embolo’,‘embole’,‘wamble’,‘semese’,‘看来好像’,‘sawbwa’,‘sawbwa’)

注意:这个程序不输出一个字母的单词，也不按单词长度过滤。这很容易添加，但与问题无关。如果一些单词可以用多种方式拼写，它还会多次输出这些单词。如果一个给定的单词可以有很多种不同的拼写方式(最坏的情况是:网格中的每个字母都是相同的(例如;'A')，字典里有'aaaaaaaaaa'之类的词)，那么运行时间就会变成可怕的指数级增长。在算法完成后，过滤掉重复项和排序是微不足道的。

我不得不对一个完整的解决方案进行更多的思考，但作为一种方便的优化，我想知道是否值得根据字典中的所有单词预先计算一个图表和三字母组合(2字母和3字母组合)的频率表，并使用它来确定搜索的优先级。我会选择单词的首字母。因此，如果你的字典包含“印度”、“水”、“极端”和“非凡”这些词，那么你预先计算的表可能是:

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

然后按照共性的顺序(首先是EX，然后是WA/ in)搜索这些图表

我建议根据单词做一个字母树。这棵树将由字母结构组成，像这样:

letter: char
isWord: boolean

然后构建树，每个深度添加一个新字母。换句话说，第一层是字母表;然后从这些树中，会有另外26个条目，以此类推，直到你把所有的单词都拼出来。坚持这个解析树，它将使所有可能的答案更快地查找。

使用这个解析过的树，您可以非常快速地找到解决方案。下面是伪代码:

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.

这可以通过一些动态编程来加快。例如，在你的样本中，两个“A”都在一个“E”和一个“W”旁边，这(从它们击中它们的点来看)是相同的。我没有足够的时间来详细说明这个代码，但我想你们可以理解。

此外，我相信你会找到其他解决方案，如果你谷歌“Boggle solver”。

搞笑。几天前我差点因为这款该死的游戏而发布了同样的问题!然而，我没有，因为我只是搜索谷歌Boggle solver python，得到了我想要的所有答案。

你可以把这个问题分成两部分:

1. 某种搜索算法可以在网格中列举出可能的字符串。
2. 一种测试字符串是否是有效单词的方法。

理想情况下，(2)还应该包括一种测试字符串是否是有效单词前缀的方法——这将允许您精简搜索并节省大量时间。

亚当·罗森菲尔德(Adam Rosenfield)的Trie是(2)的一个解决方案。它很优雅，可能是算法专家的首选，但有了现代语言和现代计算机，我们可能会更懒一点。此外，正如Kent所建议的，我们可以通过丢弃网格中没有字母的单词来减少字典的大小。这是一些蟒蛇:

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

哇;常数时间前缀测试。加载你链接的字典需要几秒钟，但只需要几秒钟:-)(注意words <= prefixes)

现在，对于第(1)部分，我倾向于用图表来思考。所以我将创建一个像这样的字典:

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

例如，graph[(x, y)]是你可以从位置(x, y)到达的坐标集。我还将添加一个虚拟节点None，它将连接到所有东西。

构建它有点笨拙，因为有8个可能的位置，你必须做边界检查。下面是一些相应笨拙的python代码:

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

这段代码还建立了一个字典，将(x,y)映射到相应的字符。这让我把一个位置列表转换成一个单词:

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

最后，我们进行深度优先搜索。基本程序是:

1. 搜索到达一个特定的节点。
2. 检查到目前为止的路径是否可能是单词的一部分。如果不是，就不要进一步探索这个分支。
3. 检查到目前为止的路径是否是一个单词。如果是，则添加到结果列表中。
4. 探索迄今为止所有孩子未走的路。

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)

运行代码如下:

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)

并检查res来查看答案。下面是为你的例子找到的单词列表，按大小排序:

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

代码需要(字面上的)几秒钟来加载字典，但其余的在我的机器上是立即完成的。

对于字典加速，有一个通用的转换/过程可以大大减少提前的字典比较。

鉴于上面的网格只包含16个字符，其中一些字符是重复的，您可以通过简单地过滤掉具有不可获取字符的条目来大大减少字典中的总键数。

我认为这是明显的优化，但看到没有人这么做，我就提出来了。

在输入过程中，它将我的字典从20万个键减少到只有2000个键。这至少减少了内存开销，并且这肯定会映射到某个地方的速度增加，因为内存不是无限快的。

Perl实现

我的实现有点头重脚轻，因为我重视能够知道每个提取的字符串的确切路径，而不仅仅是其中的有效性。

我也有一些适应在那里，理论上允许一个网格中有洞的功能，网格有不同大小的线(假设你得到了正确的输入，它以某种方式对齐)。

早期过滤器是迄今为止我的应用程序中最重要的的瓶颈，正如之前怀疑的那样，注释掉了该行从1.5s膨胀到7.5s。

在执行时，它似乎认为所有的个位数都在他们自己的有效单词上，但我很确定这是由于字典文件的工作方式。

它有点臃肿，但至少我重用了cpan中的树:单词查找树

其中有些部分是受到现有实现的启发，有些是我已经想到的。

建设性的批评和改进的方法欢迎(/我注意到他从来没有在CPAN搜索一个拼字游戏解决器，但这是更有趣的工作)

新标准更新

#!/usr/bin/perl


use strict;
use warnings;


{


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


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


package Prefix;
use Moose;


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


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


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


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


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


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


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


# Returns  the rightmost node on this path


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


# pretty-format $o->path


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


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


__PACKAGE__->meta->make_immutable;
}


{


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


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


package MatrixNode;
use Moose;


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


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


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


# Convenience method to derive a path starting at this node


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


}


{


package Matrix;
use Moose;


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


__PACKAGE__->meta->make_immutable;
}


use Tree::Trie;


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


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


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


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


# Inject all grid nodes into the processing queue.


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


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


# put the dictionary into "exact match" mode.


$d->deepsearch('exact');


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


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


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


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


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


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


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


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


# Here is where the real work starts.


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


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


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

Arch/执行信息进行比较:

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

关于正则表达式优化的更多嘟囔

我使用的正则表达式优化对于多解字典是无用的，而对于多解字典，您将需要一个完整的字典，而不是一个预先修整过的字典。

然而，也就是说，对于一次性解决，它真的很快。(Perl正则表达式是在C!:))

以下是一些不同的代码添加:

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 unfiltered   filtered
unfiltered   8.16         --       -94%
filtered    0.464      1658%         --

_{Ps: 8.16 * 200 = 27分钟。}

我的答案和这里的其他答案一样，但我把它贴出来是因为它看起来比其他Python解决方案快一些，因为设置字典更快。(我对比了John Fouhy的解决方案。)设置后，解决的时间在噪声中下降。

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)

示例用法:

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

编辑:过滤掉长度小于3个字母的单词。

我很好奇为什么Kent Fredric的Perl解决方案更快;它使用正则表达式匹配，而不是一组字符。在Python中做同样的事情，速度大约会翻倍。

对VB不感兴趣?:)我忍不住了。我解决这个问题的方法不同于这里提出的许多解决方案。

我的时间是:

• 将字典和单词前缀加载到哈希表:.5到1秒。
• 找单词:平均不到10毫秒。

编辑:web主机服务器上的字典加载时间比我的家用电脑长1到1.5秒。

我不知道随着服务器负载的增加，时间会恶化到什么程度。

我把我的解决方案写成了。net的网页。myvrad.com/boggle

我用的是原题中提到的字典。

字母在单词中不能重复使用。只找到3个字符或以上的单词。

我使用所有唯一的单词前缀和单词的哈希表，而不是一个trie。我不知道什么是trie，所以我学到了一些东西。除了完整的单词之外，创建单词前缀列表的想法最终使我的时间减少到一个可观的数字。

阅读代码注释以获得更多详细信息。

代码如下:

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

令人惊讶的是，没有人尝试使用PHP版本。

这是John Fouhy的Python解决方案的PHP版本。

虽然我从其他人的答案中得到了一些建议，但这主要是抄袭约翰的。

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

这里是一个生活链接，如果你想尝试一下。虽然在我的本地机器上需要大约2秒，但在我的web服务器上需要大约5秒。无论哪种情况，它都不是很快。尽管如此，它还是很可怕，所以我可以想象时间可以大大缩短。任何关于如何实现这一目标的建议都将不胜感激。PHP缺少元组，这使得坐标处理起来很奇怪，而且我无法理解到底发生了什么，这对我一点帮助都没有。

编辑:一些修复使它在本地花费的时间小于1。

当我看到问题陈述时，我想到了“Trie”。但看到其他一些海报使用了这种方法，我寻找另一种不同的方法。可惜的是，Trie方法表现更好。我在我的机器上运行Kent的Perl解决方案，在调整它以使用我的字典文件后，它花了0.31秒运行。我自己的perl实现需要0.54秒才能运行。

这就是我的方法:

1. 创建一个转换散列来模拟合法的转换。

2. 遍历所有16^3个可能的三个字母组合。

   • 在循环中，排除非法转换并重复访问 相同的广场。形成所有合法的3个字母序列，并将它们存储在哈希中 李< / ul > < / >
   • 然后循环遍历字典中的所有单词。
     • 排除过长或过短的单词
     • 滑动一个3个字母的窗口，穿过每个单词，看看它是否在步骤2中的3个字母组合中。排除失败的单词。这消除了大多数不匹配。
     • 如果仍然没有消除，使用递归算法，看看是否可以通过在谜题中设置路径来形成单词。(这部分很慢，但很少调用。)
     李< / ul > < / >

     • 打印我找到的单词。

       我尝试了3个字母和4个字母的序列，但是4个字母的序列减慢了程序

在我的代码中，我使用/usr/share/dict/words作为我的字典。它是MAC OS X和许多Unix系统的标准配置。如果你愿意，你可以使用另一个文件。要破解不同的谜题，只需更改变量@puzzle。这将很容易适应更大的矩阵。你只需要改变%transitions哈希值和%legalTransitions哈希值。

这种解决方案的优点是代码短，数据结构简单。

下面是Perl代码(我知道它使用了太多的全局变量):

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

我在Java上的尝试。读取文件和构建trie大约需要2秒，解决谜题大约需要50毫秒。我用了问题中链接的字典(里面有几个我不知道在英语中存在的单词，比如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

源代码由6个类组成。我将把它们贴在下面(如果这不是StackOverflow的正确做法，请告诉我)。

gineer.bogglesolver.Main

package gineer.bogglesolver;


import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;


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


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


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


}
}

gineer.bogglesolver.Solver

package gineer.bogglesolver;


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


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


private boolean[] used;
private StringBuilder stringSoFar;


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


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


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


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


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


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


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


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


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


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


}

gineer.bogglesolver.trie.Node

package gineer.bogglesolver.trie;


import gineer.bogglesolver.util.Constants;


class Node
{
Node[] children;
boolean isKey;


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


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


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


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


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


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


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


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


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


public boolean isKey()
{
return isKey;
}


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

gineer.bogglesolver.trie.Trie

package gineer.bogglesolver.trie;


public class Trie
{
Node root;


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


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


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


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


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


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


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




}

gineer.bogglesolver.util.Constants

package gineer.bogglesolver.util;


public class Constants
{


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

gineer.bogglesolver.util.Util

package gineer.bogglesolver.util;


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


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


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


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


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


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


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


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


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


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


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


return squares;
}


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


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

我知道我太迟了，但我在PHP中做了一个——只是为了好玩……

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu 在0.90108秒

给出了一些程序实际在做什么的指示-每个字母是它开始查看模式的地方，而每个'。这显示了中国试图走的一条道路。越多越好。“它搜索得越远。

如果你想要密码，请告诉我…这是一个可怕的PHP和HTML的混合体，从来没有想过要看到阳光，所以我不敢在这里张贴:P

我花了3个月的时间致力于解决10个最佳点密集的5x5 Boggle板问题。

这个问题现在已经解决了，并在5个网页上进行了全面披露。有问题请联系我。

该棋盘分析算法使用显式堆栈，通过具有直接子信息的有向无环词图伪递归遍历棋盘方格，并使用时间戳跟踪机制。这很可能是世界上最先进的词汇数据结构。

该方案在四核上每秒评估大约10,000块非常好的电路板。(9500 +分)

父网页:

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

组件网页:

最佳计分板- http://www.pathcom.com/~vadco/binary.html

高级词汇结构- http://www.pathcom.com/~vadco/adtdawg.html

单板分析算法- http://www.pathcom.com/~vadco/guns.html

并行批处理- http://www.pathcom.com/~vadco/parallel.html

我意识到这个问题的时间来了又去了，但由于我自己正在研究一个求解器，并在谷歌搜索时偶然发现了这个，我想我应该发布一个参考，因为它似乎与其他一些问题有点不同。

我选择在游戏棋盘上使用平面数组，并从棋盘上的每个字母进行递归搜索，从有效邻居遍历到有效邻居，如果索引中的有效前缀是当前字母列表，则扩展搜索。而遍历当前单词的概念是进入板的索引列表，而不是组成单词的字母。在检查索引时，将索引转换为字母并完成检查。

索引是一个蛮力字典，有点像trie，但允许对索引进行python查询。如果单词'cat'和'cater'在列表中，你会在字典中看到:

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

因此，如果current_word是'ca'，您知道它是一个有效的前缀，因为'ca' in d返回True(因此继续遍历板)。如果current_word是'cat'，那么你知道它是一个有效的单词，因为它是一个有效的前缀，并且'cat' in d['cat']也返回True。

如果感觉这允许一些可读的代码，似乎不是太慢。像其他人一样，这个系统的费用是读取/构建索引。解这个板子相当麻烦。

代码位于http://gist.github.com/268079。它是故意垂直和幼稚的，有很多明确的有效性检查，因为我想理解问题，而不是用一堆魔法或晦涩难懂的东西把它弄得乱七八糟。

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

我有在OCaml中实现了一个解决方案。它将字典预编译为trie，并使用双字母序列频率来消除单词中永远不会出现的边，以进一步加快处理速度。

它在0.35ms内解决了示例板的问题(额外的6ms启动时间主要与将trie加载到内存有关)。

找到的解决方案:

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

这是我的java实现:https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

Trie构建耗时0小时0分1秒532毫秒
单词搜索耗时0小时0分0秒92毫秒

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

<强>注意: 我在这个线程的开头使用了字典和字符矩阵。代码在我的MacBookPro上运行，下面是关于这台机器的一些信息。< / p > 型号名称:MacBook Pro
型号标识符:MacBookPro8,1
处理器名称:Intel Core i5
处理器速度:2.3 GHz
Number Of Processors: 1
.输出说明 Total Number Of Cores: 2
L2 Cache(每核):256kb
L3 Cache: 3mb
内存:4gb
引导ROM版本:MBP81.0047.B0E
SMC版本(系统):1.68f96

我认为你可能会花大部分时间去匹配那些不可能由你的字母网格构成的单词。所以，我要做的第一件事就是加快这一步，这应该能让你大致达到目的。

为此，我将把网格重新表示为一个可能的“移动”表，您可以根据您正在查看的字母转换对其进行索引。

首先从你的字母表中给每个字母分配一个数字(a =0, B=1, C=2，…等等)。

让我们举个例子:

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

现在，让我们使用现有字母的字母表(通常你可能每次都想使用相同的字母表):

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

然后你创建一个2D布尔数组，告诉你是否有某个字母转换可用:

     |  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

现在浏览单词列表，将单词转换为过渡段:

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

然后检查这些转换是否允许通过在你的表中查找它们:

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

如果它们都被允许，就有可能找到这个词。

例如，单词“头盔”可以在第4个转换(m到e:头盔)时被排除，因为表中的这个条目是假的。

单词hamster可以被排除，因为第一个(h到a)的转换是不允许的(在你的表中甚至不存在)。

现在，对于可能剩下的很少几个你没有删除的单词，试着按照你现在做的方法或在这里的其他答案中建议的方法在网格中找到它们。这是为了避免网格中相同字母之间的跳转导致的误报。例如，表格允许使用单词“help”，但网格不允许。

关于这个想法的一些进一步的性能改进技巧:

1. 不是使用2D数组，而是使用1D数组，自己简单地计算第二个字母的索引。因此，不要像上面那样使用12x12数组，而是创建一个长度为144的1D数组。如果你总是使用相同的字母表(即标准英语字母表的26x26 = 676x1数组)，即使不是所有的字母都显示在你的网格中，你也可以预先计算这个1D数组的索引，你需要测试来匹配你的字典单词。例如，在上面的例子中，'hello'的索引是

   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. Extend the idea to a 3D table (expressed as a 1D array), i.e. all allowed 3-letter combinations. That way you can eliminate even more words immediately and you reduce the number of array lookups for each word by 1: For 'hello', you only need 3 array lookups: hel, ell, llo. It will be very quick to build this table, by the way, as there are only 400 possible 3-letter-moves in your grid.

3. Pre-compute the indices of the moves in your grid that you need to include in your table. For the example above, you need to set the following entries to 'True':

   (0,0) (0,1) -> here: h, b : [6][0]
   (0,0) (1,0) -> here: h, e : [6][3]
   (0,0) (1,1) -> here: h, e : [6][3]
   (0,1) (0,0) -> here: b, h : [0][6]
   (0,1) (0,2) -> here: b, c : [0][1]
   .
   :
   

4. Also represent your game grid in a 1-D array with 16 entries and have the table pre-computed in 3. contain the indices into this array.

I'm sure if you use this approach you can get your code to run insanely fast, if you have the dictionary pre-computed and already loaded into memory.

BTW: Another nice thing to do, if you are building a game, is to run these sort of things immediately in the background. Start generating and solving the first game while the user is still looking at the title screen on your app and getting his finger into position to press "Play". Then generate and solve the next game as the user plays the previous one. That should give you a lot of time to run your code.

(I like this problem, so I'll probably be tempted to implement my proposal in Java sometime in the next days to see how it would actually perform... I'll post the code here once I do.)

UPDATE:

Ok, I had some time today and implemented this idea in Java:

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


class BoggleSolver {


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




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


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


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


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




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


DictionaryEntry[] candidateWords;
int candidateCount;


int[] usedBoardPositions;


DictionaryEntry[] foundWords;
int foundCount;


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


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


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


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


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




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


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


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


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




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


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




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


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


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


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


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

以下是一些结果:

对于原始问题(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

对于在原始问题中作为示例发布的信件(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

对于以下5x5网格:

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

它给出了这个:

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

为此，我使用了TWL06锦标赛拼字游戏单词列表，因为原始问题中的链接不再有效。这个文件是1.85MB，所以略短一些。buildDictionary函数抛出所有小于3个字母的单词。

以下是对其性能的一些观察:

• 它比Victor Nicollet的OCaml实现报告的性能慢了大约10倍。这是否是由于不同的算法、他使用的更短的字典、他的代码是在Java虚拟机中编译而我的代码是在Java虚拟机中运行的事实，或者是我们计算机的性能(我的是一台运行WinXP的Intel Q6600 @ 2.4MHz)，我不知道。但它比原始问题末尾引用的其他实现的结果快得多。所以，这个算法是否优于trie字典，目前我还不知道。

• checkWordTriplets()中使用的表格方法可以很好地近似于实际答案。它通过的3-5个单词中只有1个会不通过checkWords()测试(参见上面的候选人数量 vs. 实际单词数量)。

• 上面你看不到的东西:checkWordTriplets()函数大约需要3.65ms，因此在搜索过程中完全占主导地位。checkWords()函数占用了剩余的0.05-0.20毫秒。

• checkWordTriplets()函数的执行时间线性地依赖于字典的大小，并且实际上是独立于板的大小!< / >强

• checkWords()的执行时间取决于板子大小和checkWordTriplets()未排除的字数。

• 上面的checkWords()实现是我提出的最愚蠢的第一个版本。它基本上根本没有优化。但与checkWordTriplets()相比，它与应用程序的总体性能无关，所以我不担心它。但是，如果板尺寸变大，这个函数将变得越来越慢，最终将开始起作用。然后，它也需要进行优化。

• 这段代码的一个优点是它的灵活性:
  • 你可以很容易地改变板的大小:更新第10行和传递给initializeBoard()的String数组。
  • 它可以支持更大/不同的字母，并且可以处理像将'Qu'作为一个字母这样的事情，而没有任何性能开销。要做到这一点，我们需要更新第9行以及将字符转换为数字的两个位置(目前只需从ASCII值中减去65)
  李< / ul > < / >

  好吧，但我觉得现在这篇文章已经足够长了。我当然可以回答你可能有的任何问题，但让我们把它转移到评论。

我也用Java解决了这个问题。我的实现有269行，非常容易使用。首先，您需要创建Boggler类的一个新实例，然后用网格作为参数调用solve函数。在我的电脑上加载5万个单词的字典大约需要100毫秒，它在大约10-20毫秒内找到单词。找到的单词存储在数组列表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;
}
}

我用c语言解决了这个问题。在我的机器上运行大约需要48毫秒(其中98%的时间花在从磁盘加载字典和创建trie上)。字典是/usr/share/dict/american-english，有62886个单词。

源代码

我很快完美地解决了这个问题。我把它放进了一个安卓应用程序。在play store链接中查看视频，看看它是如何运作的。

Word Cheats是一个应用程序，“破解”任何矩阵风格的文字游戏。这个应用程序 来帮我在文字混淆器上作弊。它可以用于单词搜索， 沙沙，单词，单词查找器，单词破解，拼字游戏，和更多!< / p >

这里可以看到 https://play.google.com/store/apps/details?id=com.harris.wordcracker < / p >

在视频中查看应用程序的操作 https://www.youtube.com/watch?v=DL2974WmNAI < / p >

我是用c++写的求解器。我实现了一个自定义树结构。我不确定它是否可以被认为是一个trie，但它是相似的。每个节点有26个分支，一个代表字母表中的每个字母。我遍历拼字板的分支，与我的字典的分支平行。如果字典中不存在分支，我将停止在Boggle板上搜索它。我把黑板上的所有字母都转换成整数。所以A = 0。因为它只是数组，所以查找总是O(1)。每个节点存储它是否完成了一个单词以及它的子节点中存在多少单词。当发现单词时，树会被修剪，以减少重复搜索相同的单词。我相信修剪也是O(1)。

在<加载178,590个单词的字典;1秒。< br > 在4秒内解决100x100 Boggle (Boggle .txt)。
解决4x4 Boggle游戏的速度太快，无法提供有意义的基准。:) < / p >

Fast Boggle Solver GitHub Repo

我已经在c#中使用DFA算法解决了这个问题。你可以查看我的代码

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

除了在矩阵中查找单词外，我的算法还保存单词的实际路径，所以在设计单词查找游戏时，你可以检查在实际路径上是否有单词。

如何简单的排序和使用字典中的二分查找 ?

返回0.35秒中的整个列表，并可以进一步优化(例如删除含有未使用字母的单词等)。

from bisect import bisect_left


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


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


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


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


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


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


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


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


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

一个Node.JS JavaScript解决方案。在不到一秒钟的时间内计算所有100个独特的单词，其中包括阅读字典文件(MBA 2012)。

代码:

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

    package ProblemSolving;


import java.util.HashSet;
import java.util.Set;


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


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


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


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


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


}

给定一个有N行M列的Boggle板，让我们假设如下:

• N*M基本上大于可能单词的数量
• N*M基本上大于可能的最长单词

在这些假设下，该解的复杂度为O(N*M)。

我认为比较这个示例板的运行时间在很多方面都没有重点，但是，为了完整起见，这个解决方案在我的现代MacBook Pro上只需要0.2秒就可以完成。

这个解决方案将为语料库中的每个单词找到所有可能的路径。

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

我使用了链表的思想。每个Node都有一个字符值、一个位置值和一个next指针。

location值是我发现两个节点是否连接的方法。

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

所以使用这个网格，如果第一个节点的位置等于第二个节点的位置+/- 1(同一行)，+/- 9,10,11(上下一行)，我就知道两个节点是连接的。

我使用递归进行主搜索。它从wordList中取出一个单词，找到所有可能的起点，然后递归地找到下一个可能的连接，记住它不能去到它已经使用的位置(这就是为什么我添加$notInLoc)。

无论如何，我知道它需要一些重构，并且希望听到关于如何使它更干净的想法，但是它根据我使用的字典文件产生了正确的结果。根据黑板上元音和组合的数量，大约需要3到6秒。我知道，一旦我对字典结果进行预匹配，这将显著减少。

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


?>

我知道我真的在派对上迟到了，但我已经实现了，作为编码练习，在几种编程语言(c++， Java, Go, c#， Python, Ruby, JavaScript, Julia, Lua, PHP, Perl)中实现了一个填字器，我认为有人可能会对这些感兴趣，所以我在这里留下链接: https://github.com/AmokHuginnsson/boggle-solvers < / p >

import java.util.HashSet;
import java.util.Set;


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


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


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


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


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


}


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


}


}


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


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


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


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


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


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


}


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

这是我想出的解决填字游戏的办法。我想这是最“python”的做事方式:

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


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


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


def isCombinationAllowed(combination,length,doubleLength):


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


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




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


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

我善意地建议您不要将此部分用于所有可能的匹配，但它实际上提供了一种可能性来检查你生成的单词是否真的构成有效的单词:

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


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

一旦创建你的矩阵转换成一个字符数组，并执行这段代码

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)

输出:

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

我希望你能得到它。

该解决方案还提供了在给定的板中搜索的方向

算法:

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

输出:

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

代码:

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)