这几天微博上面有条信息,说某数学家花了几个月发现了个数独的问题,只有一种解法,反正就是很难解。我把我几年前写的解数独的程序来跑了下,一瞬间就出来。现在把代码贴出来,顺便说下思路。
这个其实随便一个搞了ACM的很快就可以写出来。
#include "stdio.h" int R[9]; int C[9]; int G[9]; int M[9][9]; bool dfs(int x,int y) { if(x == 9) { for (int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { printf("%d ", M[i][j] + 1); } printf("\n"); } printf("OK"); return true; } if(M[x][y] != -1) { return dfs(x+(y+1)/9,(y+1)%9); } int z = x/3*3 + y/3; int e = C[x]|R[y]|G[z]; if(e == 511) return false; for(int i = 0; i < 9; i++) { if ((e|(1<<i)) != e) { C[x] |= 1<<i; R[y] |= 1<<i; G[z] |= 1<<i; int old = M[x][y]; M[x][y] = i; if(dfs(x+(y+1)/9,(y+1)%9)) return true; M[x][y] = old; C[x] ^= 1<<i; R[y] ^= 1<<i; G[z] ^= 1<<i; } } return false; } int main() { int num; char row[10]; for (int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { M[i][j] = -1; } } for(int i = 0;i < 9;i++) { scanf("%s",row); for(int j = 0;j < 9;j++) { if(row[j] != '?') { num = row[j]-'1'; M[i][j] = num; R[j] |= 1<<num; C[i] |= 1<<num; G[i/3*3 + j/3] |= 1<<num; } } } dfs(0, 0); while(1); return 0; }
我觉得值得一提的是里面的状态压缩。
R[], C[]数组里面的一个数表示某行,某列已经出现的数字,R[0]表示第一行(列)已经出现的数,用一个bit表示某位是否出现,因此只用到了最低的9bit。
G[]表示每个3*3格子出现了的数。
M[][]表示当前已经填了的局面,如果为-1表示该位未知,则从小到大试添格子所在的行,列,3*3格子都没有出现的数字。状态压缩后则行,列,3*3已出现的数字简单用或就可以算出来。