6

我做了一个算法来生成数独，但它的效率非常低。每个谜题都需要几分钟才能生成。所以现在我正在尝试以最佳方式再次编写它。但是我遇到了一些需要帮助的问题。

有两种方法：

  1. 从空白网格开始并添加数字，然后检查它是否可以解决。
  2. 创建包含所有 81 个数字的完整有效网格，然后删除，直到我们对剩余数字的数量感到满意并且它仍然可以解决。

首先我使用第一种方法，但现在我将使用第二种方法，因为我认为它更有效（我们从保证可解决的有效难题开始）。我是对的，第二种方法更好？

当我试图生成完整的填充网格时，我遇到了困难。我的算法是：

  • 为每个单元格设置候选者。最初它们是数字 1 到 9。
  • 选择没有值的随机单元格。
  • 从该单元格中选择随机候选并将其分配为单元格值。其他候选人被丢弃。
  • 现在对于与分配的单元格对应的每一行、单元格和正方形，我从这些候选者中删除单元格的值，因此每个数字在行/列/正方形中都是唯一的
  • 重复

这种技术保证随机网格没有重复的数字。然而，大多数时候，当我不违反任何放置规则时，就会发生冲突——比如所有候选人都被删除的空单元格等，我需要重新开始。有没有更优雅/有效的方法来用数字填充整个网格而不破坏放置规则和仍然是随机数？

4

4 回答 4

8

你看过现有的算法和/或代码吗？

查看http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf以获得算法描述，以及 Peter Norvig 在http://norvig.com/sudoku.html上的文章。

Python中有一些实现。到目前为止，我从未见过已发布的 C# 解决方案。

祝你好运！

于 2012-02-15T15:00:51.350 回答
0

如果您正在查看一些现有的算法，那么有 ac# 项目。这实际上来自与 Peter Norvig 相同的解决方案。在此处阅读有关它的更多信息

希望这会有所帮助！

于 2012-02-15T15:10:22.030 回答
0

我使用编程来删除与最后一个条目冲突的所有先前条目。使用这种方法，我可以输入一些给定并定期计算解决方案或输入整个网格。我没有使用整个网格的随机条目，因为随机删除先前的条目可能会导致设置时间过长。对于随机条目，我希望阻止冲突条目会导致空白单元格，因此答案可能是在删除先前冲突条目的同时进行长时间设置。您将需要返回所有空单元格，直到没有空单元格为止。当所有单元格都填满时，解决方案必须是有效的，否则就会消除冲突。

于 2013-11-11T02:19:33.973 回答
0

我的方法是将您的第一种和第二种方法结合在一起。

首先，你必须有一个数独求解器。将求解器应用于空数独。那就是为没有线索的数独寻找解决方案。从左上角到右下角依次填写数字。否则就是时间问题。我不知道为什么。无论如何，它的工作速度非常快，没有时间完成数独谜题。应用回溯时，将每个位置的可能数字列表打乱。否则，您每次都会得到相同的谜题。

其次，随机化所有职位的新列表。这是一个随机排列的 81 个位置的列表。根据这个顺序列表，尝试从上面的拼图中删除数字。每次删除一个数字时，都必须检查它是否有多个解决方案。如果它有多个解决方案。该数字应放回并尝试随机列表中的下一个位置。这个过程一直持续到列表结束，或者您已经成功地从拼图中删除了 64 个数字。这个数字是 64，因为有人已经证明没有少于 17 条线索的数独具有唯一解。这个过程从 15 秒到 2 分钟不等。通常需要 30 秒才能得到一个数独谜题。

第三，如果您不想为每个数独谜题等待 30 秒到 2 分钟，您可以对上述数独应用一些突变。这包括切换行和列、旋转。您也可以重新映射数字。例如，1->2、2->3...9->1。旋转和重新映射后，没有人会注意到这是原来的数独。

于 2021-04-02T01:28:57.373 回答