用一個數組把空位記錄下來，直接搜索就好了
#include <cstdio>#include <cstring>struct node{ int x,y;};node ns[100];int len;char g[10][10];bool flag;bool check(int k, int index){ int x = ns[index].x; int y = ns[index].y; int cx = (x/3)*3+1; int cy = (y/3)*3+1;//當前所在子矩陣的中心坐標 int mark = false; for(int i = 0; i < 9; ++i) { if(g[x][i] == k) { mark = true; break; } if(g[i][y] == k) { mark = true; break; } } if(mark) return false; if(g[cx][cy] == k || g[cx-1][cy-1] == k || g[cx-1][cy] == k || g[cx][cy-1] == k || g[cx+1][cy] == k || g[cx][cy+1] == k || g[cx-1][cy+1] == k || g[cx+1][cy-1] == k || g[cx+1][cy+1] == k) mark = true; if(mark) return false; return true;}void DFS(int index){ if(index == len) { flag = true; return; } for(int k = 1; k <= 9; ++k) { if(check(k+'0',index)) { g[ns[index].x][ns[index].y] = k+'0'; DFS(index+1); if(flag) return; g[ns[index].x][ns[index].y] = '0'; } }}int main(){ int t; scanf("%d",&t); while(t--) { flag = false; len = 0; for(int i = 0; i < 9; ++i) for(int j = 0; j < 9; ++j) { scanf(" %c",&g[i][j]); if(g[i][j] == '0') { ns[len].x = i; ns[len].y = j; ++len; } } DFS(0); for(int i = 0; i < 9; ++i) { for(int j = 0; j < 9; ++j)新聞熱點
疑難解答
