如何用独特的解决scheme生成Sudoku板
如何用独特的解决scheme生成Sudoku板？ 我认为是初始化一个随机板，然后删除一些数字。 但我的问题是如何保持解决scheme的独特性？
简单：
- 使用高效的回溯algorithm查找所有解决scheme。
- 如果只有一个解决scheme，你就完成了。 否则，如果您有多个解决scheme，请find大多数解决scheme不同的位置。 在这个位置添加号码。
- 转到1。
我怀疑你可以find一个比这更快的解决scheme。
这是我自己的SuDoKu程序的方式：
-
从一个完整有效的董事会开始（填写81个号码）
-
列出所有81个细胞位置并随机洗牌
-
只要列表不是空的，从列表中的下一个位置，并从相关的单元格中删除号码
-
使用快速解算器testing唯一性（如果需要，则使用回溯）。 我的求解器能够计算所有的解决scheme，但是当它find一个以上的解决scheme时，它会停下来。
-
如果当前板子只有一个解决scheme，转到步骤3）并重复。
-
如果当前板子有多个解决scheme，则撤销上次移除（步骤3），并从列表中的下一个位置继续步骤3
-
停止testing所有81个职位。
这不仅可以为您提供独特的板子，还可以让您在不破坏解决scheme的独特性的情况下无法移除更多数量的板子。
当然，这只是algorithm的后半部分。 上半部分是先find一个完整的有效的董事会（随机填写！）它工作非常相似，但“在另一个方向”：
-
从空板开始
-
在空闲小区之一添加一个随机数（小区是随机select的，根据SuDoKu规则从该小区有效的号码列表中随机select号码）
-
使用回溯求解器检查当前板是否至less有一个有效的解决scheme。 如果不是，请撤消第2步，并用另一个数字和单元格重复。 请注意，这一步可能会自行生成完整有效的板，但这些板不是随机的。
-
重复，直到董事会完全充满数字
你可以作弊。 从现有的数独板开始，可以解决，然后摆弄它。
您可以将任意三行的3×3块与其他行交换。 您可以将三个3×3块的任何一列与另一列交换。 在每个块行或块列中，可以交换单行和单列。 最后，您可以对数字进行排列，因此只要整个棋盘上的排列是一致的，那么在填充的位置就会有不同的数字。
这些变化都不会使解决板无法解决。
除非P = NP，否则没有多项式时间algorithm可以用一个解来生成一般的数独问题。
在他的硕士论文中，Takayuki Yato定义了另一个解决scheme问题 （ASP），其目标是给出一个问题和一些解决scheme，find不同的解决scheme来解决这个问题，或者说不存在。 Yato然后定义了ASP完整性，难以find另一个解决scheme的问题，并且显示数独是ASP完整的。 因为他也certificate了ASP的完整性意味着NP硬度，这意味着如果你允许任意大小的数独棋盘，没有多项式时间algorithm来检查你生成的谜题是否有唯一的解决scheme（除非P = NP）。
对不起，以破坏你的快速algorithm的希望！
提供一个通用的解决scheme并不容易。 你需要知道几件事来产生一个特定types的数独…例如，你不能build立一个超过9个空9数字组（行，3×3块或列）的数独。 在一个单一的解决scheme中，最小给定的数字（即“线索”）被认为是17，但是如果我没有错，这个数独的数字位置是非常具体的。 数独的线索平均数大概是26，我不确定，但是如果你退出一个完整的网格数，直到有26个并且以对称的方式离开，你可能会有一个有效的数独。 另一方面，您可以从完成的网格中随机退出数字，然后使用CHECKER或其他工具对其进行testing，直至出现OK。
我也认为你必须明确地检查唯一性。 如果你的投票数less于17，那么一个独特的解决scheme是不太可能的，尽pipe还没有被发现，尽pipe还不清楚它是否可能存在。
但是你也可以使用SAT求解器，而不是写一个自己的回溯algorithm。 这样，您可以在一定程度上调节find解决scheme的困难程度：如果您限制SAT解算器使用的推理规则，则可以检查是否可以轻松解决这个难题。 只是谷歌“SAT解决数独”。
这是一个经典的数独谜题的方法（数独谜题有一个唯一的解决scheme;预填充的方块围绕中心广场R5C5对称）。
1）从一个完整的网格开始（使用组填充加循环来轻松获取）
2）如果可以使用剩下的线索推断清除的方块，则从两个对称的方块中移除数字。
3）重复（2）直到所有的数字被检查。
使用这种方法，您可以创build一个非常简单的数独谜题编程或不编程。 你也可以使用这种方法来制作更难的数独谜题。 您可能需要在YouTube上search“创build经典数独”以获得一步一步的示例。
