题解 | #Sudoku#

#include <bits/stdc++.h>

/*
从左上角开始去遍历这个数独。

对于没有填入的格子（即格子数值为0），我们去枚举1～9每个数字填入，
然后根据数独的性质（同行、同列、同一个九宫格不能有相同数字）去判断填入。
如果可以成功填完所有格子那么就是找到了答案。
找到答案后可以用一个bool变量，然后注意在回溯的地方根据这个变量及时的return，
防止已经找到答案后又回溯为0。

对于初始化就有值的格子，我们往右走（列数值加一），
那么因为一行只有9个，所以当列走到头的时候，列的值变成0，行的值加1（其实就是换到了下一行的开头）。
*/

using namespace std;

const int N = 15;
int mp[N][N];//存储数独
bool findAnswerOk = false; //是否找到答案

//检验在当前位置填入val后，满足要求与否
bool check(int row, int col, int val){
    //同行
    for(int j = 0; j < 9; j++){
        if(mp[row][j] == val) return false;
    }
    
    //同列
    for(int i = 0; i < 9; i++){
        if(mp[i][col] == val) return false;
    }
    
    //同一个九宫格
    int rowLimit = (row / 3) * 3 + 3; //九宫格行的终点(1--9) //
    int colLimit = (col / 3) * 3 + 3; //九宫格列的终点(1--9) //
    for(int i = rowLimit - 3; i < rowLimit; i++){ //
        for(int j = colLimit - 3; j < colLimit; j++){ //
            if(mp[i][j] == val) return false;
        }
    }
    
    return true;
}

//dfs 当前行、列
void dfs(int row, int col){
    if(col == 9){//当前行结束(最多为8)
        row++; //下一行
        col = 0;
    }
    
    //终止条件 (遍历完了整个矩阵)
    if(row == 9 && col == 0){
        findAnswerOk = true; //找到了答案
        return;
    }
    
    if(mp[row][col] == 0){ //该位置还没填充数字
        for(int i = 1; i <= 9; i++){ //遍历检查数字是否能填充
            if(check(row, col, i)){
                mp[row][col] = i; //进行填充
                dfs(row, col + 1); //下一个
                
                if(findAnswerOk) return; //已经找到了答案，直接返回
                
                mp[row][col] = 0; //没有找到答案，回溯
            }
        }
    }
    else{
        dfs(row, col + 1); //已填充，直接下一个数字
    }
}

int main(){
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> mp[i][j];
        }
    }
    
    dfs(0, 0);//起点坐标（0，0）
    
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cout << mp[i][j] << ' ';
        }
        cout << endl;
    }
    
    return 0;
}