题解 | Sudoku

回溯算法

可以看看代码随想录的实现思路：

https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

本题思路与之类似，只不过是将需要填空的点单独收集起来，避免频繁遍历不必要的元素

#include <array>
#include <iostream>
#include <vector>
using namespace std;

// 校验是否可以在数独矩阵的 point 处插入 num
bool check(const array<array<int, 9>, 9>& mertix, pair<int, int> point, int num){
    // 判断行是否满足
    for(int j = 0; j < 9; ++j){
        if(mertix[point.first][j] == num) return false; 
    }

    // 判断列是否满足
    for(int i = 0; i < 9; ++i){
        if(mertix[i][point.second] == num) return false;
    }

    // 判断 3 * 3 粗线宫是否满足
    int x = (point.first / 3) * 3;
    int y = (point.second / 3) * 3;
    for(int i = x; i < x + 3; ++i){
        for(int j = y; j < y + 3; ++j){
            if (mertix[i][j] == num)
                return false;
        }
    }

    return true;
}

vector<pair<int, int>> points;

// 回溯算法
bool traceback(array<array<int, 9>, 9>& mertix, int point_index){
    if(point_index == points.size()) return true;

    for(int num = 1; num <= 9; ++num){
        pair<int, int> point = points[point_index];
        if(!check(mertix, point, num)) continue;

        mertix[point.first][point.second] = num;
        if(traceback(mertix, point_index + 1)) return true;
        mertix[point.first][point.second] = 0;
    }

    return false;
}

int main() {
    // 9 * 9 矩阵
    array<array<int, 9>, 9> mertix;
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            cin >> mertix[i][j];
            if(mertix[i][j] == 0) points.emplace_back(i, j);
        }
    }

    traceback(mertix, 0);

    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            cout << mertix[i][j] << " ";
        }
        cout << endl;
    }
}