algorithm - 如何查找可能的字母矩阵中的单词列表[Boggle Solver]

  显示原文与译文双语对照的内容

最近我一直在玩游戏我的iphone称为争夺。 有些人可能会把这个游戏理解为 Boggle 。 实际上,当游戏开始时,你会得到像这样的字母矩阵:


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

游戏的目标是找到尽可能多的单词,这些单词可以通过链接字母来形成。 你可以与任何字母开头,字母都环绕着你是公平的游戏,一旦你进入下一个字母,周围的所有信件,信是公平的游戏,除了任何先前使用字母。 因此,在上面的网格中,我可以提出单词 LOBTUXSEAFAME,等等 字必须至少为 3个字符,但在这里游戏中的字符必须是 16个字符,但在某些实现中可能会有所不同。 虽然这个游戏很有趣,让人上瘾,我显然不是很好,我想稍微作弊通过一个程序,( 单词越长,你得到的点数越多) 会给我最好的词。

Sample Boggle

不幸的是,我对算法或者它们的效率并不是很好。 我第一次尝试使用字典 ,比如这个 ( ~2.mb ),做一个线性搜索试图匹配字典条目的组合。 这需要一个长时间找到可能的单词,因为你只有 2分钟每轮,它仅仅是不够的。

我想看看是否有Stackoverflowers能提供更有效的解决方案。 我在寻找使用大 3 Ps的解决方案: python,PHP和 Perl,尽管任何使用Java或者 C++的东西都很酷,因为速度是至关重要的。

当前解决方案:

奖金:

我向这个问题添加了一个奖励,因为我感谢所有参与他们的程序的人。 遗憾的是我只能给你们接受的答案,所以我将测量谁的最快犹豫解决 7天从现在和奖得主赏金。

奖励奖励。感谢参加了。

时间:

我的答案与其他的一样,但我将发布它,因为它看起来比其他 python 解决方案更快,从设置字典更快。 (我检查这对约翰解决方案。)后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个字母的单词。

编辑 2: 我很好奇为什么Fredric解决方案的Kent Perl会更快;结果是使用regular-expression匹配而不是一组字符。 在 python 中做同样的事情,速度加倍。

对于字典加速,有一个一般的转换/过程可以在提前的时候减少字典比较。

鉴于上述网格只包含 16字符,其中一些重复的,可以大大减少总钥匙的数量在你的字典通过过滤条目高不可攀的人物。

我认为这是最明显的优化,但没有人这么做。

在输入处理过程中,它把我从 200,000个键的字典中减少到 2,000个键。 这至少减少了内存开销,而且一定会映射到一个速度,因为内存不是无限快速的。

Perl实现

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

我也有几个adaptions理论上允许网格与漏洞功能,( 假设你得到了输入,它就会以某种方式排列) 和不同大小的网格线。

early-filter是迄今为止最重要瓶颈在我的应用程序中,正如之前怀疑的,评论,从 1.5年代 7.5s线阻塞它。

执行时,似乎所有单个数字都在它们自己的有效单词上,但我很肯定这是因为字典文件是如何工作的。

它有点臃肿,但至少我重用了来自cpan的Tree::Trie

部分的灵感来自于现有的实现,其中一些我已经想到了。

建设性的批评和方法可以改进的欢迎(/me 指出他从不搜索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/execution信息:


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

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

更多Mumblings关于 正规表达式 优化

我使用的正规表达式 优化对于multi-solve字典是无用的,对于 multi-solve,你需要完整的字典,而不是 pre-trimmed 。

然而,对于一次性解决,它真的很快。 ( 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分钟。

你可以将问题分成两个部分:

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

理想情况下,( 2 ) 还应该包括一种测试字符串是否是有效单词前缀的方法- 这将允许你删除搜索并保存整个时间堆。

Rosenfield的Adam Trie是( 2 )的解决方案。 它很优雅,可能是你的算法专家喜欢的,但是使用现代语言和现代计算机,我们可以是一位 lazier 。 同样,就像Kent所暗示的,我们可以通过丢弃不存在于网格中的字母来减小我们的字典大小。 下面是一些 python:


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

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

 return words, prefixes

哇;constant-time前缀测试。加载你链接的字典需要几秒钟时间,但是只有一对:- ) ( 注意 words <= prefixes )

现在,对于第( 1 ) 部分,我倾向于考虑图形。 因此,我将构建一个类似这样的字典:


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

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

构建有点笨拙,因为有 8个可能的位置,你必须进行边界检查。 下面是一些 correspondingly-clumsy 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))

这里代码还将字典映射为对应的字符。 这让我把位置列表变成一个单词:


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

最后,我们执行depth-first搜索。 基本过程是:

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

代码需要( 字面上) 几秒钟来加载字典,但剩下的是我的机器上的instant 。

我尝试在java中。大约需要 2年代读文件,建立单词查找树,和周围 50女士来解决这个难题。 我使用字典相关问题(几句话,用英语我不知道存在如仙,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版本。

这是一个工作的PHP版本的Fouhy python 解决方案。

虽然我从每个人的答案中获取了一些指针,但这大部分是从John复制的。


$boggle ="fxie
 amlo
 ewbx
 astu";

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

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

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

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

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

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

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

下面是一个 live链接如果你想试试它。 虽然在我的本地机器上使用了 ~2s,但它在我的网络服务器上需要 ~5s 。 不管哪种情况,它都不是很快。 尽管如此,它还是相当可怕的,所以我可以想象这个时间可以显著减少。 关于如何完成这一切的任何指针都是值得的。 缺少元组的php使得坐标的协调和我无法理解,我无法理解到底发生了什么。

的编辑: 一些修复使它的本地版本少于 1.

我对VB不感兴趣。 我的解决方法与这里给出的许多解决方案不同。

我的时间是:

  • 将字典和单词前缀加载到hashtable中: .5到 1秒。
  • 查找单词:在 10毫秒内平均。

编辑:网站主机服务器上的字典加载时间比我的主计算机运行大约 1到 1.5秒。

我不知道服务器上的负载会使时间恶化。

我在. NET 中将我的解决方案写成网页。 myvrad.com/boggle

我正在使用原始问题中引用的词典。

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

我使用了所有唯一单词前缀和单词的hashtable而不是一个 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 上面.
 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

当我看到问题语句时,我想到"trie"。 但由于其他一些海报使用了这种方法,我寻找另一种方法只是为了与众不同。 哎呀,Trie方法执行得更好。 我跑perl的肯特解决方案在我的机器上, 0.31 秒运行,改造后使用我的字典文件。 我自己的perl实现需要花费秒的时间来运行 0.54.

这是我的方法:

  1. 创建一个转换哈希来建模合法转换。

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

    • 在循环中,排除非法的转换并重复访问同一个正方形。 形成所有合法的3 -letter序列并将它们存储在一个散列中。
  3. 然后遍历字典中的所有单词。

    • 排除过长或者短的单词
    • 在每个单词之间滑动一个 3 -letter窗口,并查看它是否在第 3步的-letter组合中。 排除失败的单词。这将消除大多数 non-matches 。
    • 如果仍然没有消除的话,使用递归算法看看这个词是否可以通过在谜题中生成路径来形成。 ( 这里部分较慢,但不经常调用) 。
  4. 打印出我找到的单词。

    我尝试了 3 -letter和 4 -letter序列,但是 4 -letter序列减慢了程序的速度。

在我的代码中,我在字典中使用/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.
}

我知道我超级晚但我做了一个不久前在 PHP——只是为了好玩。

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu 发现 75话说( 133 pts ) 0.90108 秒

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

表明了程序实际上是做什么——每个字母就是它开始通过模式,而每个'。'显示了一个路径,它一直在努力。 '。'越多,它搜索的就越多。

如果你想要密码,请告诉我。。 这是一个可怕的混合的PHP和 HTML,从未打算看到的光,所以我不敢在这里张贴它:p

...