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

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

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

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

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

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

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

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

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

import java.util.HashSet;
import java.util.Set;

/**
 * @author Sujeet Kumar (mrsujeet@gmail.com) It prints out all strings that can
 *         be formed by moving left, right, up, down, or diagonally and exist in
 *         a given dictionary , without repeating any cell. Assumes words are
 *         comprised of lower case letters. Currently prints words as many times
 *         as they appear, not just once. *
 */

public class BoggleGame 
{
  /* A sample 4X4 board/2D matrix */
  private static char[][] board = { { 's', 'a', 's', 'g' },
                                  { 'a', 'u', 't', 'h' }, 
                                  { 'r', 't', 'j', 'e' },
                                  { 'k', 'a', 'h', 'e' }
};

/* A sample dictionary which contains unique collection of words */
private static Set<String> dictionary = new HashSet<String>();

private static boolean[][] visited = new boolean[board.length][board[0].length];

public static void main(String[] arg) {
    dictionary.add("sujeet");
    dictionary.add("sarthak");
    findWords();

}

// show all words, starting from each possible starting place
private static void findWords() {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            StringBuffer buffer = new StringBuffer();
            dfs(i, j, buffer);
        }

    }

}

// run depth first search starting at cell (i, j)
private static void dfs(int i, int j, StringBuffer buffer) {
    /*
     * base case: just return in recursive call when index goes out of the
     * size of matrix dimension
     */
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
        return;
    }

    /*
     * base case: to return in recursive call when given cell is already
     * visited in a given string of word
     */
    if (visited[i][j] == true) { // can't visit a cell more than once
        return;
    }

    // not to allow a cell to reuse
    visited[i][j] = true;

    // combining cell character with other visited cells characters to form
    // word a potential word which may exist in dictionary
    buffer.append(board[i][j]);

    // found a word in dictionary. Print it.
    if (dictionary.contains(buffer.toString())) {
        System.out.println(buffer);
    }

    /*
     * consider all neighbors.For a given cell considering all adjacent
     * cells in horizontal, vertical and diagonal direction
     */
    for (int k = i - 1; k <= i + 1; k++) {
        for (int l = j - 1; l <= j + 1; l++) {
            dfs(k, l, buffer);

        }

    }
    buffer.deleteCharAt(buffer.length() - 1);
    visited[i][j] = false;
  }
}

该解决方案还提供了在给定的板中搜索的方向

一件事:

1. Uses trie to save all the word in the english to fasten the search
2. The uses DFS to search the words in Boggle

输出:

Found "pic" directions from (4,0)(p) go  → →
Found "pick" directions from (4,0)(p) go  → → ↑
Found "pickman" directions from (4,0)(p) go  → → ↑ ↑ ↖ ↑
Found "picket" directions from (4,0)(p) go  → → ↑ ↗ ↖
Found "picked" directions from (4,0)(p) go  → → ↑ ↗ ↘
Found "pickle" directions from (4,0)(p) go  → → ↑ ↘ →

代码:

from collections import defaultdict
from nltk.corpus import words
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize

english_words = words.words()

# If you wan to remove stop words
# stop_words = set(stopwords.words('english'))
# english_words = [w for w in english_words if w not in stop_words]

boggle = [
    ['c', 'n', 't', 's', 's'],
    ['d', 'a', 't', 'i', 'n'],
    ['o', 'o', 'm', 'e', 'l'],
    ['s', 'i', 'k', 'n', 'd'],
    ['p', 'i', 'c', 'l', 'e']
]

# Instead of X and Y co-ordinates
# better to use Row and column
lenc = len(boggle[0])
lenr = len(boggle)

# Initialize trie datastructure
trie_node = {'valid': False, 'next': {}}

# lets get the delta to find all the nighbors
neighbors_delta = [
    (-1,-1, "↖"),
    (-1, 0, "↑"),
    (-1, 1, "↗"),
    (0, -1, "←"),
    (0,  1, "→"),
    (1, -1, "↙"),
    (1,  0, "↓"),
    (1,  1, "↘"),
]


def gen_trie(word, node):
    """udpates the trie datastructure using the given word"""
    if not word:
        return

    if word[0] not in node:
        node[word[0]] = {'valid': len(word) == 1, 'next': {}}

    # recursively build trie
    gen_trie(word[1:], node[word[0]])


def build_trie(words, trie):
    """Builds trie data structure from the list of words given"""
    for word in words:
        gen_trie(word, trie)
    return trie


def get_neighbors(r, c):
    """Returns the neighbors for a given co-ordinates"""
    n = []
    for neigh in neighbors_delta:
        new_r = r + neigh[0]
        new_c = c + neigh[1]

        if (new_r >= lenr) or (new_c >= lenc) or (new_r < 0) or (new_c < 0):
            continue
        n.append((new_r, new_c, neigh[2]))
    return n


def dfs(r, c, visited, trie, now_word, direction):
    """Scan the graph using DFS"""
    if (r, c) in visited:
        return

    letter = boggle[r][c]
    visited.append((r, c))

    if letter in trie:
        now_word += letter

        if trie[letter]['valid']:
            print('Found "{}" {}'.format(now_word, direction))

        neighbors = get_neighbors(r, c)
        for n in neighbors:
            dfs(n[0], n[1], visited[::], trie[letter], now_word, direction + " " + n[2])


def main(trie_node):
    """Initiate the search for words in boggle"""
    trie_node = build_trie(english_words, trie_node)

    # print the board
    print("Given board")
    for i in range(lenr):print (boggle[i])
    print ('\n')

    for r in range(lenr):
        for c in range(lenc):
            letter = boggle[r][c]
            dfs(r, c, [], trie_node, '', 'directions from ({},{})({}) go '.format(r, c, letter))


if __name__ == '__main__':
    main(trie_node)