我正在研究类似填字游戏的问题，但我不知道如何设计算法。
例如：
因此，算法的任务是制作存储在字典中的正确单词。
app - > lapp - > leapp - > lecapp - > .... - > lappe - > eappc - > ... - > appl - > apple（正确答案）
这个算法的最佳解决方案是什么？
您可能对Gol和Jacobson（1988）的研究论文"The World's Fastest Scrabble Program"感兴趣。算法以伪代码概述，因此需要花费一些工作才能将其塑造成可用的形式并将它们粘合在一起;但是，作者概述的程序非常有用。
将您的字典存储为树，例如：
*
|
+----+----+
| |
A* B
| |
+--+--+ E*
| | |
P S +-+-+
| | | |
P* K* A E*
| |
+-+-+ +-+-+
| | | |
E L D* N*
| |
A E*
|
L*
感谢paxdiablo让我的树更具可读性。
这棵树有单词a，app，appeal，apple，ask，bead，bean，be和bee。标有星号的节点表示“如果我要停在这里，这将是一个有效的单词”，例如'be'下面的'e'下面的'e'。
当您找到一个您不知道的信件时，请使用通配符（即，选择所有孩子并递归所有路径）。
你说填字游戏，但是你的“字母......制作单词”似乎表明了拼字游戏。这对两者都有效。不是最快，但速度很快。
感谢Andreas提醒我们这被称为trie。
如果你想说“第二个字母是P”你将从根节点开始并取每个分支（这将是字母表中的每个字母，假设它是一个正确的字典），然后是“P”分支，然后去从那里开始。
我之前实际上写了一个填字游戏程序（含糊不清但构造背后的理论是相同的）。
我有一个单词及其线索的数据库，可以按使用的时间排序（这样我就不会在后续运行中获得重复的填字游戏）。
你要做的第一件事就是设计你的图案（黑色，你不能把字母和白色放在哪里）。在动态创建模式时尝试将单词插入网格中非常耗时并且容易出错。如果你看大多数填字游戏，他们往往会遵循某些规则，以使其更容易。就像在一条对角线周围对称并且不允许四个白色单元的正方形（以便于选择合适的单词的任务）之类的事情。
一旦你有了模式，那么你就开始找到要放在其中的单词。这样，您就会知道“app”是该单词的开头，并且能够将您的搜索限制为以“app”开头的搜索，而不是每个包含“app”的单词。类似地，对于您在任何位置已知字母的单词。在已知位置定位带字母的单词比在单词中的任何起始位置评估这些字母要容易得多。
我最终用shell脚本编写（信不信由你），并使用来自Linux的字典作为单词搜索工具。如果你知道你有一个以“app”开头的5个字母的单词，它很容易使用：
grep '^app..$' words.txt
获得所有有效可能性的列表。
并且，当找到每个单词时，它被复制到包含单词和多个可能线索的clues.txt文件中。实际的格式是使用{count，word，clue}，其中同一个单词可能存在于具有不同线索的多行上 - 这允许grep通过sort的管道，以便较少使用的单词/线索浮动到顶部（每当一个单词/使用线索，其计数增加，使其下次使用的可能性降低。
一旦该文件大小合适，程序将首先使用它来定位单词，并且只有在未找到单词的情况下，它才会恢复到需要手动干预的单词文件（无线索）。
它实际上最终做得很好。它的速度并不快，但我不需要每三秒生成一个 - 这是一个每周发送一次的社区通讯。
现在您已将问题更改为Scrabble变体，这实际上要困难得多。
你需要考虑你的信件，董事会上的信件以及你需要评估更多地方的事实。这使得暴力方法更加困难。
我作为初始剪切将做的是选择随机选择的可能性（棋盘上的起始位置和方向），然后使用与上面的填字游戏变体相同的算法来找到可以适合那里的所有单词。然后，如果您有满足该单词的字母，请将其（及其分数）存储在列表中。
请记住，您需要注意干扰电路板上的其他字样。
我将继续研究可能性，直到下列之一：
最后一个是重要的 - 如果你是初学者，你不想详尽地检查数百万种可能性。
然后，从列表中选择最佳移动（或者如果在初学者级别玩，则可能不是最佳移动 - 这完全取决于您希望计算机有多好）。
Steven A. Gordon撰写了一篇有趣的论文，探讨如何搜索可能的Scrabble（我猜）动作（参见Gordon's paper on GADDAG）。虽然在搜索动作和赢得Scrabble之间存在很大差距 - 正如文章所提到的 - 这与原始问题无关。
如果你发现最直接阅读一些代码是最有用的，那么有一个很好的开源播放器，Quackle。
大多数Scrabble论文都在谈论在整个董事会中搜索最佳单词。但是如上所述，要解决您的问题，有一个非常简单的算法。
首先，你知道你想要的单词包含'app'，你知道你可以制作的最大单词是七个字母长（板上已有3个字母，托盘中有4个字母）。因此，使用sql语句搜索数据库，例如：
从词典中选择单词LIKE'％app％'和len（word）<= 7
接下来，将所有七个字母放入一个数组{l，e，c，r，a，p，p}
从数据库中读取每个单词，一次一个。然后查看字典单词的每个字符，看它是否存在于数组中。如果在数组中找到字典单词的第一个字母，则删除数组中的该元素并继续下一个字典字母。
如果在数组中找不到任何字典单词字母，则该单词不符合条件，因此，继续下一个单词。
如果您已查看字典中的所有字母并且已在数组中找到所有字母，则该字符合格，因此您将其写入列表。
请注意，将切片放入数组的原因是，一旦将字典单词中的字母与数组中的切片匹配，就需要通过删除数组中的元素来删除该字母。
因此，例如，字典数据库返回单词“上诉”。前四个字母在数组中找到，这些元素被删除，只留下{l，c，r}在数组中。当你找到第五个字母'a'时你将找不到它，所以这个词被取消资格。
“apple”这个词将符合条件，将{c，r}留在你的数组中。
用任何语言编写代码都很容易。但是，这不是最快的方法。我自己在找一个更快的方式！
如果您正在尝试创建单词索引，以便您可以尝试“解决”（或创建）填字游戏，那么我猜您会从以长度索引的单词词典开始。然后你要创建另一个词典词典词典......第一个索引是按字总长度而第二个是长度，然后是字母位置，最后是字母（六个字母的单词，第二个字母是“i”） “ 例如）。
在构建此索引之后，您可以表达尝试根据对这些索引执行的集合操作来设置或解决难题的每个步骤。 （例如，以“w”开头并以“k”结尾的8个字母单词将是以“w”开头的所有8个字母单词的交集，以及以“k”结尾的所有单词的交集 - 这不出所料地包括“作业” “）。当然，构建了我描述的索引数据结构后，可以通过执行全局单词列表的线性扫描或甚至长度分离列表的线性扫描来实现对可能匹配的更有效搜索。
一旦你有了这个基本的数据结构，那么程序的其余部分可能是树生成和遍历（当然是回溯）。创建一个程序，生成所有可能性（使用所描述的数据结构），并且每当它“卡住”时，它都会回溯，直到找到新的可能性。
正如paxdiablo所暗示的那样，你必须为生成器包含一大堆“单词”才能有合理的机会创建一个完整的“解决方案”。任何对填字游戏有经验的人都意识到，他们允许设定者采取相当多的自由（例如频繁使用指南针点，古老的术语和诗意的合同），以便让自己成为现实中的驼峰。
我没有亲自写过填字游戏。我编写了密码求解器，它使用了类似但更简单的索引结构。 （为了找到zyzxw可能在密码中的每个单词，你将它“抽象”成一个模式：abacd。你的字典包含由其抽象索引的每个单词，你可以很容易地发现“每个”匹配“zyzxw”）。在那种情况下，在每个抽象开始的列表中的线性搜索相当快，即使你正在发现“uzz”和“zyzxw”确实可能是“例如”......。我还写了一个简单的“Jotto”游戏，它根本没有从索引中获益 - 在每个淘汰步骤中通过几千个或6个字母单词进行线性扫描，在我的旧版本中用了不到一秒的时间Mhz XT在现代PC计算的前期历史中）。
寻找由Brian Sheppard（Maven的作者）撰写的名为“迈向拼字游戏的完美游戏”的博士论文。它内容丰富，非常有趣。但也很长。
如果我正确地理解了这个问题（你开始提示字母，字的子字符串，并尝试重新排列字母以获得正确的单词），这是另一种解决方案：
你可以从倒退开始。你已经在字典中有了单词，需要显示单词的一部分（子字符串）和单词中的字母列表，以便人们可以安排它们。鉴于这一切，您可以从字典中的单词开始，并创建一个距离为1的编辑距离的图表。
例
从苹果开始，继续删除一封信。这是一个小图（我没有绘制所有边缘以减少混乱）：
apple -> appe -> ape -> ...
  \                   \
   \_-> appl -> app -> ...
删除该字母后，将其放在提示列表中。
提示：l，p
提示：l，e
当播放器使用列表中的字母组成原始单词时，您只接受正确的条目，这些条目是通向前一个父级的节点。您只需向后遍历图表即可找到原始单词。
例
如果单词是app和提示：l，p
如果用户给你l：appl你移动到应用程序的prev节点，即appl。
如果用户给你e：appe，你移动到app的prev节点，在这种情况下是适用的。
用户输入的任何其他字母，您可以通过保留在当前节点来禁用。
您正在寻找的是您的anagram解算器能够找到“通配符”字母，以查看它可以用其他字母制作的字词。我有一个我写的字谜解算器，它完成了这个问题。我发现要做到这一点的一件重要事情，以及解算器的速度，是预先确定你的单词表中每个单词的字母数和分数。
对于Instance您的表应该像这样构造
word | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | score
-------------------------------------------------------------------------------------------------------------
test | 0 | 0 | 0 | 0 | 1 | 0 | 0 | h | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 4
正如您所看到的那样，单词，字母以及它们包含的字母数量和单词的分数都有一个单独的列。我提前创建了一个单独的脚本，它只是为每个单词运行并为我填写它直到完成。
这是我编写的脚本，用于计算每个单词中的字母数以及分数并更新每条记录。在运行此脚本之前，必须先从一个只包含单词的表开始。一旦你运行它，你就完成了，除非你添加新单词，否则不必再运行它。
<?
include('/includes/connect.php');
$sql = "SELECT * FROM SOWPODS WHERE word LIKE 'z%' ORDER BY word ASC";
$result = mysql_query($sql);
while($row = mysql_fetch_array($result)) {
$string = $row['word'];
$rowwordid = $row['ID'];
echo $thisword = strtoupper($row['word']);
echo " - ";
for ($ii = 0; $ii < strlen($string); ++$ii) {
$thisletter = strtolower($string{$ii});
if ($thisletter == 'a') {
$a = $a+1;
} elseif ($thisletter == 'b') {
$b = $b+1;
} elseif ($thisletter == 'c') {
$c = $c+1;
} elseif ($thisletter == 'd') {
$d = $d+1;
} elseif ($thisletter == 'e') {
$e = $e+1;
} elseif ($thisletter == 'f') {
$f = $f+1;
} elseif ($thisletter == 'g') {
$g = $g+1;
} elseif ($thisletter == 'h') {
$h = $h+1;
} elseif ($thisletter == 'i') {
$i = $i+1;
} elseif ($thisletter == 'j') {
$j = $j+1;
} elseif ($thisletter == 'k') {
$k = $k+1;
} elseif ($thisletter == 'l') {
$l = $l+1;
} elseif ($thisletter == 'm') {
$m = $m+1;
} elseif ($thisletter == 'n') {
$n = $n+1;
} elseif ($thisletter == 'o') {
$o = $o+1;
} elseif ($thisletter == 'p') {
$p = $p+1;
} elseif ($thisletter == 'q') {
$q = $q+1;
} elseif ($thisletter == 'r') {
$r = $r+1;
} elseif ($thisletter == 's') {
$s = $s+1;
} elseif ($thisletter == 't') {
$t = $t+1;
} elseif ($thisletter == 'u') {
$u = $u+1;
} elseif ($thisletter == 'v') {
$v = $v+1;
} elseif ($thisletter == 'w') {
$w = $w+1;
} elseif ($thisletter == 'x') {
$x = $x+1;
} elseif ($thisletter == 'y') {
$y = $y+1;
} elseif ($thisletter == 'z') {
$z = $z+1;
}
}
$scorea = $a*1;
$scoreb = $b*4;
$scorec = $c*4;
$scored = $d*2;
$scoree = $e*1;
$scoref = $f*4;
$scoreg = $g*3;
$scoreh = $h*3;
$scorei = $i*1;
$scorej = $j*10;
$scorek = $k*5;
$scorel = $l*2;
$scorem = $m*4;
$scoren = $n*2;
$scoreo = $o*1;
$scorep = $p*4;
$scoreq = $q*10;
$scorer = $r*1;
$scores = $s*1;
$scoret = $t*1;
$scoreu = $u*2;
$scorev = $v*5;
$scorew = $w*4;
$scorex = $x*8;
$scorey = $y*3;
$scorez = $z*10;
$totalscore = $scorea + $scoreb + $scorec + $scored + $scoree + $scoref + $scoreg + $scoreh + $scorei + $scorej + $scorek + $scorel + $scorem + $scoren + $scoreo + $scorep + $scoreq + $scorer + $scores + $scoret + $scoreu + $scorev + $scorew + $scorex + $scorey + $scorez;
$SQL_update_count = "UPDATE TWL06 SET a = '$a', b = '$b', c = '$c', d = '$d', e = '$e', f = '$f', g = '$g', h = '$h', i = '$i', j = '$j', k = '$k', l = '$l', m = '$m', n= '$n', o = '$o', p = '$p', q = '$q', r = '$r', s = '$s', t = '$t', u = '$u', v = '$v', w = '$w', x = '$x', y = '$y', z = '$z', score = '$totalscore' WHERE ID = '$rowwordid'";
echo "<br>";
$result_update_count = mysql_query($SQL_update_count);
$a = 0;
$b = 0;
$c = 0;
$d = 0;
$e = 0;
$f = 0;
$g = 0;
$h = 0;
$i = 0;
$j = 0;
$k = 0;
$l = 0;
$m = 0;
$n = 0;
$o = 0;
$p = 0;
$q = 0;
$r = 0;
$s = 0;
$t = 0;
$u = 0;
$v = 0;
$w = 0;
$x = 0;
$y = 0;
$z = 0;
}
?>
完成后，您所要做的就是创建一个脚本，对列中的字母进行计数，并将其与您给出的字母进行匹配。你将不得不首先爆炸这些字母并找出你所拥有的每个字母的数量。然后运行一个sql语句，查找那些字母数量或更少。