最近我一直在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)


当前回答

所以我想添加另一种PHP方法来解决这个问题,因为每个人都喜欢PHP。 我想做一点重构,比如对字典文件使用regexpression匹配,但现在我只是将整个字典文件加载到一个wordList中。

我使用了链表的思想。每个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);

    ?>

其他回答

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

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

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

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

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

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

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

首先,阅读c#语言设计师如何解决一个相关问题: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx。

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

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

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

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

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

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

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

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

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

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

我会从这里开始。