数独逻辑推导不能完成（用回溯解决数独）

数独逻辑推导不能完成（用回溯解决数独）number_unassigned →此函数找到一个空单元格，并使变量'row'和'col'等于该单元格的索引。在C中，我们使用指针来改变传递给该函数的变量（row，col）的值（通过引用传递）。在Java和Python中，我们返回一个包含这些值的数组（或Python列表）。所以，这个函数告诉我们是否有任何未分配的单元格。如果有任何未分配的单元格，那么此函数也会告诉我们该单元格的索引。print_sudoku() →这只是打印矩阵的功能。在回溯中，我们首先从一个子解决方案开始，如果这个子解决方案没有给我们一个正确的最终答案，那么我们回过头来改变我们的子解决方案。我们将以类似的方式解决我们的数独。我们将遵循的步骤是：所以，让我们编写代码吧。class Sudoku { private static final int SIZE = 9; private static int[][] ma

在这篇文章中，我将介绍一种使用回溯的数独求解算法。如果你不知道回溯，那么只需刷过上一篇文章。

Sudoku是一个9x9矩阵，填充数字1到9，每个行，列和子矩阵（3x3）的每个数字都是1到9.我们提供了部分填充的9x9矩阵，必须填充其中每个剩余的细胞。例如，下面给出了数独问题。

其解决方案如下。

您可以看到每个行，列和子矩阵（3x3）包含从1到9的每个数字。因此，我们还可以得出结论，如果数独满足以下任何条件，则认为数据被错误填充：

1. 任何行包含多次相同的数字。
2. 任何列都包含多次相同的数字。
3. 任何3x3子矩阵都具有不止一次的相同数字。

在回溯中，我们首先从一个子解决方案开始，如果这个子解决方案没有给我们一个正确的最终答案，那么我们回过头来改变我们的子解决方案。我们将以类似的方式解决我们的数独。我们将遵循的步骤是：

• 如果没有未分配的单元格，则数独已经解决。我们将回归真实。
• 否则，我们将使用1到9之间的数字填充未分配的单元格，以便在任何行，列或3x3子矩阵中不存在冲突。
• 现在，我们将尝试填充下一个未分配的单元格，如果这成功发生，那么我们将返回true。
• 否则，我们将返回并更改用于填充单元格的数字。如果没有满足需要的数字，那么我们将返回false，因为没有这个数独的解决方案。

所以，让我们编写代码吧。

class Sudoku { private static final int SIZE = 9; private static int[][] matrix = { {6 5 0 8 7 3 0 9 0} {0 0 3 2 5 0 0 0 8} {9 8 0 1 0 4 3 5 7} {1 0 5 0 0 0 0 0 0} {4 0 0 0 0 0 0 0 2} {0 0 0 0 0 0 5 0 3} {5 7 8 3 0 1 0 2 6} {2 0 0 0 4 8 9 0 0} {0 9 0 6 2 5 0 8 1} }; private static void printSudoku() { for(int i=0;i<SIZE;i ) { for(int j=0;j<SIZE;j ) { System.out.print(matrix[i][j] "\t"); } System.out.println(""); } } //function to check if all cells are assigned or not //if there is any unassigned cell //then this function will change the values of //row and col accordingly private static int[] numberUnassigned(int row int col) { int numunassign = 0; for(int i=0;i<SIZE;i ) { for(int j=0;j<SIZE;j ) { //cell is unassigned if(matrix[i][j] == 0) { //changing the values of row and col row = i; col = j; //there is one or more unassigned cells numunassign = 1; int[] a = {numunassign row col}; return a; } } } int[] a = {numunassign -1 -1}; return a; } //function to check if we can put a //value in a paticular cell or not private static boolean isSafe(int n int r int c) { //checking in row for(int i=0;i<SIZE;i ) { //there is a cell with same value if(matrix[r][i] == n) return false; } //checking column for(int i=0;i<SIZE;i ) { //there is a cell with the value equal to i if(matrix[i][c] == n) return false; } //checking sub matrix int row_start = (r/3)*3; int col_start = (c/3)*3; for(int i=row_start;i<row_start 3;i ) { for(int j=col_start;j<col_start 3;j ) { if(matrix[i][j]==n) return false; } } return true; } //function to solve sudoku //using backtracking private static boolean solveSudoku() { int row=0; int col=0; int[] a = numberUnassigned(row col); //if all cells are assigned then the sudoku is already solved //pass by reference because number_unassigned will change the values of row and col if(a[0] == 0) return true; //number between 1 to 9 row = a[1]; col = a[2]; for(int i=1;i<=SIZE;i ) { //if we can assign i to the cell or not //the cell is matrix[row][col] if(isSafe(i row col)) { matrix[row][col] = i; //backtracking if(solveSudoku()) return true; //if we can't proceed with this solution //reassign the cell matrix[row][col]=0; } } return false; } public static void main(String[] args) { if (solveSudoku()) printSudoku(); else System.out.println("No solution"); } } 代码说明

最初，我们只是为Sudoku制作一个矩阵，并用0填充未分配的单元格。因此，矩阵包含Sudoku问题，值为0的单元格是空白单元格。

print_sudoku() →这只是打印矩阵的功能。

number_unassigned →此函数找到一个空单元格，并使变量'row'和'col'等于该单元格的索引。在C中，我们使用指针来改变传递给该函数的变量（row，col）的值（通过引用传递）。在Java和Python中，我们返回一个包含这些值的数组（或Python列表）。所以，这个函数告诉我们是否有任何未分配的单元格。如果有任何未分配的单元格，那么此函数也会告诉我们该单元格的索引。

is_safe(int n int r int c)→此函数检查我们是否可以将值'n'放入单元格（r，c）中。我们这样做是首先检查行'r'中是否有任何单元格的值为'n'或不是 - if(matrix[r][i] == n)。然后我们检查在'c'列中是否有任何值为'n'的单元格 - if(matrix[i][c] == n)。最后，我们正在检查子矩阵。 (r/3)*3 给出了行r的起始索引。例如，如果'r'的值是2，那么它在从（0 0）开始的子矩阵中。同样，我们得到了起始列的值(c/3)*3。因此，如果一个单元格是（2 2），那么这个单元格将在一个从（0 0）开始的子矩阵中，我们得到这个值(c/3)*3和(r/3)*3。在获得起始索引之后，我们可以轻松地遍历子矩阵以检查我们是否可以将值'n'放在该子矩阵中。

solve_sudoku()→这是解决数独并使用回溯的实际功能。我们首先通过使用该number_unassigned函数检查是否有任何未分配的单元格 ，如果没有未分配的单元格，则解决数独。 number_unassigned 函数还给出了空单元的索引。因此，如果有任何空白单元格，那么我们将尝试用1到9之间的值填充此单元格。我们将使用它 is_safe 来检查是否可以填充该单元格中的特定值。找到一个值后，我们将尝试解决数独的其余部分solve_sudoku。如果此值无法解决其余问题，我们将返回并尝试此单元格的其他值matrix[row][col]=0;。循环将尝试单元格中的其他值。

整理不易，请大家多多收藏加关注 ，谢谢。