如何使用独特的解决方案生成数独板

Question

如何使用独特的解决方案生成数独板？我想的是初始化一个随机板然后删除一些数字。但我的问题是如何保持解决方案的独特性？

Answer 1

简单：

1. 使用高效的回溯算法找到所有解决方案。
2. 如果只有一个解决方案，那么你就完成了。否则，如果您有多个解决方案，请找到大多数解决方案不同的位置。在此位置添加号码。
3. 转到1。

我怀疑你能找到比这更快的解决方案。

Answer 2

这是我自己的SuDoKu程序的方式：

---

1. 从一个完整有效的电路板（填充81个数字）开始。
2. 列出所有81个单元格位置并随机随机播放。
3. 只要列表不为空，请从列表中取出下一个位置，然后从相关单元格中删除该编号。
4. 使用快速回溯求解器测试唯一性。理论上，我的解算器能够计算所有解决方案，但是为了测试唯一性，它会在找到多个解决方案时立即停止。
5. 如果当前电路板仍然只有一个解决方案，请转到步骤3）并重复。
6. 如果当前电路板有多个解决方案，请撤消上次移除（步骤3），然后从列表中的下一个位置继续执行步骤3
7. 当您测试了所有81个位置时停止。

---

这不仅为您提供了独特的电路板，而且还为您提供了无法在不破坏解决方案独特性的情况下再删除任何数字的电路板。

当然，这只是算法的后半部分。前半部分是首先找到一个完整有效的板（随机填充！）它的工作方式非常相似，但“在另一个方向”：

---

1. 从空板开始。
2. 在其中一个空闲单元格中添加一个随机数（随机选择该单元格，并根据SuDoKu规则从该单元格的有效数字列表中随机选择该数字）。
3. 使用回溯解算器检查当前板是否至少有一个有效的解决方案。如果不是，请撤消步骤2并重复另一个数字和单元格。请注意，此步骤可能会自行生成完整的有效板，但这些板并非随机。
4. 重复直到电路板完全充满数字。

Answer 3

你可以作弊。从现有的数独板开始，然后可以解决它。

您可以将三个3x3块的任意行与任何其他行交换。您可以将三个3x3块的任何列与另一列交换。在每个块行或块列中，您可以交换单行和单列。最后，您可以对数字进行置换，因此只要整个板上的排列一致，填充位置就会有不同的数字。

这些变化都不会使可解决的电路板无法解决。

Answer 4

除非P = NP，否则没有多项式时间算法可以用一个解决方案生成一般的数独问题。

在他的硕士论文中，Takayuki Yato定义了The Another Solution Problem（ASP），其目标是，在给出问题和解决方案的情况下，找到针对该问题的不同解决方案或表明不存在问题。 Yato然后定义了ASP完整性，难以找到另一个解决方案的问题，并表明Sudoku是ASP完成的。由于他也证明ASP完全性意味着NP硬度，这意味着如果你允许任意大小的数独板，没有多项式时间算法来检查你生成的拼图是否有一个独特的解决方案（除非P = NP）。

抱歉，破坏了快速算法的希望！

Answer 5

提供通用解决方案并不容易。你需要知道一些事情才能生成特定类型的数独...例如，你不能建立一个超过9个空的9个数字组（行，3x3块或列）的数独。单一解决方案中的最小给定数字（即“线索”）被认为是17，但如果我没错，这个数独的数字位置非常具体。数独游戏的平均线索数约为26，我不确定，但是如果你退出已完成网格的数字直到有26并且以对称的方式离开它们，那么你可能拥有一个有效的数独游戏。另一方面，您可以随机退出已完成网格中的数字并使用CHECKER或其他工具对其进行测试，直到找到确定。

Answer 6

这是一种制作经典数独拼图的方法（数独拼图有一个唯一的解决方案;预填充正方形围绕中心正方形R5C5对称）。

1）从一个完整的网格开始（使用组填充加循环移位以轻松获得）

2）如果可以使用剩余的线索推断出清晰的方块，则从两个对称的方格中移除数字。

3）重复（2）直到检查所有数字。

使用此方法，无论是否编程，您都可以创建一个非常简单的数独谜题。你也可以使用这种方法来制作更难的数独谜题。您可能希望在YouTube上搜索“创建经典数独游戏”以获得一步一步的示例。

Answer 7

解决方案分为两部分： A.生成数字模式6000亿 B.生成掩蔽模式〜7e23组合

A）对于数字模式，最快的方式可以产生独特的组合，没有花费在回溯或测试上的时间

步骤1.选择一个已经存在的矩阵，我选择了下面的矩阵，因为它可以在没有计算设备或求解器帮助的情况下由人类轻松制作：

第一行是按升序排列的数字 第二行也是按升序排列，但从4开始滚动 第三行也是按升序排列，但从7开始滚动 第4,5,6行：用右上方的列替换三个细胞柱 - 2 5 8并在最后一列的3x3细胞内滚动 第7,8,9行：用右上方的列替换三个细胞柱 - 3 6 9并在最后一列的3x3细胞内滚动

1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 1 5 6 4 8 9 7 5 6 4 8 9 7 2 3 1 8 9 7 2 3 1 5 6 4 3 1 2 6 4 5 9 7 8 6 4 5 9 7 8 3 1 2 9 7 8 3 1 2 6 4 5

步骤2.随机移动数字并替换所有其他单元格 步骤3.随机重新排列第1,2和3列 步骤4.在其自身内随机重新排列第4,5和6列 步骤5.在其自身内随机重新排列第7,8和9列 步骤6.随机重新排列行1,2和3 步骤7.随机重新排列其自身内的行4,5和6 步骤8.随机重新排列其自身内的行7,8和9 步骤9.随机重新排列3个大小为9x3的列组 步骤10.随机重新排列3个大小为3x9的行组

瞧...

5 8 3 1 6 4 9 7 2 7 2 9 3 5 8 1 4 6 1 4 6 2 7 9 3 8 5 8 5 2 6 9 1 4 3 7 3 1 7 4 2 5 8 6 9 6 9 4 8 3 7 2 5 1 4 6 5 9 1 3 7 2 8 2 3 1 7 8 6 5 9 4 9 7 8 5 4 2 6 1 3

B）对于掩蔽模式，我们需要一个求解器算法。由于我们已经有一个非常独特的数字网格（也已经解决了！），这使我们使用求解器的性能更快

步骤1：从81中选择15个随机位置开始。 第2步：使用求解器检查它是否具有唯一解 第3步：如果解决方案不唯一，请选择其他位置。迭代步骤2和3，直到找到唯一解决方案

这应该会给你一个非常独特和快速的数独板。

Answer 8

我还认为你必须明确检查唯一性。如果你的数量少于17，那么一个独特的解决方案是不太可能的，但是：尚未找到，但目前尚不清楚它是否存在。）

但是你也可以使用SAT求解器，而不是编写自己的回溯算法。这样，您可以在某种程度上规定找到解决方案的难度：如果您限制SAT解算器使用的推理规则，您可以检查是否可以轻松解决难题。只是谷歌为“SAT解决数独”。

Answer 9

一种更快地生成数独的方法。

1. 找到一个存在的数独。
2. 用随机组交换值。
3. 交换单元格或列或行网格或列网格。

你交换的值会使值不同，如果没有交换行或列，数据就不会在必要时改变。

您可以使用9个网格标记数独，交换的行和列必须在同一网格中执行。就像你可以交换row1-3，row4-6，row7-9，不要交换row1-4或row1-7。您也可以交换行网格（交换行1~3与行4~6或行7~9）。

解决数独：使用所有可能的值记录空，然后检查1到9之间的值。如果一个值是唯一的，则将其从循环中删除。