单纯的dfs，用三个数组记录行、列以及3×3方格的情况。
只是一开始不知道为什么没办法结束程序的运行，提交两次TLE，感觉应该是getchar()的问题。
code:
#include<cstdio> #include<iostream> #include<cstring> using namespace std ; bool c[ 10][ 10] ; bool r[ 10][ 10] ; bool s[ 4][ 4][ 10] ; bool vis[ 10][ 10] ; char str[ 10] ; int data[ 10][ 10] ; bool flag ; int cur( int x){ if(x< 3) return 1 ; else if(x< 6) return 2 ; else return 3 ; } void dfs( int row, int col){ if(row== 9){ flag = true ; return ; } if(vis[row][col]){ if(col== 8) dfs(row+ 1, 0) ; else dfs(row, col+ 1) ; } else{ vis[row][col] = true ; for( int i= 1; i<= 9; i++){ if(flag) break ; if(!r[row][i]&&!c[col][i]&&!s[cur(row)][cur(col)][i]){ data[row][col] = i ; r[row][i] = true ; c[col][i] = true ; s[cur(row)][cur(col)][i] = true ; if(col== 8) dfs(row+ 1, 0) ; else dfs(row, col+ 1) ; r[row][i] = false ; c[col][i] = false ; s[cur(row)][cur(col)][i] = false ; } } vis[row][col] = false ; } } int main(){ int t, i, j ; scanf( " %d ", &t) ; while(t--){ memset(vis, false, sizeof(vis)) ; for(i= 0; i< 9; i++){ getchar() ; scanf( " %s ", str) ; for(j= 0; j< 9; j++){ data[i][j] = str[j] - ' 0 ' ; if(data[i][j]> 0) vis[i][j] = true ; } } memset(c, false, sizeof(c)) ; memset(r, false, sizeof(r)) ; memset(s, false, sizeof(s)) ; for(i= 0; i< 9; i++) for(j= 0; j< 9; j++){ if(data[i][j]> 0){ r[i][data[i][j]] = true ; c[j][data[i][j]] = true ; s[cur(i)][cur(j)][data[i][j]] = true ; } } flag = false ; dfs( 0, 0) ; for(i= 0; i< 9; i++){ for(j= 0; j< 9; j++) printf( " %d ", data[i][j]) ; printf( " \n ") ; } } return 0 ;
}