我正在研究一个类似纵横字谜的问题，但我不知道如何设计算法。编写一个拼字游戏的算法
例如：
所以算法的任务是制作存储在字典中的正确单词。
应用程序 - >拉普 - > leapp - > lecapp - > ... - > lappe - > eappc - > - >申请 - >苹果（正确答案）
什么是最好的解决办法对于这个算法？
存储你的字典为一棵树，例如：
*
|
+----+----+
| |
A* B
| |
+--+--+ E*
| | |
P S +-+-+
| | | |
P* K* A E*
| |
+-+-+ +-+-+
| | | |
E L D* N*
| |
A E*
|
L*
感谢paxdiablo让我的树更具可读性。
这棵树有单词a，app，诉求，苹果，问，珠子，豆子，be和蜜蜂。标有星号的节点表示“如果我要在这里停下来，这将是一个有效的单词”，例如'be'的'b'下面的'e'。
当您发现一封不认识的信件时，请使用通配符（即，选取所有的孩子并缓解所有路径）。
你说纵横字谜，但那么你的“用于制造单词的字母”似乎指示拼字游戏。这对两者都有效。不是最快的，但速度很快。
感谢Andreas提醒我们，这叫做trie。
如果你想说“第二个字母是P”，你可以从根节点开始，并取每个分支（这将是字母表中的每个字母，假设它是一个合适的字典），然后“P”分支，然后从那里继续。
我已经写了一个填字游戏程序之前（神秘但建设背后的理论是相同的）。
我有一个数据库的单词和他们的线索可以按使用次数排序（这样我就不会倾向于在随后的运行中得到重复的填字游戏）。
你应该做的第一件事是设计你的模式（黑人，你不能把字母和白人放在你可以的地方）。尝试在飞行中创建模式时将单词合并到网格中非常耗时并且容易出错。如果你看大多数填字游戏，他们往往遵循一定的规则，以使其更容易。像对角线周围对称并且禁止四个白色方格（减轻选择合适词语的任务）的事情。
一旦你有了模式，然后你开始寻找单词来放置它。这样，您就会知道“应用”是该词的开头，并且能够将您的搜索限制为以“app”开头的搜索，而不是每个带有“app”的词。对于在任何位置已知字母的单词也是如此。使用字母在已知位置处查找单词比在单词内的任何起始位置评估这些字母要容易得多。
我最终被编写在shell脚本中（不管你信不信），并使用来自Linux的字典作为单词搜索工具。如果你知道你必须以“app”一个5个字母的单词，这是很容易使用：
grep '^app..$' words.txt
得到的所有有效的可能性列表。
而且，找到每个单词后，它被复制到包含单词和多个可能线索的clues.txt文件中。实际的格式是{count，word，clue}，其中相同的单词可能存在于多条线上，并且有不同的线索 - 这允许管道编号为grep到sort，以便较少使用的单词/线索浮动到顶部（每当一个单词/线索被使用了，它的计数增加了，下次使用它的可能性就降低了）。
一旦该文件尺寸合适，程序将首先使用它来定位单词，并且只有在找不到单词时才会恢复为需要手动干预的单词文件（无线索）。
它实际上最终做得很好。虽然速度并不快，但我不需要每三秒产生一次 - 这是为了每周发送一次社区时事通讯。
既然您已经将问题更改为拼字游戏变体，那实际上要困难得多。
你需要考虑到你有的字母，董事会的信件和事实上有更多的地方，你必须评估。这使得暴力方法更加困难。
作为初始剪辑，我会做的是选择随机选择的可能性（开始位置和方向），然后使用与上述填字游戏变体相同的算法来找到所有适合的词。然后，如果您有满足该单词的字母，请将它（连同其分数）存储在列表中。
请记住，您需要注意干扰板上的其他词语。
我会继续研究的可能性，直到一个：
最后一个很重要 - 如果你在玩初学者，你不想详尽地检查数以百万计的可能性。
然后，从你的列表中选择最好的移动（或者如果在初学者级别玩 - 也许不是最好的 - 这一切都取决于你想要电脑有多好）。
如果你想创建一个词的索引，以便你可以尝试“解决”（或创建）填字游戏，那么我想你会开始使用按词长度索引的单词词典。然后，你会创建另一个字典字典词典...第一个索引是全部字长，而第二个索引是长度，然后是字母位置，最后是字母（例如，带有第二个字母“i”的六个字母的单词）。
建立此索引后，您可以表达每个步骤尝试设置或解决在这些上执行的集合操作的难题。 （例如，以“w”开头并以“k”结尾的8个字母的单词将是以“w”开头的所有8个字母单词和以“k”结尾的所有单词的交集---其中，不出意外地将“家庭作业“）。当然，构建我所描述的索引数据结构允许对可能的匹配进行更有效的搜索，然后通过执行全局词列表的线性扫描或者甚至对长度分隔的列表进行线性扫描）。一旦你有了这个基本的数据结构，那么程序的其余部分可能会成为树的生成和遍历（当然还有回溯）。创建一个能够产生所有可能性的程序（使用所描述的数据结构），并且每当它“卡住”时，都会回溯到找到新的可能性。
正如paxdiablo所暗示的那样，您必须包含大量“单词”才能让发电机有合理的机会创建完整的“解决方案”。任何对填字游戏有经验的人都会意识到，他们允许二传手采取相当多的自由行为（例如频繁使用指南针点，古老术语和诗意合同），以便让自己变得像过去一样高兴。
我还没有亲自写过一个字谜发生器。我已经编写了密码解算器，它使用了一个类似的，但更简单的索引结构。 （要找到zyzxw在密码中可能出现的每个单词，请将其“抽象”为一个模式：abacd。您的字典包含通过其抽象索引的每个单词，并且您可以轻松地找到“every”匹配“zyzxw”）。在这种情况下，即使在关联发现具有“zyzxw”的“uvz”实际上可能是“the”...）时，在每个抽象中开始对列表进行线性搜索也是相当快的。我还写了一个简单的“Jotto”游戏，它不会从索引中受益 - 在每个消除步骤中通过几千个5或6个字母的单词进行线性扫描，在我以前的6个步骤中所用的时间不到一秒钟Mhz XT在现代个人电脑计算的历史中）。
Appel and Jacobson（1988）您可能会感兴趣在谷歌搜索"The World's Fastest Scrabble Program"。算法在伪代码中概述，因此需要一些工作来将其转换为可用的形式并将它们粘合在一起;然而，作者概述的程序很好。
Steven A. Gordon写了一篇关于如何搜索可能的拼字游戏（tm I guess）动作的有趣论文（参见Gordon's paper on GADDAG）。虽然在拼字游戏中寻找动作和获胜之间存在很大差距 - 正如文中提到的 - 这与原始问题无关。
如果你发现它最有用的只是直接阅读一些代码，有一个很好的开源播放器， Quackle。
寻找由Brian Sheppard（Maven的作者）撰写的名为“Towards Perfect Play of Scrabble”的博士论文。它的内容丰富，非常有趣。但也很长。
大部分的拼字游戏文件都是关于搜索整个棋盘上最好的单词。但要解决你的问题，如上所述，有一个非常简单的算法。
首先，你知道你想要的单词包含'app'，并且你知道你可以制作的最大单词是七个字母（板上已经有3个字母，而你的托盘上有4个字母）。所以，用一个SQL语句，如搜索数据库：
从字典那里字LIKE“％的应用％”和len（字）< = 7
接下来，把所有七封信到一个数组中，选择字{ l，e，c，r，a，p，p}
从数据库中逐个读取每个单词。然后查看字典单词的每个字符并查看它是否存在于数组中。如果在数组中找到字典单词的第一个字母，则删除数组中的该单元并转到下一个字典字母。
如果在该数组中找不到字典单词字母，则该单词不符合条件，因此请继续阅读下一个单词。
如果您查看了字典中的所有字母，并且在数组中找到了所有字母，则该字符合该字词，因此您将其写入列表中。
请注意，将磁贴放入数组的原因是，一旦将字典单词中的字母与数组中的磁贴相匹配，您需要从进一步考虑中删除该字母，方法是删除该元素在数组中。
因此，例如，字典数据库返回单词'上诉'。前四个字母在您的数组中找到，并且这些元素被删除，只剩下{l，c，r}在数组中。当你寻找第五个字母'a'时，你不会找到它，所以这个词是不合格的。
单词'apple'将符合条件，将{c，r}留在您的数组中。
用任何语言编码都很容易。但是，这不是最快的方法。我正在寻找更快的方式！
如果我理解正确的问题（你启动W¯¯提示字母，单词的子串，并尝试重新排列字母得到一个正确的字）这里是另一种解决方案：
您可以倒退开始。 您已经拥有词典中的单词，需要显示词的一部分（子字符串）和单词中的字母列表，以便人们可以排列它们。考虑到所有这些，您可以从字典中的单词开始，创建一个距编辑距离1的单词图。
例
开始苹果并保持移除了一封信。这里是一个小图（对此我没有画所有边缘，以减少混乱）：
苹果 - > APPE - >猿 - > ...
＆NBSP \＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP＆NBSP \
＆NBSP＆NBSP \ _ - > appl - > app - > ...
当您删除该字母时，将它放在提示列表中。
提示：L，P
提示：L，E
当玩家使用字母从列表中形成的原词，你只接受正确的项，其是导致节点到以前的家长。你只需向后遍历图表即可找到原始单词。
例
如果单词应用和提示：L，P
如果用户给出你升：申请您移动到应用程序的先前节点是 appl。
如果用户给你e：你移动到应用程序的prev节点，这里是 在这种情况下。
用户输入的任何其他字母，您通过保留在当前节点而不允许输入。
你在找什么是你的字谜求解器能够找到“通配符”字母来查看它可以用额外的字母做什么字。我有一个我写的anagram求解器，它确实做了这件事。我发现的一个重要的事情，也是解决者的速度，是预先定义你的单词表中每个单词的字母数和得分。
比如你表必须这样
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语句来查找这些字母或更少的字符。
您如何搜索本字典，对非主要字母进行限制？例如第二个字母必须是P？ – 2010-03-23 09:26:44
这被称为“trie”或前缀树。 – 2010-03-23 09:37:21