65.9K
CodeProject 正在变化。 阅读更多。
Home

倒计时数字谜题求解器

DavidHancock
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (45投票s)

2014 年 3 月 10 日

CPOL

10分钟阅读

viewsIcon

90743

downloadIcon

3126

描述了一个用 c# 编写的解决 Countdown 数字谜题的算法。

Git 仓库：https://github.com/DHancock/Countdown

引言

Countdown 是英国 Channel 4 频道一档热门的日间电视游戏节目。其中一个游戏是数字谜题，参赛者选择 6 个数字，然后在 30 秒倒计时内用这些数字构建一个等于随机生成的目标值的等式。如果您没有看过这个节目，规则可以在这里找到

这个谜题非常适合用计算机来解决。它永远不会忘记已经用过的数字，并且总能找到那个显而易见的解决方案，它就在你眼前，但你就是看不到。

本文档介绍了我想出的算法。与大多数算法一样，诀窍在于快速地完成它。

用户界面

由于没有多人游戏功能和本地化用户界面，它尚未达到商业标准，但它提供了足够的功能来玩游戏和运行求解器。它可以用作训练辅助工具。

“选择”按钮生成牌面和目标值。

“启动/停止计时器”按钮控制一个 30 秒的计时器。

“求解”按钮启动 SolvingEngine。

求解引擎的工作原理

这使用了一种简单的暴力破解方法，即评估所有可能的等式。等式以后缀形式构建，这消除了对括号的需求，从而大大简化了问题。使用映射来定义后缀等式的构建方式。

模型的 Solve() 方法如下所示

public static SolverResults Solve(int[] tiles, int target)
{
    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();

    SolverResults results = new SolverResults();

    for (int k = 2; k <= tiles.Length; k++)
    {
        Combinations<int> combinations = new Combinations<int>(tiles, k);

        foreach (List<int> combination in combinations)
        {
            Permutations<int> permutations = new Permutations<int>(combination);

            Parallel.ForEach(permutations,
                            // the partitions local solver
                            () => new SolvingEngine(target, k),
                            // the parallel action
                            (permutation, loopState, solvingEngine) =>
                            {
                                solvingEngine.Solve(permutation);
                                return solvingEngine;
                            },
                            // local finally 
                            (solvingEngine) => results.AggregateData(solvingEngine));
        }
    }

    stopWatch.Stop();
    results.Elapsed = stopWatch.Elapsed;

    return results;
}

如您所见，它循环选择 6 张牌的连续 k 组合。对于每个组合，它计算其所有排列，对于每个排列，它在一个并行 foreach 循环中评估所有可能的后缀等式。每个并行分区都有自己的求解引擎。引擎的 Solve() 方法运行给定排列的引擎，遍历每个映射条目。

public void Solve(List<int> permutation)
{
    foreach (List<int> mapEntry in map)
        SolveRecursive(-1, mapEntry, 0, permutation, 0, 0);
}

求解引擎的 SolveRecursive() 方法是主要的“主力”。由于函数是手动内联的，代码相当冗长，因此我展示了等效的伪代码

SolveRecursive(recursion_depth)
{
    // get the stack for this recursion depth
    stack = stacks[recursion_depth] ;
 
    while (mapEntry > 0)   // push tiles onto the stack as per map
    {
        stack.push ;  
        --mapEntry ;
    }

    left_digit = stack.pop ;
    right_digit = stack.peek ;
 
    foreach (operator in {*, +, -, /})
    {
        result = evaluate (left_digit operator right_digit) ;
 
        if (there are more map entries)
        {
            // set up stack for next recursion
            next_stack = stacks[recursion_depth + 1]
            copy stack to next_stack 
            next_stack.poke = result ;
            
            SolveRecursive(recursion_depth + 1)
        }
        else
        {
            if (result == target)
            {
                record equation ;
                break ;
            }
 
            if (no targets found and result is close enough)
                record closest equation;
        }
    }
}

该方法实现了一系列操作：在执行运算符之前将零个或多个牌推入堆栈。然后它递归地执行另一个序列。每个递归调用都会获得当前堆栈的自己的副本，这样当递归展开时，调用者可以简单地继续执行下一个运算符。当映射完成时，递归结束。

虽然它在概念上是一个线性函数，但可以将其视为一棵树。每个序列分成 4 个分支，每个运算符一个，并且对于每个递归，每个分支进一步分成 4 个分支。这会重复，直到达到映射的末尾，此时获得 4 个运算符的最终结果。执行第一个等式后，后续等式通过仅执行一个运算符而不是完整的等式来评估。随着递归的展开，每个树节点都适用相同的原理。树结构和递归是一种美。

组合和排列

组合和排列集合类是使用常见模式实现的，其中类的枚举器按需提供下一个组合或排列。为了使代码可重用，我使用泛型编写了它们。

这两个类都使用 Donald Knuth 文档中记载的算法，按字典顺序生成数据。我认为我可以放心地假设它们是好的解决方案。排列算法实际上是 C++ 标准模板库函数 std::next_permutation() 的移植版本。

组合算法不会产生重复项。此外，我修改了算法，以过滤掉当源集合本身包含重复项时产生的重复组合。

后缀映射

后缀等式由重复的数字压入堆栈序列，然后执行运算符组成。所有等式都从压入 2 位数字开始，然后执行 0 或 1 个运算符，然后是另一个数字，然后是 0 到 2 个运算符等等。运算符的数量总是比数字少一个，并且等式总是以运算符结尾。

考虑 4 张牌的情况，将有 5 个映射子条目，每个可能的等式对应一个

在第一列中，O 表示等式中运算符的位置。代码生成第二列，即该位置运算符的计数。然后它将这些计数转换为映射条目，其中大于零的数字表示将该数量的数字压入堆栈，零表示应执行运算符。

那么有多少个等式呢？

它是每个 k 牌数对应的等式数之和。如果没有重复的牌，那么这很简单。

最后一项是运算符的乘积。所以我们有

这总共得到 33,665,400 个等式。请注意，k = 6 占总数的 92%。

然而，根据游戏规则，可以有一两对重复的牌。问题始于计算组合的数量。谷歌找到了这个 elegantly explained solution。当然，生成的一些组合也会包含重复项，这反过来又会影响排列的数量。我把这个问题留给了数学家，只是在代码中添加了一些工具。结果是

在实践中，由于游戏的非负整数算术规则，完全评估的等式数量将大大减少。如果一个等式违反了其中一个规则，它会在失败时立即被丢弃。

此外，我还丢弃任何执行恒等操作的等式，即除以或乘以一，因为它将是一个重复的等式。

我还通过检测运算符是否直接作用于牌值而不是任何中间派生值来过滤掉重复的等式。如果运算符是可交换的，即加法和乘法；如果左侧数字大于右侧，我将丢弃该等式。

最后一个过滤器是乘法是第一个被评估的运算符。如果等式完整且结果小于目标，则跳过其他运算符。

最终，将有多少等式被完全评估将取决于所选牌的值和目标。

对于典型的牌组和目标

求解器在戴尔 Inspiron 5578 上运行，配备 I7-7500 双核处理器 (2.7 GHz) 和 16 GB 内存，运行 Windows 10。请注意，计时是在通过键盘启动求解器时进行的。点击大约需要 20 毫秒，这可能是由于系统运行了额外的后台进程。

字母游戏

在 3.0 版本中，我添加了字母和谜语游戏。我一直打算这样做，但问题是找到合适的单词列表。然后我偶然发现了 SOWPODS 拼字游戏单词列表。这些单词列表不包含专有名词、带连字符的单词、拼写错误等。这非常好，因为检查 159,946 个单词的有效性并不是一个实际可行的建议。

为了实现游戏，我将单词列表预处理成一个包含字谜列表的字典。一旦变成字谜形式，单词中字母的顺序就不再重要，所以我使用字母的排序列表作为字典键。组合枚举器会生成按字典顺序排列的组合，因此要解决谜题，只需将用户选择的字母输入枚举器，并将其输出用作字典的键即可。

单词列表在解决方案中的一个单独项目中进行预处理。它读取单词列表文本文件，并使用 deflate 压缩将字谜列表写入一个压缩文本文件。此文件作为嵌入式资源构建到 Countdown 应用程序中。当应用程序在后台任务中启动时，它会转换回字典。我没有设置任何预/后构建步骤来将压缩文本文件复制到应用程序构建中，如果您使用自己的单词列表，您必须手动执行此操作。解决方案下载中包含一个压缩文本文件。

用户界面很简单

您可以键入字母或点击元音或辅音按钮。元音和辅音的选择频率可以在“设置”选项卡中编辑。要查看您的单词是否有效，您可以在列表上方的文本框中键入它。如果单词在列表中，则会显示一个绿色勾号，点击箭头按钮将选择它，展开其组并将其滚动到视图中。

我最初使用树视图控件来显示结果，但事实证明，要将列表框、列表视图和树视图控件全部样式化成相似的外观和感觉太困难了。最终，只使用列表视图控件来处理所有列表要容易得多。我喜欢树视图的扩展器，所以我相应地样式化了组标题。

谜语游戏

这只是字母游戏的一个子集，使用只有一种解决方案的 9 个字母的单词。选择按钮将始终生成一个有效的谜语。如果您输入字母，则只有在存在有效的单一解决方案时，“解决”按钮才会启用。

结论

这有什么意义吗？不，真的没有。这只是一个有趣的学术练习。

我曾打算使用 Xamarin 将 2.0 版本移植到 Android，但当我找到单词列表时，我的注意力被转移了。也许那将是我的下一个项目。

使用该应用程序查找比 Susie 更长的单词绝对是作弊。

历史

  • 3.2 - 字母游戏偶尔会因为无效字典键而返回不正确的单词。当读取单词列表资源时，如果缓冲区在读取一行过程中部分重新填充，并且该行包含多个字谜而不是单个单词，则可能会生成无效键。当使用提供的单词列表时，这影响了 131,781 个键中的 15 个，所以这不是一个常见的错误，但可以使用字母“AAEEILNRT”重现。已在 PR #4 中修复

  • 3.1 - Bug 修复。“字母”选项卡上的“选择”按钮未清除任何预先存在的错误。

  • 3.0 - 实现字母游戏。更新组合和排列枚举器以处理可为空类型。更新数字游戏求解器以使用并行 foreach 循环。将解决方案更新到 VS 2017。

  • 2.0 - 将 WinForms UI 替换为 WPF。将代码重构为 MVVM 设计模式。将解决方案更新到 VS 2015。将单元测试代码移至单元测试项目。重写单元测试并添加新的视图模型测试。

  • 1.3 - 修复 CodeProject 成员 WideBoyDixon 发现的 bug。求解引擎未能找到需要将两个相同值的牌相除的解决方案。

  • 1.2 - Channel 4 的 Countdown 团队友好地回复了我的电子邮件，确认目标范围从 101 而不是 100 开始，因此单个牌的解决方案是不可能的。

  • 1.1 - 将计时代码移出求解引擎，以便清楚地测量什么。完成测试代码中的异常处理。测试通过了，不幸的是，该领域被忽视了。各种小的代码重构。没有 bug 修复。

  • 1.0 - 初始发布

参考文献

Countdown 节目网站
http://www.channel4.com/programmes/countdown[^]

Countdown 百科全书式事实网站
http://www.thecountdownpage.com/index.htm[^]

后缀表达式，也称为逆波兰表示法
https://en.wikipedia.org/wiki/Reverse_Polish_notation[^]

组合和排列简介
http://www.mathsisfun.com/combinatorics/combinations-permutations.html[^]

Thomas Guest 编写的 C++ 中的算法 L
http://wordaligned.org/articles/next-permutation#tocimplementation[^]

Björn Edström 编写的 Python 中的算法 L
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html[^]

计算包含重复项的组合
http://mathforum.org/library/drmath/view/56197.html[^]

Adrian Akison 编写的使用 C# 泛型的排列、组合和变体
https://codeproject.org.cn/Articles/26050/Permutations-Combinations-and-Variations-using-C-G[^]

© . All rights reserved.