19

我正在构建一个用 Javascript 编写的有趣的数独游戏。
一切正常，每次都使用一个解决方案完全生成电路板。

我唯一的问题是，这使我无法将我的项目公开发布的
原因是我不知道如何对我的电路板进行难度等级评分。我到处都看过，
在论坛上发帖等等。我不想自己编写算法，这不是这个项目的重点，
而且，它们对我来说太复杂了，因为我不是数学家。

我唯一接近的是这个通过 JS 进行评分的网站，
但问题是，代码是以如此糟糕的无证、非常临时的方式编写的，
因此不能借用......

我会说到点子上——
谁能指点我一个提供数独分级/评级源代码的地方？

谢谢

22.6.11 更新：
这是我的数独游戏，我已经实现了自己的评分系统，它依赖
于基本的人类逻辑解决技术，所以检查一下。

4

6 回答 6

5

我自己考虑过这个问题，我能做的最好的就是通过实际解决它并分析游戏树来确定这个难题的难度。

最初：使用“人类规则”实现您的求解器，而不是使用人类玩家不太可能使用的算法。（这本身就是一个有趣的问题。）根据人类使用的难度为求解器中的每个逻辑规则评分。使用数百个或更大的值，以便您可以自由调整相对于彼此的分数。

解决难题。在每个位置：

  • 枚举所有可以在当前游戏位置逻辑推导出的新单元格。
  • 每个扣除的分数（完全解决一个单元格）是足以进行该扣除的最简单规则的分数。
  • 编辑：如果必须同时应用多个规则或多次应用一个规则以进行单个扣除，则将其作为单个“复合”规则应用程序进行跟踪。为了给一个化合物打分，也许使用单个规则应用程序的最小数量来解决一个单元格乘以每个单元格的分数之和。（此类扣除需要相当多的脑力劳动。）根据您的规则集，计算应用程序的最小数量可能是 CPU 密集型工作。在继续探索该位置之前，应回滚任何完全解决一个或多个单元格的规则应用程序。
  • 排除所有扣除中分数高于最低值的所有扣除。（这里的逻辑是玩家不会感知更难的，而是感知到更容易的并接受它；而且，这有望从决策过程中剔除大量计算。）
  • 当前位置的最低分数除以“最简单”的扣分数（如果有很多，找到一个更容易）就是该位置的难度。因此，如果规则 A 是最容易适用的规则，得分为 20，并且可以在 4 个单元格中应用，则该位置的得分为 5。
  • 随机选择一个“最简单”的扣法作为您的游戏，然后进入下一个游戏位置。我建议只为下一个位置保留完全解决的单元格，不传递其他状态。这当然会浪费 CPU，重复已经完成的计算，但目标是模拟人类游戏。

谜题的整体难度是您通过游戏树的路径中的位置得分的总和。

编辑：替代位置分数：不是使用更难的规则完全排除扣除，而是计算每个规则（或复合应用程序）的总体难度并选择最小值。（这里的逻辑是，如果规则 A 得分为 50，规则 B 得分为 400，并且规则 A 可以在一个单元格中应用，而规则 B 可以在十个单元格中应用，那么位置得分为 40，因为玩家更有可能找出十个更难的游戏之一，而不是一个更容易的游戏。但这需要你计算所有可能性。）

编辑： Briguy37 建议的替代方案：在位置分数中包含所有扣除项。对每个位置进行评分，1 / (1/d1 + 1/d2 + ...)其中d1、d2等是个人扣除项。（这基本上计算了给定个人“扣除阻力”等位置的“任何扣除阻力” d1。d2但这需要您计算所有可能性。）

希望这个评分策略会产生一个随着你对难度的主观评估增加而增加的谜题指标。如果没有，那么调整规则的分数（或您从上述选项中选择的启发式方法）可能会实现所需的相关性。一旦你在分数和主观体验之间取得了一致的相关性，你应该能够判断“容易”、“困难”等的数字阈值应该是多少。然后你就完成了！

于 2011-05-25T16:54:39.203 回答
4

Donald Knuth 研究了这个问题并提出了解决数独的Dancing Links 算法，然后对它们的难度进行评级。

谷歌周围，有几个 Dancing Links 引擎的实现。

于 2011-05-25T17:03:36.840 回答
2

也许您可以对拼图的一般“约束”进行评分？考虑一个新的谜题（只有提示）可能有一定数量的单元格，这些单元格可以简单地通过消除它不能包含的值来确定。我们可以说这些单元格被“限制”到比典型单元格更少的可能值，并且存在的高度受限的单元格越多，人们可以在不猜测的情况下在拼图上取得更多进展。（这里我们认为“猜测”的要求是使难题变得困难的原因。）

然而，在某些时候，玩家必须开始猜测，同样，单元格的约束很重要，因为对于给定单元格选择的值越少，就越容易找到正确的值（并增加其他单元格的约束）。

当然，我实际上并不玩数独（我只是喜欢为它编写游戏和求解器），所以我不知道这是否是一个有效的指标，只是大声思考=）

于 2011-05-25T16:39:27.050 回答
2

我有一个简单的求解器，它只在行、列和正方形中寻找唯一的可能性。当它解决了可以通过这种方法解决的少数单元格时，它会选择剩余的候选者进行尝试，并查看简单的求解器是否会导致解决方案或没有可能性的单元格。在第一种情况下，难题被解决了，在第二种情况下，一种可能性被证明是不可行的，因此被消除了。在第三种情况下，既没有最终解决方案，也没有不可行的情况，因此无法得出任何推论。

循环执行此过程的主要结果是消除可能性，直到选择正确的单元格条目导致解决方案。到目前为止，这个程序已经成功地解决了最难的难题。它通过多种解决方案轻松解决难题。如果随机选择试验候选者，它将生成所有可能的解决方案。

然后，我根据在简单求解器找到解决方案之前必须消除的非法候选者的数量来生成难题的难度。

我知道这就像猜测，但如果简单的逻辑可以消除一个可能的候选者，那么更接近最终的解决方案。

麦克风

于 2012-11-24T21:46:42.033 回答
1

我过去做过这件事。

关键是您必须从人类逻辑的角度弄清楚要使用哪些规则。您提供的示例详细说明了许多不同的人类逻辑模式作为右侧的列表。

您实际上需要使用这些规则而不是计算机规则来解决难题（使用简单的模式替换可以在几毫秒内解决它）。每次更换棋盘时，您都可以从“最简单”的模式（例如，单元格或行中的单个打开的框）重新开始，然后沿着链向下移动，直到找到下一个要使用的逻辑“规则”。

在对数独进行评分时，会为每种方法分配一些点值，您可以为需要填写的每个字段加起来。虽然“单个空单元格”可能会得到 0，但“XY 链”可能会得到 100。您将所有需要的方法（和频率）制成表格，最后得到最终的权重。有很多地方列出了这些权重的预期值，但它们都是相当经验性的。您正在尝试对人类逻辑进行建模，因此请随意提出自己的权重或增强系统（如果您真的只使用 XY 链，那么这个难题可能比它需要更高级的机制更容易）。

您可能还会发现，即使您有一个独特的数独，它也无法通过人类逻辑解决。

还要注意，这比以标准的、模式化的方式解决它要占用更多的 CPU 资源。几年前，当我编写代码时，需要花费数秒（我完全忘记了，但甚至可能长达 15 秒）来解决我创建的一些生成的谜题。

于 2011-05-25T16:51:19.187 回答
0

假设难度与用户解决难题所需的时间成正比，这里有一个人工智能解决方案，它随着时间的推移接近理想算法的结果。

  1. 随机生成固定数量的起始拼图布局，例如 100 个。
  2. 最初，提供一个随机难度部分，让用户从可用布局中玩随机谜题。
  3. 为每个用户保留一个平均随机求解时间。我可能会为此制作前 10 名/前 X 名排行榜，以激发对玩随机谜题的兴趣。
  4. 为每个拼图解决方案保留一个平均解决时间乘数（如果用户通常在 5 分钟内解决拼图并在 20 分钟内解决，则拼图平均解决时间乘数应计算为 4）
  5. 一旦一个谜题玩了足够多的次数以获得该谜题的基本难度，比如 5 次，将该谜题添加到您的评分谜题列表中，并将另一个随机生成的谜题添加到您可用的谜题布局中。
    注意： 您应该将第一个谜题保留在随机谜题列表中，以便获得更好的统计数据。
  6. 一旦你有足够的基础级谜题，比如 50 个，就允许用户访问你的应用程序的“额定难度”部分。每个谜题的难度将是该谜题的平均时间乘数。
    注意： 当用户选择玩具有额定难度的谜题时，这不应该影响平均随机解题时间或平均解题时间乘数，除非你想计算加权平均值（否则如果用户玩了很多更难的谜题，他们的平均值时间和时间乘数会出现偏差）。

使用上面的方法，一个解决方案的评分从 0（已经解决/没有时间解决）到 1（用户可能会在他们的平均时间内解决这个难题）到 2（用户可能需要两倍的时间来解决这个难题）他们的平均时间）到无穷大（用户将永远寻找这个难题的解决方案）。

于 2011-05-25T17:32:37.803 回答