论数独解决

有人可以帮我理解这个解决方案 ：

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 } } } } 

Answer 1

这是一个简单的蛮力解算器。 它从左上角开始，逐行左右工作，尝试将每个可能的数字放入每个方格，然后继续使用递归调用。 失败后，它会回溯并尝试不同的选择。

名为safe的函数通过检查已在行，列和框中放置了哪些值来确定将值n放在某个单元格中是否合法。

这是解决数独的最简单（也是最慢）的方法之一。

Answer 2

有很多方法可以解决数独（不知道你是否对它感兴趣）。 它基本上是一个约束满足问题，您可以应用您最喜欢的一致性检查技术（例如AC3）来传播约束，并且更早地修剪明显无效的路径。 您的变量是每个方块，每个变量可以采用的域是整数1到9.约束是单元的各个子集上的AllDiff。

您还可以将其表示为整数线性规划问题，并让您最喜欢的ILP引擎（例如lp_solve）解决它！

Answer 3

最令人困惑的是，我希望算法在完成时用正确的值填充数独矩阵，但它只是打印值然后回溯到开头，因为t变量的值总是写回到网格（也许算法）甚至设法找到另一种解决方案）。

为了在算法完成时填充网格，可以使求解函数返回true / false，然后根据内部调用的结果决定是否追溯。