题干描述 就是一个数独问题
这道题说是简单题，但是我觉得这个“简单”是在对数据结构，递归非常熟悉的基础上，对于我这种新手其实并不简单，也有很多坑等我我去踩
这道题说是剪枝，但是我觉得主要妙点还是好在gw老师的设置的数据结构太好了。见代码。
当要在一个空格子（0）放数字时，直接放那些在这个空格子所在行、列、3*3小方框没出现过的数字，这样效率不就高了许多吗？
但是，找到这些已经出现过的数字呢？记录下来？或者搜索一下？dwd
gw老师的办法很棒，这里面有一个重要的启发是：当题目要频繁查找某个位置的元素的状态，例如本题中我们要频繁的查找某位置其所在行、列、3*3小方框是否包含某数字，这时就可以用位置做数组下标，用值记录状态（0，1），这样直接访问数组就获得了所需信息，不必查找。
从这一题我认识到，我对递归的过程仍然不熟悉，特别是回溯，但是不能浮躁，不能气馁，慢慢来~
ac代码：
#include <cstring> #include <iostream> #include <vector> using namespace std; #define maxn 102 int hn[10][10]; //记录，某行中是否存有某个数 int ln[10][10]; int gn[10][10]; int map[10][10]; //地图 struct pos{ int r,c; pos(int rr,int cc):r(rr),c(cc){} }; vector<pos> b; inline int gb(int r,int c){ //由行列号得到序号（1~81） int rr=r/3; int cc=c/3; return rr*3+cc; } void saf(int i,int j,int num,int f){ //第f=1-->i行j列有num这个数，f=0意思相反 hn[i][num]=f; ln[j][num]=f; gn[gb(i,j)][num]=f; } bool isk(int i,int j,int num){ //num这个数放在i,j位置ok吗？ return !gn[gb(i,j)][num] && !hn[i][num] && !ln[j][num]; } int dfs(int n){ if(n<0) return 1; //从80->0 当n=-1代表前面0-80全部处理过 int r=b[n].r; int c=b[n].c; for(int i=1;i<=9;++i){ if(isk(r,c,i)){ map[r][c]=i; saf(r,c,i,1); if(dfs(n-1)) return 1; else saf(r,c,i,0); //回溯 } } return 0; } int main() { freopen("in.txt","r",stdin); int t; cin>>t; while(t--){ memset(hn,0,sizeof(hn)); memset(ln,0,sizeof(ln)); memset(gn,0,sizeof(gn)); b.clear(); for(int i=0;i<9;i++) for(int j=0;j<9;j++){ char c; cin>>c; map[i][j]=c-'0'; if(map[i][j]) saf(i,j,map[i][j],1); else b.push_back(pos(i,j)); } if(dfs(b.size()-1)){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++) cout<<char(map[i][j]+'0'); cout<<endl; } } } return 0; }