您如何生成具有独特解决方案的数独板？我的想法是初始化一个随机板，然后删除一些数字。但我的问题是如何保持解决方案的唯一性？
问问题
103717 次
14 回答
64
这是我自己的数独程序的做法：
从一个完整、有效的棋盘开始（填充 81 个数字）。
列出所有 81 个单元格位置并随机洗牌。
只要列表不为空，就从列表中取出下一个位置并从相关单元格中删除数字。
使用快速回溯求解器测试唯一性。我的求解器 - 理论上 - 能够计算所有解决方案，但为了测试唯一性，它会在找到多个解决方案时立即停止。
如果当前电路板仍然只有一个解决方案，请转到步骤 3) 并重复。
如果当前板子有多个解决方案，请撤消最后一次删除（步骤 3），然后从列表中的下一个位置继续步骤 3
测试完所有 81 个位置后停止。
这不仅为您提供了独特的板，而且还为您提供了在不破坏解决方案唯一性的情况下无法删除更多数字的板。
当然，这只是算法的后半部分。前半部分是先找到一个完整的有效棋盘（随机填充！）它的工作原理非常相似，但是“在另一个方向”：
从空板开始。
在其中一个空闲单元格中添加一个随机数（该单元格是随机选择的，并且该数字是根据 SuDoKu 规则从对该单元格有效的数字列表中随机选择的）。
使用回溯求解器检查当前板是否至少有一个有效的解决方案。如果不是，请撤消第 2 步并使用另一个数字和单元格重复。请注意，此步骤可能会自行生成完整的有效电路板，但这些电路板绝不是随机的。
重复直到板子完全填满数字。
于 2011-09-02T07:44:33.377 回答
35
简单的：
- 使用有效的回溯算法找到所有解决方案。
- 如果只有一个解决方案，你就完成了。否则，如果您有多个解决方案，请找到大多数解决方案不同的位置。在此位置添加数字。
- 转到 1。
我怀疑你能找到比这更快的解决方案。
于 2011-08-08T15:11:06.150 回答
22
你可以作弊。从可以解决的现有数独板开始，然后摆弄它。
您可以将三个 3x3 块的任何一行与任何其他行交换。您可以将三个 3x3 块的任何一列与另一列交换。在每个块行或块列中，您可以交换单行和单列。最后，您可以排列数字，只要排列在整个棋盘上保持一致，填充位置就有不同的数字。
这些更改都不会使可解决的董事会无法解决。
于 2011-08-03T11:29:52.193 回答
13
除非 P = NP，否则没有多项式时间算法可以生成只有一种解决方案的一般数独问题。
在他的硕士论文中，Takayuki Yato 定义了另一个解决方案问题(ASP)，其目标是，给定一个问题和一些解决方案，找到该问题的不同解决方案或证明不存在任何解决方案。Yato 随后定义了 ASP 完备性，即很难找到另一种解决方案的问题，并表明数独是 ASP 完备的。由于他还证明了 ASP 完备性意味着 NP 难度，这意味着如果您允许任意大小的数独板，则没有多项式时间算法来检查您生成的谜题是否具有唯一解（除非 P = NP）。
很抱歉破坏了您对快速算法的希望！
于 2011-09-02T07:55:25.620 回答
8
解决方案分为两部分：
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 ) 对于 Masking Pattern，我们需要一个求解器算法。由于我们已经有一个非常独特的数字网格（也已解决！），这为我们使用求解器提供了更快的性能
第 1 步：从 81 个随机位置中选择 15 个开始。
第 2 步：与求解器检查它是否具有唯一解
第 3 步：如果解决方案不是唯一的，则选择其他位置。迭代步骤 2 和 3，直到找到唯一的解决方案
这应该会给你一个非常独特和快速的数独板。
于 2019-03-27T09:02:13.700 回答
4
这是您可以生成任何可能的数独板以及任何其他 nxn 数独板
至于这个算法的效率如何，在 java 中生成一百万个板需要 3.6 秒，在 golang 中需要 3.5 秒
- 找到任何填满的数独板。（使用琐碎的不会影响最终结果）
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（比如 num），（即 1、2、3、5、6、7、8、9）从范围 [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;
}
}
}
}
- 现在洗牌。取第一组 3 行，将它们洗牌，然后对所有行进行。（在 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;
}
- 交换列，再次取 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;
}
}
- 交换行块本身（即 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 提示数独
于 2020-04-26T14:01:47.423 回答
2
斯威夫特 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()
于 2020-11-20T01:56:25.210 回答
1
给出一个通用的解决方案并不容易。您需要了解一些事情才能生成特定类型的数独……例如，您不能构建具有超过 9 个空 9 数字组（行、3x3 块或列）的数独。单一解决方案数独中的最小给定数字（即“线索”）被认为是 17，但如果我没记错的话，这个数独的数字位置非常具体。数独的平均线索数约为 26，我不确定，但如果您退出已完成网格的数字直到有 26 个并以对称方式保留它们，您可能有一个有效的数独。另一方面，您可以从已完成的网格中随机退出数字并使用 CHECKER 或其他工具对其进行测试，直到出现 OK。
于 2011-08-03T10:14:23.353 回答
1
这是制作经典数独谜题的一种方法（具有唯一解决方案的数独谜题；预填充的正方形围绕中心正方形 R5C5 对称）。
1）从一个完整的网格开始（使用组填充加循环移位轻松获得它）
2）如果清除的方块可以使用剩余的线索推断出来，则从两个对称的方块中删除数字。
3）重复（2），直到所有的数字都被检查。
使用这种方法，无论是否编程，您都可以创建一个非常简单的数独游戏。您还可以使用此方法制作更难的数独谜题。您可能想在 YouTube 上搜索“创建经典数独”以获取逐步示例。
于 2017-03-05T02:12:43.030 回答
0
我还认为您必须明确检查唯一性。如果您的给定少于 17 个，则不太可能找到唯一的解决方案：尚未找到任何解决方案，尽管尚不清楚它是否存在。）
但是您也可以使用 SAT 求解器，而不是编写自己的回溯算法。这样，您可以在一定程度上调节找到解决方案的难度：如果您限制 SAT-solver 使用的推理规则，您可以检查您是否可以轻松解决难题。只是谷歌“SAT解决数独”。
于 2011-09-02T08:33:21.997 回答
0
又快又脏，但有效：
将 numpy 导入为 np
导入数学
N = 3
# 重写 https://www.tutorialspoint.com/valid-sudoku-in-python
def isValidSudoku(M):
'''
检查数独矩阵：
一个 9x9 数独矩阵是有效的，当且仅当：
行包含 1 - 9 和
col 包含 1 - 9 和
3x3 包含 1 - 9
0 用于空白条目
'''
对于范围内的 i (9)：
行 = {}
col = {}
块 = {}
row_cube = N * (i//N)
col_cube = N * (i%N)
对于范围内的 j (N*N)：
如果 M[i][j] != 0 并且 M[i][j] 在行中：
返回假
行[M[i][j]] = 1
如果 M[j][i] != 0 和 M[j][i] 在 col：
返回假
科尔[M[j][i]] = 1
rc = row_cube + j//N
cc = col_cube + j%N
如果 M[rc][cc] 在块中并且 M[rc][cc] != 0：
返回假
块[M[rc][cc]]=1
返回真
def generate_sudoku_puzzles(run_size, 种子):
order = int(math.sqrt(run_size))
计数 = 0
有效 = 0
空= []
np.random.seed(seed) # 获得可重复的结果
对于范围内的 k（顺序）：
对于 l 在范围内（顺序）：
A = np.fromfunction(lambda i, j: ((k*i + l+j) % (N*N)) + 1, (N*N, N*N), dtype=int)
B = np.random.randint(2, size=(N*N, N*N))
empty.append(np.count_nonzero(B))
C = A*B
计数 += 1
如果是有效数独（C）：
有效 += 1
最后 = C
# print('C(',k,l,') 是有效的数独：')
# print(C) # 取消对拼图的注释
print('Tried', count, 'valid', valid, 'yield', round(valid/count, 3)*100, '%', '平均线索', round(sum(empty)/len(empty)) )
返回（最后）
posTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 0), \
(3, 0, 0, 5, 0, 7, 0, 0, 2), \
(0, 0, 5, 0, 0, 0, 3, 0, 0), \
(0, 4, 0, 3, 0, 6, 0, 5, 0), \
(6, 0, 0, 0, 0, 0, 0, 0, 8), \
(0, 1, 0, 2, 0, 8, 0, 3, 0), \
(0, 0, 7, 0, 0, 0, 4, 0, 0), \
(1, 0, 0, 8, 0, 2, 0, 0, 9), \
(0, 6, 0, 0, 9, 0, 0, 1, 0), \
])
negTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 2), \
(3, 0, 0, 5, 0, 7, 0, 0, 2), \
(0, 0, 5, 0, 0, 0, 3, 0, 0), \
(0, 4, 0, 3, 0, 6, 0, 5, 0), \
(6, 0, 0, 0, 0, 0, 0, 0, 8), \
(0, 1, 0, 2, 0, 8, 0, 3, 0), \
(0, 0, 7, 0, 0, 0, 4, 0, 0), \
(1, 0, 0, 8, 0, 2, 0, 0, 9), \
(0, 6, 0, 0, 9, 0, 0, 1, 0), \
])
print('阳性质量控制测试：', isValidSudoku(posTest))
print('阴性质量控制测试：', isValidSudoku(negTest))
打印（generate_sudoku_puzzles（10000, 0））
输出：
阳性质量控制测试：真
阴性质量控制测试：错误
尝试 10000 有效 31 产量 0.3 % 平均线索 40
[[0 0 2 3 0 0 0 7 8]
[7 8 9 1 2 0 0 0 0]
[5 0 0 0 9 0 0 3 0]
[0 0 0 6 7 8 0 0 2]
[0 2 0 0 0 0 7 8 9]
[8 0 0 2 3 0 0 0 0]
[0 0 0 0 0 2 3 0 5]
[0 5 6 0 8 9 1 2 0]
[0 3 0 5 0 0 0 9 0]]
取消注释拼图源的两行。
于 2021-11-05T10:02:40.657 回答
0
您可以从任何有效的（填充的）拼图开始，然后对其进行修改以产生完全不同的拼图（再次填充）。您可以交换单个单元格，而不是排列数字组 - 种子拼图和结果拼图之间没有任何相似之处。我很久以前用VB写过一个简单的程序，你可以在这里找到它：https ://www.charalampakis.com/blog/programming-vb-net/a-simple-algorithm-for-creating-sudoku-puzzles-using -视觉基础。它可以很容易地翻译成任何语言。
然后，随机并逐渐移除单元格并检查拼图是否可解决并具有唯一解决方案。您还可以根据解决方案所需的规则根据难度对难题进行评分。继续，直到删除任何已知的单元格导致无法解决的难题。
高温高压
于 2020-11-30T08:27:25.737 回答
0
您可能需要这样的代码：
#pz is a 9x9 numpy array
def PossibleValueAtPosition(pz:[], row:int, col:int):
r=row//3*3
c=col//3*3
return {1,2,3,4,5,6,7,8,9}.difference(set(pz[r:r+3,c:c+3].flat)).difference(set(pz[row,:])).difference(set(pz[:,col]))
def SolvePuzzle(pz:[], n:int, Nof_solution:int):# init Nof_solution = 0
if Nof_solution>1:
return Nof_solution # no need to further check
if n>=81:
Nof_solution+=1
return Nof_solution
(row,col) = divmod(n,9)
if pz[row][col]>0: # location filled, try next location
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
else:
l = PossibleValueAtPosition(pz, row,col)
for v in l: # if l = empty set, bypass all
pz[row][col] = v # try to fill a possible value v
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
pz[row][col] = 0
return Nof_solution # resume the value, blacktrack
于 2021-03-19T07:22:46.993 回答
0
一种更快生成数独的方法。
- 找到一个存在的数独。
- 与随机组交换值。
- 交换单元格或列或行网格或列网格。
您交换值会使值不同，如果不交换行或列，则数独本质上不会改变。
您可以用 9 个网格标记数独，交换的行和列必须在同一个网格中进行。就像你可以交换row1-3、row4-6、row7-9，不要交换row1-4或row1-7。您还可以交换行网格（将第 1~3 行与第 4~6 行或第 7~9 行交换）。
解数独：用所有可能的值记录空，然后检查从1到9的值。如果一个值是唯一的，则将其从循环中删除。
于 2019-07-03T04:41:21.733 回答