题解 | #Sudoku#

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

const int N = 9;
int  arrVect[N][N];
bool flag = false;

/*检测当前的值是否满足需求*/
bool check(int row, int col, int val) {
    // 同行不能出现重复
    for(int i = 0; i < 9; i++) {
        if(arrVect[row][i] == val) {
            return false;
        }
    }
    // 同列不能出现重复
    for(int i = 0; i < 9; i++) {
        if(arrVect[i][col] == val) {
            return false;
        }
    }
    
    //同一个9宫格不能出现重复
    int threeRow = row / 3 * 3 + 3; // 输入0~2，输出为3，输入3，输出6
    int threeCol = col / 3 * 3 + 3;
    for(int i = threeRow - 3; i < threeRow; i++) {
        for(int j = threeCol - 3; j < threeCol; j++) {
            if (arrVect[i][j] == val) {
                return false;
            }
            
        }
    }
    return true;
}
/*
思路：将9*9二维数组隔离成3*3的二维数组，若查找是含有0且1-9缺少的值，其值替换0。把3*3的二维数组重新组合9*9数组
*/
void DFS(int row, int col)
{
    if(col == 9) { //列的末尾，重现起一行
        row++;
        col = 0;
    }
    if(row == 9 && col == 0) { //遍历结束
        flag = true;
        return;
    }
    if(arrVect[row][col] == 0) {
        for(int i = 1; i <= 9; i++) {
            if(check(row, col, i)) {
                arrVect[row][col] = i;
                DFS(row, col + 1);
                if(flag) { //已经找到答案，直接返回
                    return;
                }
                 arrVect[row][col]  = 0; //没有查找到，回溯
            }
        }
    } else {
        DFS(row, col + 1);
    }
}

int main()
{
    int n = 9;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin>>arrVect[i][j];
        }
    }
    DFS(0, 0); //坐标起点
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout<<arrVect[i][j]<< ' ';
        }
        cout<<endl;
    }
}