关于数独求解
有人可以帮我理解这个解决方案：
Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
Fill in some empty grid with the known values
Make an original copy of the array
Start from top left grid (nx = 0, ny = 0), check if grid is empty
if (grid is empty) {
assign the empty grid with values (i)
if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
fill in the number
if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
discard (i) and repick other values (i++)
}
else {
while (nx < 9) {
Proceed to next row grid(nx++, ny)
if (nx equals 9) {
reset nx = 1
proceed to next column grid(nx,ny++)
if (ny equals 9) {
print solution
}
}
}
}
Can someone please help me understand this solution:
Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
Fill in some empty grid with the known values
Make an original copy of the array
Start from top left grid (nx = 0, ny = 0), check if grid is empty
if (grid is empty) {
assign the empty grid with values (i)
if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
fill in the number
if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
discard (i) and repick other values (i++)
}
else {
while (nx < 9) {
Proceed to next row grid(nx++, ny)
if (nx equals 9) {
reset nx = 1
proceed to next column grid(nx,ny++)
if (ny equals 9) {
print solution
}
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一个简单的暴力求解器。它从左上角开始，从左到右逐行工作，尝试将每个可能的数字放入每个方块中，然后使用递归调用继续。一旦失败，它会回溯并尝试不同的替代方案。
名为
safe的函数通过检查哪些值已被放置在行、列和框中来确定当前将值n放置在特定单元格中是否合法。这是解决数独的最简单（也是最慢）的方法之一。
It's a simple brute force solver. It starts from the top left, working left to right line by line, trying to place each possible number into each square, and continuing by using a recursive call. On failure it backtracks and tries a different alternative.
The function called
safedetermines whether it is currently legal to place the valuenin a certain cell, by checking which values have already been placed in the row, column and box.It's one of the simplest (and slowest) ways to solve a Sudoku.
解数独的方法有很多（不知道大家是否对此感兴趣）。从根本上讲，它是一个约束满足问题，您可以应用您最喜欢的一致性检查技术（例如 AC3）来传播约束并更早地修剪明显无结果的路径。您的变量是每个正方形，每个变量可以采用的域是整数 1 到 9。约束是对单元格的各个子集的 AllDiff。
您还可以将其表述为整数线性规划问题，然后让您最喜欢的 ILP 引擎（例如 lp_solve）来解决它！
There are a lot of ways to solve Sudoku (don't know if you're interested in it in general). It is fundamentally a Constraint Satisfaction Problem, and you can apply your favorite consistency checking techniques (e.g. AC3) to propagate constraints and prune obviously fruitless paths much earlier. Your variables are each square, the domain each variable can take is the integers 1 through 9. Constraints are AllDiff on various subsets of the cells.
You can also formulate it as an Integer Linear Programming problem and just let your favorite ILP engine (e.g. lp_solve) solve it!
最令人困惑的是，我希望算法在完成时用正确的值填充数独矩阵，但它只是打印这些值，然后回溯到开头，因为 t 变量的值总是写回网格（也许算法甚至设法找到另一种解决方案）。
为了在算法完成时填充网格，可以使求解函数返回 true/false，然后根据内部调用的结果决定是否回溯。
The most confusing thing was that I expected the algorithm to fill the sudoku matrix with correct values on finish, but instead it just prints the values and then backtracks to the beginning as the value of t variable is always written back to the grid (maybe algorithm even manages to find another solution).
In order to have the grid filled when the algorithm finishes one could make the solve function return true/false and then decide whether to trace back based on the result of inner calls.