简单数独
#include <stdio.h> #include<string.h> struct node{ int x,y; }p[90]; int map[10][10],num; bool success; bool OK(node P,int k){//P这个点填入k int i; for(i=0;i<9;i++)if(map[P.x][i]==k || map[i][P.y]==k)return false;//数字不重复 int x=(P.x/3)*3,y=(P.y/3)*3; for(i=x;i<x+3;i++) for(int j=y;j<y+3;j++) if(map[i][j]==k)return false; return true; } void DFS(int pnum){ if(success)return ; if(pnum==num){success=true;return ;} int x=p[pnum].x,y=p[pnum].y; for(int i=1;i<=9;i++) if(OK(p[pnum],i)) { map[x][y]=i; DFS(pnum+1); if(success)return ; map[x][y]=0; } } int main(){ int T,i,j;scanf("%d",&T); while(T--){ for(i=0;i<9;i++) { char s[10];scanf("%s",s); for(j=0;j<9;j++) map[i][j]=s[j]-'0'; } num=0; success=false; for(i=0;i<9;i++) for(j=0;j<9;j++) if(!map[i][j]) p[num].x=i,p[num++].y=j; DFS(0); for(i=0;i<9;i++) { for(j=0;j<9;j++) printf("%d",map[i][j]); printf("\n"); } } return 0; }