如何生成一个只有唯一解的数独棋盘？我的想法是初始化一个随机的棋盘，然后去掉一些数字。但我想知道如何保持解的唯一性？
17个回答
80
这是我自己的SuDoKu程序实现的方式：
从一个完整、有效的棋盘开始（填有81个数字）。
制作一个所有81个单元格位置的列表，并随机打乱它。
只要列表不为空，就从列表中获取下一个位置并从相关单元格中删除数字。
使用快速回溯求解器测试唯一性。我的求解器在理论上能够计算所有的解，但为了测试唯一性，当它发现多于一个解时就立即停止。
如果当前棋盘仍然只有一个解，请执行第3步并重复。
如果当前棋盘有多个解，请撤销最后一次删除（第3步），并继续使用列表中的下一个位置执行第3步。
当您测试完所有81个位置时停止。
这不仅会给您独特的棋盘，还会给您不能再删除任何数字而不破坏解唯一性的棋盘。
当然，这只是算法的后半部分。首先要完成第一部分，即先找到一个完整的有效棋盘（随机填充！）它的实现方式非常类似，但“方向相反”：
从空棋盘开始。
在一个自由单元格中添加一个随机数（单元格是随机选择的，数字是从根据SuDoKu规则对该单元格有效的数字列表中随机选择的）。
使用回溯求解器检查当前棋盘是否至少有一个有效解。如果没有，请撤销第2步并在另一个数字和单元格中重复执行。请注意，此步骤可能会独立地产生完整的有效棋盘，但这些棋盘并不是随机的。
重复直到棋盘被完全填满数字。
- Doc Brown
15
我发现你的算法特别简单而且有效。谢谢。 - krawyoti
5我对“（3）使用求解器检查当前棋盘是否至少有一个有效解”有些困惑。如果您仅向空棋盘添加了一个字符（在步骤2中），然后在其中测试求解器（在步骤3中），那么您实质上是在解决一个空棋盘。我认为我的求解器没有那么好，更重要的是，如果它能够解决一个空棋盘，那么获取有效解决方案的问题已经得到解决，我可以跳过步骤4！ - The111
1@The111：解决一个空棋盘很容易，甚至可以不用电脑。但我正在寻找一个随机填充的棋盘，这就是为什么我不会在第三步停止的原因。 - Doc Brown
第二个算法中第三个点的目的是什么？是否可能生成一个没有任何解决方案的有效棋盘？ - Luke
@Luke：拿一个有唯一解的任意数独来说吧。假设左上角是空的，如果你只应用规则（简而言之：每行、每列和每个3x3方格都应包含数字1-9），你会直接发现可以在左上角放置1、3、5和7。但最终解中只允许出现“1”，因此如果你放置了3、5或7，回溯求解器将显示这三个数字不会导致有效的最终解。 - Doc Brown
显示剩余10条评论
40
简单：
- 使用高效的回溯算法找到所有解。
- 如果只有一个解，则完成。否则，如果您有多个解，请找到其中大多数解不同的位置，并在该位置添加数字。
- 返回第1步。
我怀疑你能找到比这更快的解决方案。
- Tomas
3
1我认为你是对的，但是如何对这种生成方式产生的棋盘进行级别评分，似乎没有参数来控制难度。 - guilin 桂林
好的，那是一个不同的问题，更加困难。确定的是，你添加的数字越多，它就越容易。 - Tomas
3不必找到所有解，只需寻找第二个即可。 - Dávid Horváth
24
你可以作弊。从一个能够解决的数独游戏板开始，然后篡改它。
你可以交换任意一行三个3x3块中的行与另一行。你也可以将任意一列三个3x3块中的列与另一列互换。在每个块行或块列内，你可以交换单行和单列。最后，你可以排列数字，使填充位置有不同的数字，只要排列在整个板上是一致的即可。
这些改变都不会使本来可以解决的数独游戏板成为无法解决的。
- rossum
5
但是唯一性呢？你如何选择保持解决方案唯一的空单元格？ - Ameer Jewdaki
1@kvphxga：你从一个有唯一解的部分棋盘开始。任何允许的交换都不会影响解的唯一性。 - rossum
这不是一个可怕的解决方案吗？如果您使用一个完整的数独棋盘并交换行和列，求解器是否会注意到谜题之间的相似性（感觉相同）？您最终只使用了极少量的唯一解决方案，我担心在某些时候它对于求解器来说不会感到随机。值得花费更多的精力去做得更好。 - bryc
1你可以在行/列内交换单独的行，也可以重新分配位置上的数字。如果你想的话，你可以有十个不同的起始网格，并随机选择一个。 - rossum
1顺便提一下，这属于组合数学 - 完整解决方案比“本质不同的解决方案”要多得多（维基百科）。因此，您可以使用一个配置创建多个谜题，但正如@bryc所提到的那样，这很可能会导致谜题感觉和玩起来相似。 - LeoDog896
15
除非P = NP，否则没有用于生成仅有一个解的一般数独问题的多项式时间算法。
在他的硕士论文中，Takayuki Yato定义了另一个解决方案问题(ASP)，其目标是在给定问题和某些解决方案的情况下，找到该问题的不同解决方案或显示不存在。然后，Yato定义了ASP完备性，即难以找到另一个解决方案的问题，并证明数独是ASP完备的。由于他还证明了ASP完备性意味着NP难度，这意味着如果您允许任意大小的数独板，则没有多项式时间算法可用于检查您生成的谜题是否具有唯一解（除非P = NP）。
很抱歉破坏了您对快速算法的希望！
在他的硕士论文中，Takayuki Yato定义了另一个解决方案问题(ASP)，其目标是在给定问题和某些解决方案的情况下，找到该问题的不同解决方案或显示不存在。然后，Yato定义了ASP完备性，即难以找到另一个解决方案的问题，并证明数独是ASP完备的。由于他还证明了ASP完备性意味着NP难度，这意味着如果您允许任意大小的数独板，则没有多项式时间算法可用于检查您生成的谜题是否具有唯一解（除非P = NP）。
很抱歉破坏了您对快速算法的希望！
- templatetypedef
5
4公平地说，使用所选答案中的技术可以每秒生成数百个独特的谜题。 - Grandpa
1好的，在这种情况下，我想看看。因为如果你尝试生成恶魔数独，有时测试所有可能性确实需要很长时间。
对于有很多初始填充数字的简单数独，我同意。 - dyesdyes
我的快速斑马谜题生成器的希望几乎烟消云散，直到我仔细阅读了这篇论文（谢谢！）的开头。在求解器中，您需要找到一个解决方案（因此称为求解器），而在生成器中，您需要生成谜题--您不需要实际解决它（大多数方法使用求解器作为生成器的一部分是另一回事）。我并不是说你的第一个声明是错误的，我是说在那篇论文中没有证明它。 - greenoldman
@爷爷通过保持有效性的变换来重新排列拼图，并不会得到“根本不同”的拼图。 - starball
@starball 嗯，也许我们看到的是不同的答案？我指的是Tomas的回答，他没有提到排列拼图的问题。 - Grandpa
11
解决方案分为两部分：
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
第8步：随机重新排列第7、8和9行
第9步：在大小为9x3的3个列组中随机重新排列
第10步：在大小为3x9的3个行组中随机重新排列
完成了...
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，直到找到唯一解。
这将为您提供非常独特且快速的数独游戏板。
- gapjiba
2
我经过一番思考，现在认为我明白了。步骤2的意思是例如将所有的1改为5，将所有的2改为1。步骤3-8意味着您可以重新排列行和列，只要它们保持在相同的方块中即可。步骤9和10意味着重新排列方块的行和列。我理解得对吗？ - Michael Salmon
2这个算法只能创建非常特定类型的谜题。正如您所看到的，数字（5、8、3）总是作为一组出现在第1、2和3行中。所有其他3组也是如此。对于通用数独生成器来说，这个算法不幸地没有用处。 - Jan Feldmann
11
这样，您就可以生成任何可能的数独棋盘以及其他nxn数独棋盘。
至于这个算法的效率，使用Java生成一百万个棋盘需要3.6秒，而使用Golang则只需3.5秒。
1. 找到任何一个已填充的数独棋盘。（使用简单的棋盘不会影响最终结果）
4. 交换列，再次取出3列的块，打乱它们，并对所有3个块执行此操作。
5. 交换行块本身（即3x9块）
将块状的列互换位置。
至于这个算法的效率，使用Java生成一百万个棋盘需要3.6秒，而使用Golang则只需3.5秒。
1. 找到任何一个已填充的数独棋盘。（使用简单的棋盘不会影响最终结果）
int[][] board = new int[][] {
{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}
};
- 对于从1到9（例如1、2、3、5、6、7、8、9）的每个数字（称为num），从区间[1到9]中随机选取一个数字，遍历整个棋盘，将num与所选的随机数进行交换。
void shuffleNumbers() {
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(9);
swapNumbers(i, ranNum);
}
}
private void swapNumbers(int n1, int n2) {
for (int y = 0; y<9; y++) {
for (int x = 0; x<9; x++) {
if (board[x][y] == n1) {
board[x][y] = n2;
} else if (board[x][y] == n2) {
board[x][y] = n1;
}
}
}
}
- 现在开始洗牌。将第一组三行打乱，对所有行进行此操作（在9 x 9数独中），然后对第二组和第三组行进行同样的操作。
void shuffleRows() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapRows(i, blockNumber * 3 + ranNum);
}
}
void swapRows(int r1, int r2) {
int[] row = board[r1];
board[r1] = board[r2];
board[r2] = row;
}
4. 交换列，再次取出3列的块，打乱它们，并对所有3个块执行此操作。
void shuffleCols() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapCols(i, blockNumber * 3 + ranNum);
}
}
void swapCols(int c1, int c2) {
int colVal;
for (int i = 0; i < 9; i++){
colVal = board[i][c1];
board[i][c1] = board[i][c2];
board[i][c2] = colVal;
}
}
5. 交换行块本身（即3x9块）
void shuffle3X3Rows() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Rows(i, ranNum);
}
}
void swap3X3Rows(int r1, int r2) {
for (int i = 0; i < 3; i++) {
swapRows(r1 * 3 + i, r2 * 3 + i);
}
}
将块状的列互换位置。
void shuffle3X3Cols() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Cols(i, ranNum);
}
}
private void swap3X3Cols(int c1, int c2) {
for (int i = 0; i < 3; i++) {
swapCols(c1 * 3 + i, c2 * 3 + i);
}
}
现在你已经完成了，你的数独板应该是一个有效的数独板
要生成一个带有隐藏数值的数独板，可以使用回溯数独算法，从板上尝试移除一个元素，直到你拥有一个可解的数独板，并继续移除直到只要再移除一个元素就会变得不可解。
如果你想根据难度分类最终生成的数独板，只需在一次次移除元素时计算板上剩下的数字数量。数字越少，难度越大。
数独最少可能的提示为17，但并非所有可能的数独板都能简化为17个提示的数独。
- Manish Kumar
1
1在手动解决了数百个数独难题之后，我必须说起始数字的数量与解决难度几乎没有关系。难度来自于需要解决难题的算法的复杂性。有些算法在仅仅扫视一下难题时就可以轻松实现，而其他算法则需要在单元格中放置注释以跟踪更复杂的模式。因此，在评估难度时，必须考虑到人类解决难题的容易程度，而不是计算机所需的努力程度。 - David Rector
2
SWIFT 5 版本
这是我的代码，简单易懂：
首先，创建一个 [[Int]] 数组函数
func getNumberSudoku() -> [[Int]] {
// Original number
let originalNum = [1,2,3,4,5,6,7,8,9]
// Create line 1 to 9 and shuffle from original
let line1 = originalNum.shuffled()
let line2 = line1.shift(withDistance: 3)
let line3 = line2.shift(withDistance: 3)
let line4 = line3.shift(withDistance: 1)
let line5 = line4.shift(withDistance: 3)
let line6 = line5.shift(withDistance: 3)
let line7 = line6.shift(withDistance: 1)
let line8 = line7.shift(withDistance: 3)
let line9 = line8.shift(withDistance: 3)
// Final array
let renewRow = [line1,line2,line3,line4,line5,line6,line7,line8,line9]
// Pre-shuffle for column
let colSh1 = [0,1,2].shuffled()
let colSh2 = [3,4,5].shuffled()
let colSh3 = [6,7,8].shuffled()
let rowSh1 = [0,1,2].shuffled()
let rowSh2 = [3,4,5].shuffled()
let rowSh3 = [6,7,8].shuffled()
// Create the let and var
let colResult = colSh1 + colSh2 + colSh3
let rowResult = rowSh1 + rowSh2 + rowSh3
var preCol: [Int] = []
var finalCol: [[Int]] = []
var prerow: [Int] = []
var finalRow: [[Int]] = []
// Shuffle the columns
for x in 0...8 {
preCol.removeAll()
for i in 0...8 {
preCol.append(renewRow[x][colResult[i]])
}
finalCol.append(preCol)
}
// Shuffle the rows
for x in 0...8 {
prerow.removeAll()
for i in 0...8 {
prerow.append(finalCol[x][rowResult[i]])
}
finalRow.append(prerow)
}
// Final, create the array into the [[Int]].
return finalRow
}
然后用法：
var finalArray = [[Int]]
finalArray = getNumberSudoku()
- user12616082
1
以下是制作经典数独谜题的方法（数独谜题只有一个解; 预填的方格围绕中心方格R5C5对称）。
1）从完整的网格开始（使用组填充加循环移位轻松获得）
2）如果可以使用剩余线索推断出清除的方格，则从两个对称方格中删除数字。
3）重复步骤（2），直到检查所有数字为止。
使用此方法，您可以创建非常容易或不需要编程的数独谜题。 您还可以使用此方法制作更难的数独谜题。 您可能希望在YouTube上搜索“创建经典数独”以获得逐步示例。
1）从完整的网格开始（使用组填充加循环移位轻松获得）
2）如果可以使用剩余线索推断出清除的方格，则从两个对称方格中删除数字。
3）重复步骤（2），直到检查所有数字为止。
使用此方法，您可以创建非常容易或不需要编程的数独谜题。 您还可以使用此方法制作更难的数独谜题。 您可能希望在YouTube上搜索“创建经典数独”以获得逐步示例。
- Yaling Zheng
1
您可以从任何有效（已填写）的数独谜题开始，修改它以生成完全不同的谜题（同样是已填写的）。您可以交换单个单元格而不是排列数字组-种子谜题和结果谜题之间没有任何相似之处。我很久以前用VB编写了一个简单的程序，您可以在这里找到它：https://www.charalampakis.com/blog/programming-vb-net/a-simple-algorithm-for-creating-sudoku-puzzles-using-visual-basic。它可以轻松地转换成任何语言。
然后，随机逐渐地移除单元格并检查谜题是否可解且具有唯一解。您还可以根据解决方案所需的规则评估谜题的难度。继续进行，直到删除任何已知单元格导致无法解决的谜题。
希望这能帮助到您。
然后，随机逐渐地移除单元格并检查谜题是否可解且具有唯一解。您还可以根据解决方案所需的规则评估谜题的难度。继续进行，直到删除任何已知单元格导致无法解决的谜题。
希望这能帮助到您。
- achar
1
提供一个通用的解决方案并不容易。你需要知道一些事情才能生成特定类型的数独...例如，你不能构建一个有超过九个空的9数字组（行、3x3块或列）的数独。单解数独中最少给出的数字（即“线索”）被认为是17，但如果我没记错的话，这个数独的数字位置非常具体。数独的平均线索数量约为26，但我不确定，如果你从完成的网格中退出数字直到有26个，并以对称的方式留下这些数字，那么你可能会得到一个有效的数独。 另一方面，你可以随机地从完成的网格中退出数字，并使用CHECKER或其他工具进行测试，直到它变成OK。
- Daniel
2
2线索的数量已被证明为17个 :) - rhbvkleef
1我想补充一下，自从这次讨论以来，保证唯一解所需的最小预填单元格数量问题已被证明为17。（当然，这并不意味着每个数独棋盘都可以简化为17个单元格：它只是意味着没有16个预填单元格且有唯一解的数独棋盘存在，而至少存在一个17个预填单元格且有唯一解的棋盘。） - Sebastian
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
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 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8- Francisco Ary Martins9 6 1 2 5 4 7 8 3 2 5 4 7 8 3 9 6 1 ...- Francisco Ary Martins