经典数独问题
用DFS模拟数独解法，找摒除解和余数解
数独解法：
2676
#include "stdio.h"#include "string.h"struct node{int x,y;int s[10]; // 对于每个空格，数字i是否可用int sum; // 对于每个空格，一共可以填入的数字种数}order[101];int cnt; // 总空格数char str[101];int row[20][20],col[20][20],block[20][20]; //记录第i（行，列，小矩阵)的数字j是否已被占用int table[101][101]; // 大矩阵void init(){int i,x,y;char str[20];memset(row,0,sizeof(row));memset(col,0,sizeof(col));memset(block,0,sizeof(block));cnt=0;for (x=0;x<9;x++){scanf("%s",str);for (y=0;y<9;y++)if (str[y]=='0'){table[x][y]=0;order[cnt].x=x;order[cnt].y=y;cnt++;}else{table[x][y]=str[y]-'0';row[x][str[y]-'0']=1;col[y][str[y]-'0']=1;block[x/3*3+y/3][str[y]-'0']=1;}}}void updata(){int x,y,i,j,k;int oprow[10][10],opcol[10][10],opblock[10][10]; // 记录每行，列，小矩阵中数字k一共有几个可以放置的地方memset(oprow,0,sizeof(oprow));memset(opcol,0,sizeof(opcol));memset(opblock,0,sizeof(opblock));for (i=0;i<cnt;i++){x=order[i].x;y=order[i].y;if (table[x][y]==0){order[i].sum=0;memset(order[i].s,0,sizeof(order[i].s));for (k=1;k<=9;k++)if (row[x][k]==0 && col[y][k]==0 && block[x/3*3+y/3][k]==0){order[i].sum++;order[i].s[k]=1;oprow[x][k]++;opcol[y][k]++;opblock[x/3*3+y/3][k]++;}}}for(i=0;i<9;i++)for (k=1;k<=9;k++){if (oprow[i][k]==1) // 如果第i行能放置数字k的位置只有一个{for (j=0;j<cnt;j++)if (order[j].x==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}if (opcol[i][k]==1){for (j=0;j<cnt;j++)if (order[j].y==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}if (opblock[i][k]==1){for (j=0;j<cnt;j++)if (order[j].x/3*3+order[j].y/3==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}}}int getnow(){int temp,mark,i,x,y;temp=10;mark=-1;for (i=0;i<cnt;i++){x=order[i].x;y=order[i].y;if (table[x][y]==0 && order[i].sum<temp){temp=order[i].sum;mark=i;}}return mark;}int dfs(int w){int i,j,now,x,y,k;if (w==cnt){for (i=0;i<9;i++){for (j=0;j<9;j++)printf("%d",table[i][j]);printf("\n");}return 1;}now=getnow();if (now==-1) return 0;x=order[now].x;y=order[now].y;for (k=1;k<=9;k++)if (order[now].s[k]){row[x][k]=1;col[y][k]=1;block[x/3*3+y/3][k]=1;table[x][y]=k;updata();if (dfs(w+1)==1) return 1;row[x][k]=0;col[y][k]=0;block[x/3*3+y/3][k]=0;table[x][y]=0;updata();}return 0;}int main(){int i,j,t;scanf("%d",&t);getchar();while (t–){//if (strcmp(str,"end")==0) break;init();updata();dfs(0);}return 0;}
3074
#include "stdio.h"#include "string.h"struct node{int x,y;int s[10]; // 对于每个空格，数字i是否可用int sum; // 对于每个空格，一共可以填入的数字种数}order[101];int cnt; // 总空格数char str[101];int row[20][20],col[20][20],block[20][20]; //记录第i（行，列，小矩阵)的数字j是否已被占用int table[101][101]; // 大矩阵void init(){int i,x,y;memset(row,0,sizeof(row));memset(col,0,sizeof(col));memset(block,0,sizeof(block));cnt=0;for (i=0;i<81;i++){x=i/9;y=i%9;if (str[i]=='.'){table[x][y]=0;order[cnt].x=x;order[cnt].y=y;cnt++;}else{table[x][y]=str[i]-'0';row[x][str[i]-'0']=1;col[y][str[i]-'0']=1;block[x/3*3+y/3][str[i]-'0']=1;}}}void updata(){int x,y,i,j,k;int oprow[10][10],opcol[10][10],opblock[10][10]; // 记录每行，列，，小矩阵中数字k一共有几个可以放置的地方memset(oprow,0,sizeof(oprow));memset(opcol,0,sizeof(opcol));memset(opblock,0,sizeof(opblock));for (i=0;i<cnt;i++){x=order[i].x;y=order[i].y;if (table[x][y]==0){order[i].sum=0;memset(order[i].s,0,sizeof(order[i].s));for (k=1;k<=9;k++)if (row[x][k]==0 && col[y][k]==0 && block[x/3*3+y/3][k]==0){order[i].sum++;order[i].s[k]=1;oprow[x][k]++;opcol[y][k]++;opblock[x/3*3+y/3][k]++;}}}for(i=0;i<9;i++)for (k=1;k<=9;k++){if (oprow[i][k]==1) // 如果第i行能放置数字k的位置只有一个{for (j=0;j<cnt;j++)if (order[j].x==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}if (opcol[i][k]==1){for (j=0;j<cnt;j++)if (order[j].y==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}if (opblock[i][k]==1){for (j=0;j<cnt;j++)if (order[j].x/3*3+order[j].y/3==i && table[order[j].x][order[j].y]==0 && order[j].s[k]==1){order[j].sum=1;memset(order[j].s,0,sizeof(order[j].s));order[j].s[k]=1;break;}}}}int getnow(){int temp,mark,i,x,y;temp=10;mark=-1;for (i=0;i<cnt;i++){x=order[i].x;y=order[i].y;if (table[x][y]==0 && order[i].sum<temp){temp=order[i].sum;mark=i;}}return mark;}int dfs(int w){int now,x,y,k;if (w==cnt) return 1;now=getnow();if (now==-1) return 0;x=order[now].x;y=order[now].y;for (k=1;k<=9;k++)if (order[now].s[k]){row[x][k]=1;col[y][k]=1;block[x/3*3+y/3][k]=1;table[x][y]=k;updata();if (dfs(w+1)==1) return 1;row[x][k]=0;col[y][k]=0;block[x/3*3+y/3][k]=0;table[x][y]=0;updata();}return 0;}int main(){int i,j;while (scanf("%s",str)!=EOF){if (strcmp(str,"end")==0) break;init();updata();dfs(0);for (i=0;i<9;i++)for (j=0;j<9;j++)printf("%d",table[i][j]);printf("\n");}return 0;}
加油鼓励看好你，一天更比一天强
