最开始模拟dfs进行计算 没有进行任何剪枝操作 仅仅可过70%的数据

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char a[9][9];

bool check(int x, int y, int num) {
    // 检查行重复
    for (int i = 0; i < 9; i++) {
        if (a[x][i] == num + '0') return false;
    }
    // 检查列重复
    for (int i = 0; i < 9; i++) {
        if (a[i][y] == num + '0') return false;
    }
    // 检查九宫格
    int startX = (x / 3) * 3;
    int startY = (y / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[startX + i][startY + j] == num + '0') return false;
        }
    }
    return true;
}
// bool found = false;

void dfs(int u) {
    // if (found) return;
    if (u == 81) {
        // found = true;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
        return;
}


    int x = u / 9;
    int y = u % 9;

    if (a[x][y] != '.') {
        dfs(u + 1);
    } else {
        for (int num = 1; num <= 9; num++) {
            if (check(x, y, num)) {
                a[x][y] = num + '0';
                dfs(u + 1);
                a[x][y] = '.';  // 回溯
            }
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        cin >> a[i];
    }
    dfs(0);
    return 0;
}

其次进行剪枝 判断当找到正确答案的时候后 我们的所有计算则可以直接return 因为只存在一个正确答案 可通过90%的数据

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char a[9][9];

bool check(int x, int y, int num) {
    // 检查行重复
    for (int i = 0; i < 9; i++) {
        if (a[x][i] == num + '0') return false;
    }
    // 检查列重复
    for (int i = 0; i < 9; i++) {
        if (a[i][y] == num + '0') return false;
    }
    // 检查九宫格
    int startX = (x / 3) * 3;
    int startY = (y / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[startX + i][startY + j] == num + '0') return false;
        }
    }
    return true;
}
 bool found = false;//增加bool数组判断是否找到了正确答案

void dfs(int u) {
     if (found) return;
    if (u == 81) {
         found = true;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
        return;
}


    int x = u / 9;
    int y = u % 9;

    if (a[x][y] != '.') {
        dfs(u + 1);
    } else {
        for (int num = 1; num <= 9; num++) {
            if (check(x, y, num)) {
                a[x][y] = num + '0';
                dfs(u + 1);
                a[x][y] = '.';  // 回溯
            }
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        cin >> a[i];
    }
    dfs(0);
    return 0;
}