题目概述
给定一个数独，求最终填好的数独。（保证有唯一解）。
思路拆分
数独的要求有三个:行，列，九宫格无重复数字。
我们只用dfs搜索每一个点就行了。
由于整个数独可以划分为9个九宫格，
在处理九宫格时我们可以将其看作一个整体，如下图：
（1,1）（1,2）（1,3）
（2,2）（2,2）（2,3）
（3,1）（3,2）（3,3）
分析每个九宫格对应的下标后，我们就可以发现：
若当前点坐标为（i,j），则它位于c[i/3][j/3]这个九宫格内。
至于查重就更简单了，把c开到三维，第三维存数据。
（行、列处理很简单，此处不再多说）
核心代码+注释
#include<bits/stdc++.h>usingnamespacestd;inta[10][10];boolh[10][10];//处理行booll[10][10];//处理列boolc[5][5][10];//处理九宫格vector<pair<int,int>>b;boolcheck(intr,intx,inti){return!h[r][i]&&!l[x][i]&&!c[r/3][x/3][i];//检查当前位置是否可行}voiddfs(intidx){if(idx==(int)b.size())//递归终止条件{for(inti=0;i<9;i++){for(intj=0;j<9;j++){cout<<a[i][j]<<" ";//输出}cout<<endl;}exit(0);//注意：此处要直接退出，不能用return,否则dfs会继续搜索其他分支}intr=b[idx].first;intx=b[idx].second;for(inti=1;i<=9;i++){if(check(r,x,i)){a[r][x]=i;h[r][i]=l[x][i]=c[r/3][x/3][i]=true;//假设填这个数dfs(idx+1);a[r][x]=0;h[r][i]=l[x][i]=c[r/3][x/3][i]=false;//回溯}}}intmain(){for(inti=0;i<9;i++){for(intj=0;j<9;j++){cin>>a[i][j];if(a[i][j]!=0){h[i][a[i][j]]=l[j][a[i][j]]=c[i/3][j/3][a[i][j]]=true;}else{b.push_back({i,j});}}}dfs(0);return0;}
