题目描述：
数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词“end”的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. end输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293 416837529982465371735129468571298643293746185864351297647913852359682714128574936分析： 搜索顺序：确定每一个’.‘格子能填哪些数，所以参数为u，dfs内for循环去枚举这一个格子能够填哪些数。 优化搜索顺序：每一次找到当前为’.'的且可填数最少的格子去填。 技巧：每一行，每一列，每个九宫格能够填的数，我们利用二进制数去表示，所以一个空格子能填的数为row & col & cell。 预处理：mp数组，记录1 ,10 ,100,1000…所对应的映射值1-9， ones数组，因为我们要找到可填数最少的格子，所以我们就要知道row & col & cell 的结果数所对应的方案是多少。
#include <iostream> using namespace std; const int N = 9; char s[100]; int row[N] , col[N] , cell[N/3][N/3]; int mp[1 << N]; // 求出1 10 100 1000...所对应的映射值 映射值为1 - 9 int ones[1 << N]; //求出每个值对应的能填多少个数 void init(){ for(int i = 0 ; i < N / 3 ; i ++) for(int j = 0 ; j < N / 3; j ++) cell[i][j] = row[i * 3 + j] = col[i * 3 + j] = (1 << N) - 1; } void change(int x ,int y , char c , bool flag){ int t = 1 << (c - '1'); if(flag == true) { row[x] -= t; col[y] -= t; cell[x / 3][y / 3] -= t; s[x * N + y] = c; } else { row[x] += t; col[y] += t; cell[x / 3][y / 3] += t; s[x * N + y] = '.'; } } int lowbit(int x){ return x & -x; } int get(int x ,int y){ return row[x] & col[y] & cell[x/3][y/3]; } bool dfs(int u ,int cnt){ if( u == cnt ) return true; int x , y , minnum = 10; for(int i = 0 ; i < N ; i ++)//找到可选数最少的格子 { for(int j = 0 ; j < N ; j ++) { if( s[i*N + j] == '.') { int t = ones[get(i,j)]; if( t < minnum ) { minnum = t ; x = i ; y = j; } } } } //枚举这个格子能填哪些数 for(int i = get(x,y) ; i != 0 ; i -= lowbit(i) ) { int t = lowbit(i); char number = mp[t] + '0' ; change(x , y , number , true); if( dfs(u + 1 , cnt) ) return true; change(x , y , number , false); } return false; } int main(){ for(int i = 0 ; i < N ; i ++ ) mp[1 << i] = i + 1; // 1 - > 1 , 10 - > 2 , 100 - > 3 ... for(int i = 0 ; i < 1 << N ; i ++ ) for(int j = 0 ; j < N ; j ++) ones[i] += i >> j & 1; //直接求出每个值对应的能填多少个数 while ( cin >> s , s[0] != 'e' ) { init(); int cnt = 0; //记录下有多少个待填的空格子 for(int i = 0 ; i < N ; i ++) for(int j = 0 ; j < N ; j ++) { int idx = i * N + j; if(s[idx] != '.') change(i,j,s[idx],true); else cnt ++; } dfs( 0 , cnt ); cout << s << endl; } return 0; }