最近我一直在iPhone上玩一款名为《Scramble》的游戏。有些人可能知道这个游戏叫拼字游戏。从本质上讲,当游戏开始时,你会得到一个字母矩阵:

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

The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, except for any previously used letters. So in the grid above, for example, I could come up with the words LOB, TUX, SEA, FAME, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations. While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).

(来源:boggled.org)

不幸的是,我不太擅长算法或它们的效率等等。我的第一次尝试使用一个像这样的字典(约2.3MB),并进行线性搜索,试图匹配字典条目的组合。这需要花费很长时间来找到可能的单词,因为你每轮只有2分钟的时间,这是不够的。

我很有兴趣看看是否有任何Stackoverflowers可以提出更有效的解决方案。我主要是在寻找使用三大p的解决方案:Python、PHP和Perl,尽管任何使用Java或c++的东西也很酷,因为速度是至关重要的。

目前的解决方案:

Adam Rosenfield, Python, ~20岁 John Fouhy, Python, ~3秒 Kent Fredric, Perl, ~1s Darius Bacon, Python, ~1s rvarcher, VB。净,~ 1 s Paolo Bergantino, PHP(实时链接),~5s(本地~2s)


当前回答

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

源代码

其他回答

如何简单的排序和使用字典中的二进制搜索?

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

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

我的答案和这里的其他答案一样,但我把它贴出来是因为它看起来比其他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中做同样的事情,速度大约会翻倍。

我知道我已经非常晚了,但是我之前用PHP做了一个——只是为了好玩……

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu 在0.90108秒内找到75个单词(133分)

F……X . .我 .............. E ............... 一个 ...................................... 米 .............................. L ............................ O ............................... E .................... W ............................ B .......................... X 一个 .................. 年代 .................................................. T ................. U…

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

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

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

}