编写一个用于Scrabble的算法

Question

我正在处理类似填字游戏的问题，但我不知道如何设计算法。

举个例子：

• 字典里有像“car”、“apple”这样的单词。
• 板上给出了“app”这个单词。
• 还有一些字母，如“l”、“e”、“c”、“r”…可以用来组成单词。

因此，算法的任务是生成存储在字典中的正确单词。

app -> lapp -> leapp -> lecapp -> .... -> lappe -> eappc -> ... -> appl -> apple（正确答案）

什么是这个算法的最佳解决方案？

- teddy

Answer 1

你可能会对搜索Appel和Jacobson（1988）的研究论文“The World's Fastest Scrabble Program”感兴趣。算法是用伪代码概述的，因此需要一些工作来将其塑造成可用的形式，并将其粘合在一起;但是，作者概述的程序效果很好。

- allclaws

Answer 2

将您的字典存储为树状结构，例如：

          *
          |
     +----+----+
     |         |
     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。星号标记的节点表示“如果我停在这里，这将是一个有效的单词”，例如下面'b'下面的'e'表示'be'。

当你遇到不认识的字母时，请使用通配符（即选择所有子节点并递归下所有路径）。

你说的是填字游戏，但是你提到的“用于制作单词的字母”似乎表明了它也可以用于Scrabble。这对于任何一种情况都可以工作，虽然不是最快的，但已经足够快了。

感谢Andreas提醒我们这被称为trie树。

如果你想说“第二个字母是P”，你将从根节点开始沿着每个分支（假设它是一个正确的字典，其中包含整个字母表）走到“P”分支，然后再从那里继续向下寻找。

- Zwergner

---

你如何在对非主要字母有限制的情况下搜索该字典？例如，第二个字母必须是P？ - Kirk Broadhurst

这个被称为“trie”或前缀树。 - Andreas Brinck

Answer 3

我之前写过一个填字游戏程序（谜面式的，但构建原理相同）。

我有一个单词和线索的数据库，可以按使用次数排序（这样我就不会在后续运行中得到重复的填字游戏）。

你应该做的第一件事是设计你的模式（黑色代表不能放置字母的位置，白色代表可以）。在创建模式的同时尝试将单词适配到网格中非常耗时且容易出错。如果你看看大多数填字游戏，它们往往遵循某些规则以使其更容易。例如，围绕对角线对称并禁止四个白色单元格的正方形（以便选择合适的单词更容易）。

一旦你有了模式，然后开始寻找要放置的单词。这样，你就会知道“app”是单词的开头，并能够将搜索范围限制在以“app”开头的单词上，而不是每个含有“app”的单词。类似地，对于已知任意位置的字母的单词也是如此。查找已知位置的字母的单词比在单词的任何起始位置评估这些字母要容易得多。

我的程序最终是用shell脚本编写的（信不信由你），并使用来自Linux的字典作为单词搜索工具。如果你知道有一个以“app”开头的5个字母的单词，那么使用它就非常容易：

grep '^app..$' words.txt

获取所有有效可能性的列表。

当找到每个单词时，它都会被复制到一个clues.txt文件中，该文件包含单词和多个可能的线索。实际格式为使用 {count, word, clue}，其中相同的单词可能存在于多行中，具有不同的线索 - 这允许通过sort对grep进行管道处理，以便较少使用的单词/线索浮现到顶部（每当使用单词/线索时，其计数就会增加，使其下次使用的可能性较小）。

一旦该文件大小适中，程序将首先使用它来定位单词，仅在找不到单词时才会回到不带线索的单词文件，这需要手动干预。

实际上，它非常擅长完成工作。它并不是极快的，但我不需要每三秒生成一个 - 这是为每周发送一次的社区通讯而设计的。

---

现在你把问题改成了Scrabble变体，那实际上更难。

您需要考虑您拥有的字母、棋盘上的字母以及您必须评估的位置更多。这使得暴力方法更加困难。

作为初始剪切，我会随机选择可能性（棋盘上的起始位置和方向），然后使用与上面的填字游戏变体相同的算法来定位所有适合该位置的单词。然后，如果您有满足该单词的字母，请将其（以及其分数）存储在列表中。

请记住，您需要注意不要干扰棋盘上的其他单词。

我会继续检查可能性，直到以下情况之一：

• 您的列表足够大以供选择。
• 你时间用完了。
• 您已经检查了足够多的可能性以满足您的能力水平。

最后一个很重要 - 如果您正在与初学者玩耍，您不希望详尽地检查数百万种可能性。

然后，从您的列表中选择最佳移动（或者如果在初学者级别下进行比赛，则可能不是最佳移动 - 这完全取决于您希望计算机表现得有多好）。

- paxdiablo

Answer 4

史蒂文·A·戈登写了一篇关于如何搜索可能的Scrabble(tm，我猜)走法的有趣论文（请参见戈登关于GADDAG的论文）。虽然这篇论文提到了搜索走法和在Scrabble中获胜之间存在很大差距，但这与原始问题无关。

如果您觉得直接阅读一些代码最有用，那么有一个很好的开源播放器Quackle。

- James Youngman

Answer 5

大部分的Scrabble文件讨论了在整个游戏板上搜索最佳单词来打。但为了解决你所说的问题，这里有一个非常简单的算法。

首先，你知道你想要包含'app'的单词，并且你知道你可以制作的最长单词长度为7个字母（板子上已经有3个字母，托盘里有4个）。因此，使用如下SQL语句在你的数据库中进行查询：

Select word from dictionary where word LIKE '%app%' and len(word) <= 7

接着，将所有七个字母放入一个数组{l,e,c,r,a,p,p}

从数据库中逐个读取每个单词。然后查看词典单词中的每个字符，看它是否存在于数组中。如果找到了词典单词的第一个字母，则删除该数组元素并继续查看下一个词典字母。

如果在数组中找不到任何一个词典单词字母，则该单词不符合条件，因此继续查看下一个单词。

如果你已经查看了词典中的所有字母，并且所有字母都存在于数组中，则该单词符合条件，因此将其写入列表中。

请注意，将您的瓷砖放入数组中的原因是一旦您将字典单词中的字母与数组中的瓷砖匹配，您将需要通过删除该数组元素来从进一步考虑中删除该字母。

例如，字典数据库返回单词“appeal”。前四个字母在您的数组中找到，并删除这些元素，只剩下{ l，c，r }在数组中。当您寻找第五个字母“a”时，您将找不到它，因此该单词被取消资格。

单词“apple”将符合条件，留下{ c，r }在您的数组中。

用任何语言编写这很容易。但是，这不是最快的方法。我自己正在寻找更快的方法！

- Mike

Answer 6

如果您想创建一个单词索引，以便尝试“解决”（或创建）填字游戏，那么我想您会从按长度索引的单词字典开始。然后，您将创建另一个字典的字典...第一个索引是按总单词长度排序，第二个索引是按长度、按字母位置和最后按字母排序（例如具有第二个字母“i”的六个字母单词）。

在构建此索引之后，您可以使用这些索引上执行的集合操作来表示尝试设置或解决谜题的每个步骤。（例如，以“w”开头并以“k”结尾的8个字母单词将是所有以“w”开头且以“k”结尾的8个字母单词的交集---其中包括“homework”，这并不令人意外）。当然，构建我描述的索引数据结构允许更高效率地搜索可能的匹配项，而这比仅对全局单词列表或甚至长度分离列表执行线性扫描要容易得多。

一旦您拥有了这个基本的数据结构，那么程序的其余部分将可能是树形生成和遍历（当然包括回溯）。创建一个程序，它使用所述的数据结构生成每个可能性，并且每当它“卡住”时，就让它回溯，直到找到新的可能性。

正如paxdiablo所暗示的那样，您必须包含大量的“单词”才能使生成器有合理的机会创建完成的“解决方案”。任何有经验的填字游戏玩家都知道，他们允许出题人采取相当多的自由（例如频繁使用罗盘点、古语和诗意缩写）以便让自己跨过难关。

我个人没有编写填字游戏生成器。我编写了使用类似但简单得多的索引结构的密码游戏求解器。（为了找到每个单词，zyzxw可以在密码游戏中被“抽象”成一个模式：abacd。您的字典包含每个按其抽象索引的单词，您可以轻松地发现“每个”匹配“zyzxw”）。在这种情况下，通过每个抽象开始的列表的线性搜索即使在您正在进行相关性分析以发现“uvz”与“zyzxw”确实可以是“the”时也是相当快的...例如）。我还编写了一个简单的“Jotto”游戏，它根本不需要索引---在线性扫描每个淘汰步骤中的几千个5或6个字母的单词时，在现代PC计算机的前历史时期，即使在我的旧6 Mhz XT上也不需要花费太多时间。

- Jim Dennis

Answer 7

寻找Brian Sheppard（Maven的作者）的博士论文《Towards Perfect Play of Scrabble》。它非常有启发性和趣味性，但也非常冗长。

- Fantius

Answer 8

如果我正确理解了问题（您从提示字母开始，一个单词的子字符串，并尝试重新排列字母以获得正确的单词），这里是另一种解决方案：

您可以从后往前开始。您已经拥有字典中的单词，并且需要显示单词的一部分（子字符串）和单词中的字母列表，以便人们可以将它们排列。在所有这些条件下，您从字典中的单词开始，并创建一个距离1个编辑的单词图。

例如：从“apple”开始，不断删除一个字母。这里是一个小图（为了减少混乱，我没有绘制所有边缘）：

apple -> appe -> ape -> ... \ \ \_-> appl -> app -> ...

当您删除字母时，将其放入提示列表中。

提示：l，p 提示：l，e

当玩家使用列表中的字母组成原始单词时，您只接受正确的条目，这些条目是导致先前父节点的节点。您只需向后遍历图形以找到原始单词。

示例

如果单词是app和提示：l，p

如果用户给出l：appl，则移动到app的上一个节点，即appl。

如果用户给出e：appe，则移动到app的上一个节点，即在此情况下为appe。

用户输入的任何其他字母都会使您保留在当前节点并拒绝该字母。

- Adrian

Answer 9

在某个回合中得分最高的走法，不一定是获胜的走法。有时候最好的走法是阻止对手的行动。这取决于它是否是袋子里的隐藏字母，如果是，则会改变策略。

如果知道袋子里的内容，就可以轻松计算出对手的托盘。然后最好的走法是使你相对于对手的下一个走法获得最多的净分数。

现在假设对手的托盘无法推断出来，因为袋子是隐藏的。尽管如此，袋子和对手托盘的字母组合是已知的。因此，可以统计确定对手托盘中最可能的字母。然后进行分析非常昂贵，需要扫描巨大的空间以获取每个点数和概率，以便确定最佳走法。

Scrabble 在某些形式上具有随机性和不完全信息，使得最佳走法成为一个统计问题。这与国际象棋不同，国际象棋没有随机性或隐藏信息存在，理论上的最佳走法仅基于演绎推理，即使计算机远远没有足够的强大来精确解决它。

- Gregory Morse

Answer 10

你所需要的是让你的字谜求解器具有找到“通配符”字母的能力，以查看它可以使用附加字母制作哪些其他单词。我编写了一个可以做到这一点的字谜求解器。我发现制作这个求解器的一个重要事项是预定义单词表中每个单词的字母数和得分，从而提高求解器的速度。

例如，您的表应该结构化如下：

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 语句来查找那些数量小于或等于这些字母的数量。

- Cesar Bielich