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


当前回答

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

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

其他回答

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

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

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

我会从这里开始。

令人惊讶的是,没有人尝试使用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秒。

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

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

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

我知道我已经非常晚了,但是我之前用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

我也用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;
    }
}