问题描述：
数独问题
解题要点:
回溯时要恢复回溯之前的所有状态，一开始s数组回溯时忘了清零所以结果很奇怪
代码：
#include#include #include #include #include #include using namespace std;const int maxn = 10;char input[maxn][maxn];int s[maxn][maxn];int cubicrecord[maxn][maxn];int linerecord[maxn][maxn];int columnrecord[maxn][maxn];bool success = false;void dfs(int id);int main(){ //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int t,i,j,part; scanf("%d",&t); while(t--) { success = false; memset(cubicrecord,0,sizeof(cubicrecord)); memset(linerecord,0,sizeof(linerecord)); memset(columnrecord,0,sizeof(columnrecord)); memset(s,0,sizeof(s)); memset(input,0,sizeof(input)); for(i = 1; i < maxn;++i) { scanf("%s",input[i]); for(j = 1; j < maxn; ++j) { s[i][j] = input[i][j-1] - '0'; //scanf("%d",s[i]+j); part = ((i-1)/3)*3+((j-1)/3+1); //p[i][j] = part; cubicrecord[part][s[i][j]] = 1; linerecord[i][s[i][j]]=1; columnrecord[j][s[i][j]]=1; } } /*for(i = 1; i < maxn; ++i){ for(j = 1; j < maxn;++j){ printf("%d",p[i][j]); } printf("\n"); } return 0;*/ dfs(1); for(i = 1; i < maxn; ++i){ for(j = 1; j < maxn; ++j){ printf("%d",s[i][j]); } printf("\n"); } } return 0;}void dfs(int id){ if(success) return; int x = (id - 1) / 9 + 1; int y = (id - 1) % 9 + 1; int part = ((x-1)/3)*3+((y-1)/3+1); if(id == 81) { if(s[x][y]) { success = true; return; } for(int i = 1; i < maxn; ++i) { if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i])) { s[9][9] = i; success = true; break; } } return; } if(s[x][y]) //这个格子已经填完了 { dfs(id+1); if(success) return; } else { for(int i = 1; i < maxn; ++i) { if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i])) { s[x][y] = i; linerecord[x][i] = 1; columnrecord[y][i] = 1; cubicrecord[part][i] = 1; dfs(id+1); if(success) break; linerecord[x][i] = 0; columnrecord[y][i] = 0; cubicrecord[part][i] = 0; s[x][y] = 0; } } if(success) return; }}