经典搜索问题，主要是时间上的优化，我用了三个辅助数组记录信息 row[i][k] = 1表示第i行数字k已经被使用，col[j][k] = 1表第j列数字k已经被使用，blo[i][k]表示第i个小九宫格中数字k已经被使用

还有很重要的一个优化（没有优化的话可能会超时，或者非常慢，像POJ讨论区里有很多说正着搜超时，倒着搜0ms，这的确是一个可以用的方法，但是有一定的随机性），每次填数字时，先扫描一遍整个矩阵，找出可选数字情况最少的那个0所在的地方，优先填这里，这样会使得搜索树尽可能的“瘦“一些，效果会非常明显

代码

/*
poj    2676
236K	0MS
*/ 

#include
  
   
#include
   
     #define MAXN 10 #define MAX_INT 2147483647 using namespace std; bool flag = false; int matrix[MAXN][MAXN], row[MAXN][MAXN], col[MAXN][MAXN], blo[MAXN][MAXN]; //用int判断比bool判断要快！ int area[MAXN][MAXN] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}, {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}, {0, 7, 7 ,7, 8, 8, 8, 9, 9, 9} }; void solve(int cnt) { if(flag) return ; if( !cnt ) { flag = true; for(int i = 1;i <= 9;i ++) { for(int j = 1;j <= 9;j ++) cout<
    
     >cases; while(cases --) { memset(row, 0, sizeof(row)); memset(col, 0, sizeof(col)); memset(blo, 0, sizeof(blo)); memset(matrix, 0, sizeof(matrix)); flag = false; cnt = 0; for(int i = 1;i <= 9;i ++) { for(int j = 1;j <= 9;j ++) { char ch; cin>>ch; matrix[i][j] = ch - '0'; row[i][matrix[i][j]] = 1; col[j][matrix[i][j]] = 1; blo[area[i][j]][matrix[i][j]] = 1; if( !matrix[i][j] ) cnt ++; } } solve(cnt); } return 0; }