C 语言：用 DFS 算法实现数独游戏求解

以下是一个使用深度优先搜索（DFS）算法来解决数独问题的 C 语言示例代码： ```c #include <stdio.h> #include <stdbool.h> #define N 9 // 检查在特定位置放置数字是否合法 bool isSafe(int grid[N][N], int row, int col, int num) { // 检查行中是否存在相同数字 for (int i = 0; i < N; i++) { if (grid[row][i] == num) { return false; } } // 检查列中是否存在相同数字 for (int i = 0; i < N; i++) { if (grid[i][col] == num) { return false; } } // 检查 3x3 子方格中是否存在相同数字 int startRow = row - row % 3; int startCol = col - col % 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (grid[i + startRow][j + startCol] == num) { return false; } } } return true; } // 递归函数来解决数独 bool solveSudoku(int grid[N][N]) { int row, col; // 找到未填充的位置 bool isEmpty = false; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (grid[row][col] == 0) { isEmpty = true; break; } } if (isEmpty) { break; } } // 如果没有未填充的位置，数独已解决 if (!isEmpty) { return true; } // 尝试填入 1 到 9 for (int num = 1; num <= 9; num++) { if (isSafe(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) { return true; } grid[row][col] = 0; } } return false; } // 打印数独网格 void printGrid(int grid[N][N]) { for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { printf("%d ", grid[row][col]); } printf("\n"); } } int main() { int grid[N][N] = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(grid)) { printf("数独解决方案:\n"); printGrid(grid); } else { printf("无法找到解决方案\n"); } return 0; } ``` 这段代码实现了一个简单的数独求解程序，使用深度优先搜索来尝试填入数字，并通过合法性检查来确定是否可以填入。 ######[AI写代码神器 | 990点数解答 | 2024-11-03 08:40:35]