求同个问题，c语言（或c++）的解决方案

题目：
数独问题：9*9的矩阵，要求每一行，每一列，每个九宫格都是1-9这九个数字且不能重复。

给定一9*9矩阵，里面有部分数空缺，要求找出满足上述要求的一个矩阵。

这个应该用穷举法吧，示例程序如下：

#include <stdio.h>

#define SIZE 9

// 检查数字num是否可以放置在指定的行、列或九宫格中
int checkPut(int matrix[SIZE][SIZE], int row, int col, int num) {
    // 检查行
    for (int i = 0; i < SIZE; i++) {
        if (matrix[row][i] == num) {
            return 0;
        }
    }

    // 检查列
    for (int i = 0; i < SIZE; i++) {
        if (matrix[i][col] == num) {
            return 0;
        }
    }

    // 检查九宫格是否合法
    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 (matrix[i + startRow][j + startCol] == num) {
                return 0;
            }
        }
    }

    return 1;
}

// 在空白位置尝试放置数字
int solveSudoku(int matrix[SIZE][SIZE]) {
    int row, col;

    // 查找下一个空白位置
    int found = 0;
    for (row = 0; row < SIZE; row++) {
        for (col = 0; col < SIZE; col++) {
            if (matrix[row][col] == 0) {
                found = 1;
                break;
            }
        }
        if (found) {
            break;
        }
    }

    // 如果没有空白位置，说明已经解决
    if (!found) {
        return 1;
    }

    // 尝试放置数字1-9
    for (int num = 1; num <= SIZE; num++) {
        if (checkPut(matrix, row, col, num)) {
            matrix[row][col] = num;

            // 递归解决剩余部分
            if (solveSudoku(matrix)) {
                return 1;
            }

            // 如果不能找到合适的解决方案，回溯并尝试下一个数字
            matrix[row][col] = 0;
        }
    }

    return 0;
}

// 打印数独矩阵
void printSudoku(int matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

// 检查输入是否合法
int checkValid(int matrix[SIZE][SIZE]) {
    // 检查每一行是否合法
    for (int i = 0; i < SIZE; i++) {
        int used[SIZE] = {0};
        for (int j = 0; j < SIZE; j++) {
            if (matrix[i][j] != 0 && used[matrix[i][j] - 1] == 1) {
                printf("第%d行有重复数字\n", i + 1);
                return 0;
            }
            used[matrix[i][j] - 1] = 1;
        }
    }

    // 检查每一列是否合法
    for (int i = 0; i < SIZE; i++) {
        int used[SIZE] = {0};
        for (int j = 0; j < SIZE; j++) {
            if (matrix[j][i] != 0 && used[matrix[j][i] - 1] == 1) {
                printf("第%d列有重复数字\n", i + 1);
                return 0;
            }
            used[matrix[j][i] - 1] = 1;
        }
    }

    // 检查每一个九宫格是否合法
    for (int i = 0; i < SIZE; i += 3) {
        for (int j = 0; j < SIZE; j += 3) {
            int used[SIZE] = {0};
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 3; l++) {
                    if (matrix[i + k][j + l] != 0 && used[matrix[i + k][j + l] - 1] == 1) {
                        printf("[%d][%d]开头的九宫格有重复数字\n", i, j);
                        return 0;
                    }
                    used[matrix[i + k][j + l] - 1] = 1;
                }
            }
        }
    }

    return 1;
}

int main() {
    int matrix[SIZE][SIZE];

    printf("请输入9x9的数独矩阵（用空格分隔数字，空白位置用0表示）：\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    // 检查输入是否合法
    if (checkValid(matrix) == 0) {
        printf("输入的数独矩阵不合法。\n");
        return 1;
    }

    if (solveSudoku(matrix)) {
        printf("\n找到的解决方案为：\n");
        printSudoku(matrix);
    } else {
        printf("\n无法找到解决方案。\n");
    }

    return 0;
}

以下是数独C++, 无输出

class Solution {
private:
    bool row[9][9];
    bool col[9][9];
    bool block[3][3][9];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void dfs(vector<vector<char>>& board, int p) {
        if (p == spaces.size()) {
            valid = true;
            return;
        }

        auto [i, j] = spaces[p];
        for (int num = 0; num < 9 && !valid; num++) {
            if (!row[i][num] && !col[j][num] && !block[i / 3][j / 3][num]) {
                row[i][num] = col[j][num] = block[i / 3][j / 3][num] = true;
                board[i][j] = num + '0' + 1;
                dfs(board, p + 1);
                row[i][num] = col[j][num] = block[i / 3][j / 3][num] = false;
            }
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, false, sizeof(row));
        memset(col, false, sizeof(col));
        memset(block, false, sizeof(block));
        valid = false;

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                } else {
                    int num = board[i][j] - '0' - 1;
                    row[i][num] = col[j][num] = block[i / 3][j / 3][num] = true;
                }
            }
        }

        dfs(board, 0);
    }
};

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

思路：

1. 定义一个9*9的二维数组表示数独矩阵，矩阵中空缺的位置可以用0表示。

2. 编写一个函数判断某个数字在当前行、列、九宫格中是否重复出现。

3. 编写一个递归函数，在矩阵中找到一个空缺位置，依次填入1-9的数，检查是否符合要求，如果符合要求继续递归填下一个空缺位置，否则回溯到上一个位置重新填数。

4. 最终找到一个符合要求的矩阵即为所求。

代码示例：

#include <iostream>
using namespace std;

const int N = 9;

int sudoku[N][N] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0}
};

bool check(int x, int y, int k) {
    for (int i = 0; i < N; i++) {
        if (sudoku[x][i] == k || sudoku[i][y] == k) {
            return false;
        }
    }
    int sx = x / 3 * 3, sy = y / 3 * 3;
    for (int i = sx; i < sx + 3; i++) {
        for (int j = sy; j < sy + 3; j++) {
            if (sudoku[i][j] == k) {
                return false;
            }
        }
    }
    return true;
}

bool solve(int x, int y) {
    if (x == N) {
        return true;
    }
    if (y == N) {
        return solve(x + 1, 0);
    }
    if (sudoku[x][y] != 0) {
        return solve(x, y + 1);
    }
    for (int k = 1; k <= 9; k++) {
        if (check(x, y, k)) {
            sudoku[x][y] = k;
            if (solve(x, y + 1)) {
                return true;
            }
            sudoku[x][y] = 0;
        }
    }
    return false;
}

int main() {
    // 读入数独矩阵
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> sudoku[i][j];
        }
    }
    // 解决数独问题
    if (solve(0, 0)) {
        // 输出解决方案
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << sudoku[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No solution!" << endl;
    }
    return 0;
}