链接：https://ac.nowcoder.com/acm/problem/24911
来源：牛客网

题目描述

数独是一种填数字游戏，英文名叫 Sudoku，起源于瑞士，上世纪 70 年代由美国一家数学逻辑游戏杂志首先发表，名为 Number Place，后在日本流行，1984 年将 Sudoku 命名为数独，即 “独立的数字” 的缩写，意思是 “在每一格只有一个数字”。
2004 年，曾任中国香港高等法院法官的高乐德 (Wayne Gould) 把这款游戏带到英国，成为英国流行的数学智力拼图游戏。

玩家需要根据 9x9 盘面上的已知数字，推理出所有剩余位置的数字，并满足每一行、每一列、每一个粗线九宫格内的数字包含有 1-9 的数字，且不重复。
现在给你一个数独，请你解答出来。每个数独保证有且只有一个解。

输入描述: 

输入仅一组数据，共 9 行 9 列，表示初始数独（其中 0 表示数独中的空位）。

输出描述: 

输出共 9 行 9 列，表示数独的解。
注意⾏末没有空格。
因为求唯一解-->用DFS解决，使用回溯法
注意DFS递归到最大深度时就直接输出，不要递归完了再输出
DFS的一层递归判断条件为：这个数字在这一列，这一行，这一个小格内均未出现。
DFS的递归结束条件为：全部空缺的数字已填入
注：这里有一个小技巧，用于方便的判断某个数字属于哪一个小格内，就是打表（看tabl[10][10]数组，用于表示位置为mp[x][y]的数字属于哪一个小格）
虽然也可以用其他方法判断，但是这个更加方便直观一些

代码如下：
#include<bits/stdc++.h>
using namespace std;
int mp[10][10]; //存储数独的图 
int tabl[10][10]= {{0,0,0,0,0,0,0,0,0,0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
}; //打表，方便判断小格
int hang[10][10],lie[10][10],xiaoge[10][10]; //行，列，小格的判断数组（0为未填，1为已填） 
struct node{
    int x,y;
};
vector<node>d;
void print(){
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            if(j==1) printf("%d",mp[i][j]);
            else printf(" %d",mp[i][j]);
        }
        printf("\n");
    }
}
void DFS(int n) { //n表示已经遍历完的格子，即遍历到第n+1个格子 
    if(n==d.size()){
        print(); //这里直接输出，不要递归完了再输出
        return;
    }
    node tmp=d[n];
    int xx=tmp.x;
    int yy=tmp.y;
    for(int i=1;i<=9;i++){
        if(!hang[xx][i] && !lie[yy][i] && !xiaoge[tabl[xx][yy]][i]){ //如果数字i同一行，同一列，同一小格都未出现，那么可以填入 
            hang[xx][i]=1;
            lie[yy][i]=1;
            xiaoge[tabl[xx][yy]][i]=1;
            mp[xx][yy]=i;
            DFS(n+1); //第n+1个格子好了，遍历第n+2个格子 
            hang[xx][i]=0; //回溯 
            lie[yy][i]=0;
            xiaoge[tabl[xx][yy]][i]=0;
        }
    }
}
int main() {
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            scanf("%d",&mp[i][j]);
            if(!mp[i][j]){
                d.push_back(node{i,j}); //将值为0的格子存入d中 
            }else{
                hang[i][mp[i][j]]=1; //第i行的mp[i][j]的值已被填过 
                lie[j][mp[i][j]]=1; //第j列的mp[i][j]的值已被填过 
                xiaoge[tabl[i][j]][mp[i][j]]=1; //第i个小方格中mp[i][j]已被填过 
            }
        }
    }
    DFS(0); //已经遍历完0个格子，即遍历到第一个格子 
    return 0;
}