最快的解决方案可能是将字典存储在一个trie中。然后，创建一个三元组队列(x, y, s)，其中队列中的每个元素对应于一个可以在网格中拼写的单词的前缀s，结束于位置(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中，则可以在常数时间内测试s+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))

输出:

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

Notes: This program doesn't output 1-letter words, or filter by word length at all. That's easy to add but not really relevant to the problem. It also outputs some words multiple times if they can be spelled in multiple ways. If a given word can be spelled in many different ways (worst case: every letter in the grid is the same (e.g. 'A') and a word like 'aaaaaaaaaa' is in your dictionary), then the running time will get horribly exponential. Filtering out duplicates and sorting is trivial to due after the algorithm has finished.

这是我想出的解决填字游戏的办法。我想这是最“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)]

我已经在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"]

给定一个有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}"

我的答案和这里的其他答案一样，但我把它贴出来是因为它看起来比其他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个字母的单词。

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

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

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

理想情况下，(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)

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

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

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)

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

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

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