所以我想添加另一种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);

    ?>

I wrote my solver in C++. I implemented a custom tree structure. I'm not sure it can be considered a trie but it's similar. Each node has 26 branches, 1 for each letter of the alphabet. I traverse the branches of the boggle board in parallel with the branches of my dictionary. If the branch does not exist in the dictionary, I stop searching it on the Boggle board. I convert all the letters on the board to ints. So 'A' = 0. Since it's just arrays, lookup is always O(1). Each node stores if it completes a word and how many words exist in its children. The tree is pruned as words are found to reduce repeatedly searching for the same words. I believe pruning is also O(1).

CPU: Pentium SU2700 1.3GHz 内存:3 gb

在< 1秒内加载178,590个单词的字典。 在4秒内解决100x100 Boggle (Boggle .txt)。约44000字。 解决4x4 Boggle游戏的速度太快，无法提供有意义的基准。：）

快速Boggle求解GitHub回购

我认为你可能会花大部分时间去匹配那些不可能由你的字母网格构成的单词。所以，我要做的第一件事就是加快这一步，这应该能让你大致达到目的。

为此，我将把网格重新表示为一个可能的“移动”表，您可以根据您正在查看的字母转换对其进行索引。

首先从你的字母表中给每个字母分配一个数字(a =0, B=1, C=2，…等等)。

让我们举个例子:

h b c d
e e g h
l l k l
m o f p

现在，让我们使用现有字母的字母表(通常你可能每次都想使用相同的字母表):

 b | c | d | e | f | g | h | k | l | m |  o |  p
---+---+---+---+---+---+---+---+---+---+----+----
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

然后你创建一个2D布尔数组，告诉你是否有某个字母转换可用:

     |  0  1  2  3  4  5  6  7  8  9 10 11  <- from letter
     |  b  c  d  e  f  g  h  k  l  m  o  p
-----+--------------------------------------
 0 b |     T     T     T  T     
 1 c |  T     T  T     T  T
 2 d |     T           T  T
 3 e |  T  T     T     T  T  T  T
 4 f |                       T  T     T  T
 5 g |  T  T  T  T        T  T  T
 6 h |  T  T  T  T     T     T  T
 7 k |           T  T  T  T     T     T  T
 8 l |           T  T  T  T  T  T  T  T  T
 9 m |                          T     T
10 o |              T        T  T  T
11 p |              T        T  T
 ^
 to letter

现在浏览单词列表，将单词转换为过渡段:

hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10

然后检查这些转换是否允许通过在你的表中查找它们:

[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T

如果它们都被允许，就有可能找到这个词。

例如，单词“头盔”可以在第4个转换(m到e:头盔)时被排除，因为表中的这个条目是假的。

单词hamster可以被排除，因为第一个(h到a)的转换是不允许的(在你的表中甚至不存在)。

现在，对于可能剩下的很少几个你没有删除的单词，试着按照你现在做的方法或在这里的其他答案中建议的方法在网格中找到它们。这是为了避免网格中相同字母之间的跳转导致的误报。例如，表格允许使用单词“help”，但网格不允许。

关于这个想法的一些进一步的性能改进技巧:

Instead of using a 2D array, use a 1D array and simply compute the index of the second letter yourself. So, instead of a 12x12 array like above, make a 1D array of length 144. If you then always use the same alphabet (i.e. a 26x26 = 676x1 array for the standard english alphabet), even if not all letters show up in your grid, you can pre-compute the indices into this 1D array that you need to test to match your dictionary words. For example, the indices for 'hello' in the example above would be hello (6, 3, 8, 8, 10): 42 (from 6 + 3x12), 99, 104, 128 -> "hello" will be stored as 42, 99, 104, 128 in the dictionary Extend the idea to a 3D table (expressed as a 1D array), i.e. all allowed 3-letter combinations. That way you can eliminate even more words immediately and you reduce the number of array lookups for each word by 1: For 'hello', you only need 3 array lookups: hel, ell, llo. It will be very quick to build this table, by the way, as there are only 400 possible 3-letter-moves in your grid. Pre-compute the indices of the moves in your grid that you need to include in your table. For the example above, you need to set the following entries to 'True': (0,0) (0,1) -> here: h, b : [6][0] (0,0) (1,0) -> here: h, e : [6][3] (0,0) (1,1) -> here: h, e : [6][3] (0,1) (0,0) -> here: b, h : [0][6] (0,1) (0,2) -> here: b, c : [0][1] . : Also represent your game grid in a 1-D array with 16 entries and have the table pre-computed in 3. contain the indices into this array.

我相信如果您使用这种方法，您可以让您的代码运行得非常快，如果您预先计算了字典并已经加载到内存中。

顺便说一句:如果你正在创造一款游戏，你可以在后台立即运行这些内容。在用户仍然盯着你的应用标题屏幕，并将手指放在按“Play”的位置时开始生成和解决第一款游戏。然后在用户玩前一款游戏时生成并解决下一款游戏。这应该会给您很多时间来运行代码。

(我喜欢这个问题，所以我可能会忍不住在未来几天的某个时候用Java实现我的提议，看看它实际上是如何执行的……一旦我这样做，我将在这里张贴代码。)

更新:

好的，我今天有一些时间在Java中实现了这个想法:

class DictionaryEntry {
  public int[] letters;
  public int[] triplets;
}

class BoggleSolver {

  // Constants
  final int ALPHABET_SIZE = 5;  // up to 2^5 = 32 letters
  final int BOARD_SIZE    = 4;  // 4x4 board
  final int[] moves = {-BOARD_SIZE-1, -BOARD_SIZE, -BOARD_SIZE+1, 
                                  -1,                         +1,
                       +BOARD_SIZE-1, +BOARD_SIZE, +BOARD_SIZE+1};


  // Technically constant (calculated here for flexibility, but should be fixed)
  DictionaryEntry[] dictionary; // Processed word list
  int maxWordLength = 0;
  int[] boardTripletIndices; // List of all 3-letter moves in board coordinates

  DictionaryEntry[] buildDictionary(String fileName) throws IOException {
    BufferedReader fileReader = new BufferedReader(new FileReader(fileName));
    String word = fileReader.readLine();
    ArrayList<DictionaryEntry> result = new ArrayList<DictionaryEntry>();
    while (word!=null) {
      if (word.length()>=3) {
        word = word.toUpperCase();
        if (word.length()>maxWordLength) maxWordLength = word.length();
        DictionaryEntry entry = new DictionaryEntry();
        entry.letters  = new int[word.length()  ];
        entry.triplets = new int[word.length()-2];
        int i=0;
        for (char letter: word.toCharArray()) {
          entry.letters[i] = (byte) letter - 65; // Convert ASCII to 0..25
          if (i>=2)
            entry.triplets[i-2] = (((entry.letters[i-2]  << ALPHABET_SIZE) +
                                     entry.letters[i-1]) << ALPHABET_SIZE) +
                                     entry.letters[i];
          i++;
        }
        result.add(entry);
      }
      word = fileReader.readLine();
    }
    return result.toArray(new DictionaryEntry[result.size()]);
  }

  boolean isWrap(int a, int b) { // Checks if move a->b wraps board edge (like 3->4)
    return Math.abs(a%BOARD_SIZE-b%BOARD_SIZE)>1;
  }

  int[] buildTripletIndices() {
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int a=0; a<BOARD_SIZE*BOARD_SIZE; a++)
      for (int bm: moves) {
        int b=a+bm;
        if ((b>=0) && (b<board.length) && !isWrap(a, b))
          for (int cm: moves) {
            int c=b+cm;
            if ((c>=0) && (c<board.length) && (c!=a) && !isWrap(b, c)) {
              result.add(a);
              result.add(b);
              result.add(c);
            }
          }
      }
    int[] result2 = new int[result.size()];
    int i=0;
    for (Integer r: result) result2[i++] = r;
    return result2;
  }


  // Variables that depend on the actual game layout
  int[] board = new int[BOARD_SIZE*BOARD_SIZE]; // Letters in board
  boolean[] possibleTriplets = new boolean[1 << (ALPHABET_SIZE*3)];

  DictionaryEntry[] candidateWords;
  int candidateCount;

  int[] usedBoardPositions;

  DictionaryEntry[] foundWords;
  int foundCount;

  void initializeBoard(String[] letters) {
    for (int row=0; row<BOARD_SIZE; row++)
      for (int col=0; col<BOARD_SIZE; col++)
        board[row*BOARD_SIZE + col] = (byte) letters[row].charAt(col) - 65;
  }

  void setPossibleTriplets() {
    Arrays.fill(possibleTriplets, false); // Reset list
    int i=0;
    while (i<boardTripletIndices.length) {
      int triplet = (((board[boardTripletIndices[i++]]  << ALPHABET_SIZE) +
                       board[boardTripletIndices[i++]]) << ALPHABET_SIZE) +
                       board[boardTripletIndices[i++]];
      possibleTriplets[triplet] = true; 
    }
  }

  void checkWordTriplets() {
    candidateCount = 0;
    for (DictionaryEntry entry: dictionary) {
      boolean ok = true;
      int len = entry.triplets.length;
      for (int t=0; (t<len) && ok; t++)
        ok = possibleTriplets[entry.triplets[t]];
      if (ok) candidateWords[candidateCount++] = entry;
    }
  }

  void checkWords() { // Can probably be optimized a lot
    foundCount = 0;
    for (int i=0; i<candidateCount; i++) {
      DictionaryEntry candidate = candidateWords[i];
      for (int j=0; j<board.length; j++)
        if (board[j]==candidate.letters[0]) { 
          usedBoardPositions[0] = j;
          if (checkNextLetters(candidate, 1, j)) {
            foundWords[foundCount++] = candidate;
            break;
          }
        }
    }
  }

  boolean checkNextLetters(DictionaryEntry candidate, int letter, int pos) {
    if (letter==candidate.letters.length) return true;
    int match = candidate.letters[letter];
    for (int move: moves) {
      int next=pos+move;
      if ((next>=0) && (next<board.length) && (board[next]==match) && !isWrap(pos, next)) {
        boolean ok = true;
        for (int i=0; (i<letter) && ok; i++)
          ok = usedBoardPositions[i]!=next;
        if (ok) {
          usedBoardPositions[letter] = next;
          if (checkNextLetters(candidate, letter+1, next)) return true;
        }
      }
    }   
    return false;
  }


  // Just some helper functions
  String formatTime(long start, long end, long repetitions) {
    long time = (end-start)/repetitions;
    return time/1000000 + "." + (time/100000) % 10 + "" + (time/10000) % 10 + "ms";
  }

  String getWord(DictionaryEntry entry) {
    char[] result = new char[entry.letters.length];
    int i=0;
    for (int letter: entry.letters)
      result[i++] = (char) (letter+97);
    return new String(result);
  }

  void run() throws IOException {
    long start = System.nanoTime();

    // The following can be pre-computed and should be replaced by constants
    dictionary = buildDictionary("C:/TWL06.txt");
    boardTripletIndices = buildTripletIndices();
    long precomputed = System.nanoTime();


    // The following only needs to run once at the beginning of the program
    candidateWords     = new DictionaryEntry[dictionary.length]; // WAAAY too generous
    foundWords         = new DictionaryEntry[dictionary.length]; // WAAAY too generous
    usedBoardPositions = new int[maxWordLength];
    long initialized = System.nanoTime(); 

    for (int n=1; n<=100; n++) {
      // The following needs to run again for every new board
      initializeBoard(new String[] {"DGHI",
                                    "KLPS",
                                    "YEUT",
                                    "EORN"});
      setPossibleTriplets();
      checkWordTriplets();
      checkWords();
    }
    long solved = System.nanoTime();


    // Print out result and statistics
    System.out.println("Precomputation finished in " + formatTime(start, precomputed, 1)+":");
    System.out.println("  Words in the dictionary: "+dictionary.length);
    System.out.println("  Longest word:            "+maxWordLength+" letters");
    System.out.println("  Number of triplet-moves: "+boardTripletIndices.length/3);
    System.out.println();

    System.out.println("Initialization finished in " + formatTime(precomputed, initialized, 1));
    System.out.println();

    System.out.println("Board solved in "+formatTime(initialized, solved, 100)+":");
    System.out.println("  Number of candidates: "+candidateCount);
    System.out.println("  Number of actual words: "+foundCount);
    System.out.println();

    System.out.println("Words found:");
    int w=0;
    System.out.print("  ");
    for (int i=0; i<foundCount; i++) {
      System.out.print(getWord(foundWords[i]));
      w++;
      if (w==10) {
        w=0;
        System.out.println(); System.out.print("  ");
      } else
        if (i<foundCount-1) System.out.print(", ");
    }
    System.out.println();
  }

  public static void main(String[] args) throws IOException {
    new BoggleSolver().run();
  }
}

以下是一些结果:

对于原始问题(DGHI…)中发布的图片的网格:

Precomputation finished in 239.59ms:
  Words in the dictionary: 178590
  Longest word:            15 letters
  Number of triplet-moves: 408

Initialization finished in 0.22ms

Board solved in 3.70ms:
  Number of candidates: 230
  Number of actual words: 163 

Words found:
  eek, eel, eely, eld, elhi, elk, ern, erupt, erupts, euro
  eye, eyer, ghi, ghis, glee, gley, glue, gluer, gluey, glut
  gluts, hip, hiply, hips, his, hist, kelp, kelps, kep, kepi
  kepis, keps, kept, kern, key, kye, lee, lek, lept, leu
  ley, lunt, lunts, lure, lush, lust, lustre, lye, nus, nut
  nuts, ore, ort, orts, ouph, ouphs, our, oust, out, outre
  outs, oyer, pee, per, pert, phi, phis, pis, pish, plus
  plush, ply, plyer, psi, pst, pul, pule, puler, pun, punt
  punts, pur, pure, puree, purely, pus, push, put, puts, ree
  rely, rep, reply, reps, roe, roue, roup, roups, roust, rout
  routs, rue, rule, ruly, run, runt, runts, rupee, rush, rust
  rut, ruts, ship, shlep, sip, sipe, spue, spun, spur, spurn
  spurt, strep, stroy, stun, stupe, sue, suer, sulk, sulker, sulky
  sun, sup, supe, super, sure, surely, tree, trek, trey, troupe
  troy, true, truly, tule, tun, tup, tups, turn, tush, ups
  urn, uts, yeld, yelk, yelp, yelps, yep, yeps, yore, you
  your, yourn, yous

对于在原始问题中作为示例发布的信件(FXIE…)

Precomputation finished in 239.68ms:
  Words in the dictionary: 178590
  Longest word:            15 letters
  Number of triplet-moves: 408

Initialization finished in 0.21ms

Board solved in 3.69ms:
  Number of candidates: 87
  Number of actual words: 76

Words found:
  amble, ambo, ami, amie, asea, awa, awe, awes, awl, axil
  axile, axle, boil, bole, box, but, buts, east, elm, emboli
  fame, fames, fax, lei, lie, lima, limb, limbo, limbs, lime
  limes, lob, lobs, lox, mae, maes, maw, maws, max, maxi
  mesa, mew, mewl, mews, mil, mile, milo, mix, oil, ole
  sae, saw, sea, seam, semi, sew, stub, swam, swami, tub
  tubs, tux, twa, twae, twaes, twas, uts, wae, waes, wamble
  wame, wames, was, wast, wax, west

对于以下5x5网格:

R P R I T
A H H L N
I E T E P
Z R Y S G
O G W E Y

它给出了这个:

Precomputation finished in 240.39ms:
  Words in the dictionary: 178590
  Longest word:            15 letters
  Number of triplet-moves: 768

Initialization finished in 0.23ms

Board solved in 3.85ms:
  Number of candidates: 331
  Number of actual words: 240

Words found:
  aero, aery, ahi, air, airt, airth, airts, airy, ear, egest
  elhi, elint, erg, ergo, ester, eth, ether, eye, eyen, eyer
  eyes, eyre, eyrie, gel, gelt, gelts, gen, gent, gentil, gest
  geste, get, gets, gey, gor, gore, gory, grey, greyest, greys
  gyre, gyri, gyro, hae, haet, haets, hair, hairy, hap, harp
  heap, hear, heh, heir, help, helps, hen, hent, hep, her
  hero, hes, hest, het, hetero, heth, hets, hey, hie, hilt
  hilts, hin, hint, hire, hit, inlet, inlets, ire, leg, leges
  legs, lehr, lent, les, lest, let, lethe, lets, ley, leys
  lin, line, lines, liney, lint, lit, neg, negs, nest, nester
  net, nether, nets, nil, nit, ogre, ore, orgy, ort, orts
  pah, pair, par, peg, pegs, peh, pelt, pelter, peltry, pelts
  pen, pent, pes, pest, pester, pesty, pet, peter, pets, phi
  philter, philtre, phiz, pht, print, pst, rah, rai, rap, raphe
  raphes, reap, rear, rei, ret, rete, rets, rhaphe, rhaphes, rhea
  ria, rile, riles, riley, rin, rye, ryes, seg, sel, sen
  sent, senti, set, sew, spelt, spelter, spent, splent, spline, splint
  split, stent, step, stey, stria, striae, sty, stye, tea, tear
  teg, tegs, tel, ten, tent, thae, the, their, then, these
  thesp, they, thin, thine, thir, thirl, til, tile, tiles, tilt
  tilter, tilth, tilts, tin, tine, tines, tirl, trey, treys, trog
  try, tye, tyer, tyes, tyre, tyro, west, wester, wry, wryest
  wye, wyes, wyte, wytes, yea, yeah, year, yeh, yelp, yelps
  yen, yep, yeps, yes, yester, yet, yew, yews, zero, zori

为此，我使用了TWL06锦标赛拼字词列表，因为原始问题中的链接不再有效。这个文件是1.85MB，所以略短一些。buildDictionary函数抛出所有小于3个字母的单词。

以下是对其性能的一些观察:

It's about 10 times slower than the reported performance of Victor Nicollet's OCaml implementation. Whether this is caused by the different algorithm, the shorter dictionary he used, the fact that his code is compiled and mine runs in a Java virtual machine, or the performance of our computers (mine is an Intel Q6600 @ 2.4MHz running WinXP), I don't know. But it's much faster than the results for the other implementations quoted at the end of the original question. So, whether this algorithm is superior to the trie dictionary or not, I don't know at this point. The table method used in checkWordTriplets() yields a very good approximation to the actual answers. Only 1 in 3-5 words passed by it will fail the checkWords() test (See number of candidates vs. number of actual words above). Something you can't see above: The checkWordTriplets() function takes about 3.65ms and is therefore fully dominant in the search process. The checkWords() function takes up pretty much the remaining 0.05-0.20 ms. The execution time of the checkWordTriplets() function depends linearly on the dictionary size and is virtually independent of board size! The execution time of checkWords() depends on the board size and the number of words not ruled out by checkWordTriplets(). The checkWords() implementation above is the dumbest first version I came up with. It is basically not optimized at all. But compared to checkWordTriplets() it is irrelevant for the total performance of the application, so I didn't worry about it. But, if the board size gets bigger, this function will get slower and slower and will eventually start to matter. Then, it would need to be optimized as well. One nice thing about this code is its flexibility: You can easily change the board size: Update line 10 and the String array passed to initializeBoard(). It can support larger/different alphabets and can handle things like treating 'Qu' as one letter without any performance overhead. To do this, one would need to update line 9 and the couple of places where characters are converted to numbers (currently simply by subtracting 65 from the ASCII value)

好吧，但我觉得现在这篇文章已经足够长了。我当然可以回答你可能有的任何问题，但让我们把它转移到评论。

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

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

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

当我看到问题陈述时，我想到了“Trie”。但看到其他一些海报使用了这种方法，我寻找另一种不同的方法。可惜的是，Trie方法表现更好。我在我的机器上运行了Kent的Perl解决方案，在调整它以使用我的字典文件后，它花了0.31秒运行。我自己的perl实现需要0.54秒才能运行。

这就是我的方法:

Create a transition hash to model the legal transitions. Iterate through all 16^3 possible three letter combinations. In the loop, exclude illegal transitions and repeat visits to the same square. Form all the legal 3-letter sequences and store them in a hash. Then loop through all words in the dictionary. Exclude words that are too long or short Slide a 3-letter window across each word and see if it is among the 3-letter combos from step 2. Exclude words that fail. This eliminates most non-matches. If still not eliminated, use a recursive algorithm to see if the word can be formed by making paths through the puzzle. (This part is slow, but called infrequently.) Print out the words I found. I tried 3-letter and 4-letter sequences, but 4-letter sequences slowed the program down.

在我的代码中，我使用/usr/share/dict/words作为我的字典。它是MAC OS X和许多Unix系统的标准配置。如果你愿意，你可以使用另一个文件。要破解不同的谜题，只需更改变量@puzzle。这将很容易适应更大的矩阵。你只需要改变%transitions哈希值和%legalTransitions哈希值。

这种解决方案的优点是代码短，数据结构简单。

下面是Perl代码(我知道它使用了太多的全局变量):

#!/usr/bin/perl
use Time::HiRes  qw{ time };

sub readFile($);
sub findAllPrefixes($);
sub isWordTraceable($);
sub findWordsInPuzzle(@);

my $startTime = time;

# Puzzle to solve

my @puzzle = ( 
    F, X, I, E,
    A, M, L, O,
    E, W, B, X,
    A, S, T, U
);

my $minimumWordLength = 3;
my $maximumPrefixLength = 3; # I tried four and it slowed down.

# Slurp the word list.
my $wordlistFile = "/usr/share/dict/words";

my @words = split(/\n/, uc(readFile($wordlistFile)));
print "Words loaded from word list: " . scalar @words . "\n";

print "Word file load time: " . (time - $startTime) . "\n";
my $postLoad = time;

# Define the legal transitions from one letter position to another. 
# Positions are numbered 0-15.
#     0  1  2  3
#     4  5  6  7
#     8  9 10 11
#    12 13 14 15
my %transitions = ( 
   -1 => [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
    0 => [1,4,5], 
    1 => [0,2,4,5,6],
    2 => [1,3,5,6,7],
    3 => [2,6,7],
    4 => [0,1,5,8,9],
    5 => [0,1,2,4,6,8,9,10],
    6 => [1,2,3,5,7,9,10,11],
    7 => [2,3,6,10,11],
    8 => [4,5,9,12,13],
    9 => [4,5,6,8,10,12,13,14],
    10 => [5,6,7,9,11,13,14,15],
    11 => [6,7,10,14,15],
    12 => [8,9,13],
    13 => [8,9,10,12,14],
    14 => [9,10,11,13,15],
    15 => [10,11,14]
);

# Convert the transition matrix into a hash for easy access.
my %legalTransitions = ();
foreach my $start (keys %transitions) {
    my $legalRef = $transitions{$start};
    foreach my $stop (@$legalRef) {
        my $index = ($start + 1) * (scalar @puzzle) + ($stop + 1);
        $legalTransitions{$index} = 1;
    }
}

my %prefixesInPuzzle = findAllPrefixes($maximumPrefixLength);

print "Find prefixes time: " . (time - $postLoad) . "\n";
my $postPrefix = time;

my @wordsFoundInPuzzle = findWordsInPuzzle(@words);

print "Find words in puzzle time: " . (time - $postPrefix) . "\n";

print "Unique prefixes found: " . (scalar keys %prefixesInPuzzle) . "\n";
print "Words found (" . (scalar @wordsFoundInPuzzle) . ") :\n    " . join("\n    ", @wordsFoundInPuzzle) . "\n";

print "Total Elapsed time: " . (time - $startTime) . "\n";

###########################################

sub readFile($) {
    my ($filename) = @_;
    my $contents;
    if (-e $filename) {
        # This is magic: it opens and reads a file into a scalar in one line of code. 
        # See http://www.perl.com/pub/a/2003/11/21/slurp.html
        $contents = do { local( @ARGV, $/ ) = $filename ; <> } ; 
    }
    else {
        $contents = '';
    }
    return $contents;
}

# Is it legal to move from the first position to the second? They must be adjacent.
sub isLegalTransition($$) {
    my ($pos1,$pos2) = @_;
    my $index = ($pos1 + 1) * (scalar @puzzle) + ($pos2 + 1);
    return $legalTransitions{$index};
}

# Find all prefixes where $minimumWordLength <= length <= $maxPrefixLength
#
#   $maxPrefixLength ... Maximum length of prefix we will store. Three gives best performance. 
sub findAllPrefixes($) {
    my ($maxPrefixLength) = @_;
    my %prefixes = ();
    my $puzzleSize = scalar @puzzle;

    # Every possible N-letter combination of the letters in the puzzle 
    # can be represented as an integer, though many of those combinations
    # involve illegal transitions, duplicated letters, etc.
    # Iterate through all those possibilities and eliminate the illegal ones.
    my $maxIndex = $puzzleSize ** $maxPrefixLength;

    for (my $i = 0; $i < $maxIndex; $i++) {
        my @path;
        my $remainder = $i;
        my $prevPosition = -1;
        my $prefix = '';
        my %usedPositions = ();
        for (my $prefixLength = 1; $prefixLength <= $maxPrefixLength; $prefixLength++) {
            my $position = $remainder % $puzzleSize;

            # Is this a valid step?
            #  a. Is the transition legal (to an adjacent square)?
            if (! isLegalTransition($prevPosition, $position)) {
                last;
            }

            #  b. Have we repeated a square?
            if ($usedPositions{$position}) {
                last;
            }
            else {
                $usedPositions{$position} = 1;
            }

            # Record this prefix if length >= $minimumWordLength.
            $prefix .= $puzzle[$position];
            if ($prefixLength >= $minimumWordLength) {
                $prefixes{$prefix} = 1;
            }

            push @path, $position;
            $remainder -= $position;
            $remainder /= $puzzleSize;
            $prevPosition = $position;
        } # end inner for
    } # end outer for
    return %prefixes;
}

# Loop through all words in dictionary, looking for ones that are in the puzzle.
sub findWordsInPuzzle(@) {
    my @allWords = @_;
    my @wordsFound = ();
    my $puzzleSize = scalar @puzzle;
WORD: foreach my $word (@allWords) {
        my $wordLength = length($word);
        if ($wordLength > $puzzleSize || $wordLength < $minimumWordLength) {
            # Reject word as too short or too long.
        }
        elsif ($wordLength <= $maximumPrefixLength ) {
            # Word should be in the prefix hash.
            if ($prefixesInPuzzle{$word}) {
                push @wordsFound, $word;
            }
        }
        else {
            # Scan through the word using a window of length $maximumPrefixLength, looking for any strings not in our prefix list.
            # If any are found that are not in the list, this word is not possible.
            # If no non-matches are found, we have more work to do.
            my $limit = $wordLength - $maximumPrefixLength + 1;
            for (my $startIndex = 0; $startIndex < $limit; $startIndex ++) {
                if (! $prefixesInPuzzle{substr($word, $startIndex, $maximumPrefixLength)}) {
                    next WORD;
                }
            }
            if (isWordTraceable($word)) {
                # Additional test necessary: see if we can form this word by following legal transitions
                push @wordsFound, $word;
            }
        }

    }
    return @wordsFound;
}

# Is it possible to trace out the word using only legal transitions?
sub isWordTraceable($) {
    my $word = shift;
    return traverse([split(//, $word)], [-1]); # Start at special square -1, which may transition to any square in the puzzle.
}

# Recursively look for a path through the puzzle that matches the word.
sub traverse($$) {
    my ($lettersRef, $pathRef) = @_;
    my $index = scalar @$pathRef - 1;
    my $position = $pathRef->[$index];
    my $letter = $lettersRef->[$index];
    my $branchesRef =  $transitions{$position};
BRANCH: foreach my $branch (@$branchesRef) {
            if ($puzzle[$branch] eq $letter) {
                # Have we used this position yet?
                foreach my $usedBranch (@$pathRef) {
                    if ($usedBranch == $branch) {
                        next BRANCH;
                    }
                }
                if (scalar @$lettersRef == $index + 1) {
                    return 1; # End of word and success.
                }
                push @$pathRef, $branch;
                if (traverse($lettersRef, $pathRef)) {
                    return 1; # Recursive success.
                }
                else {
                    pop @$pathRef;
                }
            }
        }
    return 0; # No path found. Failed.
}

搞笑。几天前我差点因为这款该死的游戏而发布了同样的问题!然而我没有，因为我只是在谷歌上搜索boggle solver python，得到了我想要的所有答案。