#include <stdio.h>

#define SIZE 9

// 打印數(shù)獨(dú)棋盤
void printBoard(int board[SIZE][SIZE]) {
 ? ?printf("-------------------------\n");
 ? ?for (int i = 0; i < SIZE; i++) {
 ? ? ? ?if (i % 3 == 0 && i != 0) {
 ? ? ? ? ? ?printf("|-------|-------|-------|\n");
 ? ? ? ?}
 ? ? ? ?printf("| ");
 ? ? ? ?for (int j = 0; j < SIZE; j++) {
 ? ? ? ? ? ?if (j % 3 == 0 && j != 0) {
 ? ? ? ? ? ? ? ?printf("| ");
 ? ? ? ? ? ?}
 ? ? ? ? ? ?printf("%d ", board[i][j]);
 ? ? ? ?}
 ? ? ? ?printf("|\n");
 ? ?}
 ? ?printf("-------------------------\n");
}

// 檢查在指定位置放置數(shù)字是否合法
int isSafe(int board[SIZE][SIZE], int row, int col, int num) {
 ? ?// 檢查行是否合法
 ? ?for (int i = 0; i < SIZE; i++) {
 ? ? ? ?if (board[row][i] == num) {
 ? ? ? ? ? ?return 0;
 ? ? ? ?}
 ? ?}

 ? ?// 檢查列是否合法
 ? ?for (int i = 0; i < SIZE; i++) {
 ? ? ? ?if (board[i][col] == num) {
 ? ? ? ? ? ?return 0;
 ? ? ? ?}
 ? ?}

 ? ?// 檢查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 (board[i + startRow][j + startCol] == num) {
 ? ? ? ? ? ? ? ?return 0;
 ? ? ? ? ? ?}
 ? ? ? ?}
 ? ?}

 ? ?return 1; // 數(shù)字合法
}

// 查找空白位置
int findEmptyLocation(int board[SIZE][SIZE], int *row, int *col) {
 ? ?for (*row = 0; *row < SIZE; (*row)++) {
 ? ? ? ?for (*col = 0; *col < SIZE; (*col)++) {
 ? ? ? ? ? ?if (board[*row][*col] == 0) {
 ? ? ? ? ? ? ? ?return 1; // 找到空白位置
 ? ? ? ? ? ?}
 ? ? ? ?}
 ? ?}
 ? ?return 0; // 未找到空白位置
}

// 解決數(shù)獨(dú)謎題
int solveSudoku(int board[SIZE][SIZE]) {
 ? ?int row, col;
 ? ?if (!findEmptyLocation(board, &row, &col)) {
 ? ? ? ?return 1; // 數(shù)獨(dú)已經(jīng)解決
 ? ?}

 ? ?// 嘗試填充數(shù)字
 ? ?for (int num = 1; num <= SIZE; num++) {
 ? ? ? ?if (isSafe(board, row, col, num)) {
 ? ? ? ? ? ?board[row][col] = num;

 ? ? ? ? ? ?if (solveSudoku(board)) {
 ? ? ? ? ? ? ? ?return 1; // 數(shù)獨(dú)已經(jīng)解決
 ? ? ? ? ? ?}

 ? ? ? ? ? ?board[row][col] = 0; // 回溯
 ? ? ? ?}
 ? ?}

 ? ?return 0; // 無(wú)解
}

int main() {
 ? ?int board[SIZE][SIZE] = {
 ? ? ? ?{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}
 ? ?};

 ? ?printf("數(shù)獨(dú)謎題:\n");
 ? ?printBoard(board);
 ? ?printf("\n");

 ? ?if (solveSudoku(board)) {
 ? ? ? ?printf("解決后的數(shù)獨(dú):\n");
 ? ? ? ?printBoard(board);
 ? ?} else {
 ? ? ? ?printf("無(wú)解。\n");
 ? ?}

 ? ?return 0;
}