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

#include <stdio.h> #define N 9 int isSafe(int board[N][N], int row, int col, int num) { // Check row for (int i = 0; i < N; i++) { if (board[row][i] == num) { return 0; } } // Check column for (int i = 0; i < N; i++) { if (board[i][col] == num) { return 0; } } // Check subgrid 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 (board[i+startRow][j+startCol] == num) { return 0; } } } return 1; } int solveSudoku(int board[N][N]) { int row, col; int num = 1; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (board[row][col] == 0) { // Try placing a number in the cell for (num = 1; num <= N; num++) { if (isSafe(board, row, col, num)) { board[row][col] = num; if (solveSudoku(board)) { return 1; } // Backtrack board[row][col] = 0; } } return 0; } } } return 1; } void printSudoku(int board[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", board[i][j]); } printf("\n"); } } int main() { int board[N][N] = { {3, 0, 6, 5, 0, 8, 4, 0, 0}, {5, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 8, 7, 0, 0, 0, 0, 3, 1}, {0, 0, 3, 0, 0, 0, 1, 8, 0}, {9, 0, 0, 8, 6, 3, 0, 0, 5}, {0, 5, 0, 0, 9, 0, 6, 0, 0}, {1, 3, 0, 0, 0, 0, 2, 5, 0}, {0, 0, 0, 0, 0, 0, 0, 7, 4}, {0, 0, 5, 2, 0, 6, 3, 0, 0} }; if (solveSudoku(board)) { printf("Solution:\n"); printSudoku(board); } else { printf("No solution exists\n"); } return 0; } ######[AI写代码神器 | 1464点数解答 | 2024-11-03 08:41:00]