1

首先 - 是的，这是一个家庭作业 - 但它主要是一个理论问题，而不是一个实际问题，我只是要求确认我是否正确思考或任何提示，如果我不正确。

我被要求编译一个简单的 Sudoku 求解器（在Prolog上，但现在并不那么重要），唯一的限制是它必须使用使用Best-First Algorithm的启发式函数。我能想出的唯一启发式函数解释如下：

1. Select an empty cell. 
  1a. If there are no empty cells and there is a solution return solution.
      Else return No.
2. Find all possible values it can hold. %% It can't take values currently assigned to cells on the same line/column/box.
3. Set to all those values a heuristic number starting from 1.
4. Pick the value whose heuristic number is the lowest && you haven't checked yet.
   4a. If there are no more values return no.
5. If a solution is not found: GoTo 1.
   Else Return Solution.

// I am sorry for errors in this "pseudo code." If you want any clarification let me know.

那么我这样做是对的还是有其他方法而我的方法是错误的？提前致谢。

4

3 回答 3

1

我会使用的启发式是这样的：

  1. 反复查找只能插入一个可能数字的任何空格。用适合的数字填写它们1-9。
  2. 如果每个空白空间都有两种或多种可能性，则将游戏状态压入堆栈，然后选择一个随机方块填充随机值。
  3. 转到步骤 1。

如果你设法填满每一个方格，你就找到了一个有效的解决方案。

如果你到了没有有效选项的地步，将最后一个游戏状态从堆栈中弹出（即回溯到你最后一次随机选择的时间。）做出不同的选择，然后再试一次。

作为一个有趣的旁注，您被告知使用贪婪启发式方法来执行此操作，但数独实际上可以简化为布尔可满足性问题（SAT 问题）并使用通用 SAT 求解器解决。这非常优雅，实际上可以比启发式方法更快。

于 2012-04-13T01:25:47.710 回答
1

当我自己在 Prolog 中编写数独求解器时，我使用的算法如下：

  1. 过滤掉已经解决的单元格（即开始时的给定值）
  2. 对于每个单元格，构建一个包含其所有邻居（即 20 个单元格）的列表。
  3. 对于每个单元格，构建一个包含它可以采用的所有可能值的列表（完成上述操作后很容易做到）
  4. 在包含所有要求解的单元格的列表中，将可用值最少的单元格放在顶部
  5. 如果顶部单元格剩余的可能性为 0，则转到 7，否则，转到 6，如果列表为空，则您有解决方案。
  6. 对于列表顶部的单元格：在单元格的可能值中选择一个随机数。在其邻居的所有可能值中删除此值。转到 5。
  7. 回溯（即在 Prolog 中失败）

该算法总是首先对“解决最多的”单元进行排序，并尽早检测到故障。与求解随机单元的算法相比，它大大减少了求解时间。

于 2012-04-13T11:04:32.707 回答
1

你所描述的是最受约束的变量启发式。它选择具有最少可能性的单元格，然后从该单元格开始深度递归分支。这种启发式算法在深度优先搜索算法中的速度非常快，因为它可以在靠近根的早期检测到碰撞，而搜索树仍然很小。

这是 C# 中最受约束变量启发式的实现：练习 #2：数独求解器

这篇文章还包含了这个算法对数独单元的访问总数的分析——它非常小。看起来启发式算法在第一次尝试中就解决了数独问题。

于 2013-07-17T14:42:20.947 回答