problem
- 補全9*9的數獨
- 滿足每行，每列，每個3*3方格內1~9均只出現一次
solution
1、答案
- 狀態：我們關心數獨每個位置填了什么數。我們需要在每個狀態中找出沒有填的位置，檢查有哪些值可以填。這些可以填的值構成了向下遞歸的分支。（狀態就是每個每個時刻的9*9數獨）
- 搜索邊界：1、所有位置填完了，找到答案。2、發現某個位置沒有能填的值，搜索失敗。
- 提醒：對于每個狀態下，我們要找的是1個位置填什么，而不是枚舉所有位置和能填的數（其他位置會在更深的地方被搜索到）。
2、剪枝
- 優化搜索順序：如果是人類玩數獨，策略一定是先填上“已經能夠唯一確定的位置”，考慮在該位置填什么數，再向下搜索。所以我們在每個狀態下選擇所有未填的位置中，能填合法數字最少的位置，考慮在這上面填數。
3、位運算
- 對于每行，每列，每個九宮格，分別用一個9為二進制數保存哪些數字還可以填。
- 對于每個位置，把他鎖在的行，列，九宮格對應的數取 & 運算就可以得到剩余哪些數可以填。lowbit(x)取出能填的數。
- 當某個位置的數填上時把對應的行，列，九宮格對應位置改為0。
codes
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;char str[10][10];
int row[10], col[10], grid[9], cnt[512], num[512], tot;
inline int g(int x, int y){return ((x / 3) * 3) + (y / 3);//在第幾個九宮格
}
inline void flip(int x, int y, int z){row[x] ^= 1<<z; //x行z不能填了col[y] ^= 1<<z;grid[g(x,y)] ^= 1<<z;
}bool dfs(int now){//剩余要填的數的總數if(now == 0)return 1;//優化順序：枚舉每個位置,找能填的最少的填int t = 10, x, y;for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(str[i][j] != '0')continue;int val = row[i] & col[j] & grid[g(i,j)];if(!val)return 0;if(cnt[val] < t){t = cnt[val];x = i, y = j;}}}//填數int val = row[x] & col[y] & grid[g(x,y)];for(; val; val -= val&-val){int z = num[val&-val];//能填的數str[x][y] = '1'+z;flip(x,y,z);if(dfs(now-1))return 1;flip(x,y,z);str[x][y] = '0';}return 0;
}int main(){//每個狀態已經填的數有幾個for(int i = 0; i < 1<<9; i++)for(int j = i; j; j-=j&-j)cnt[i]++;//對于狀態(1<<i),對應的數為'1'+num[1<<i];for(int i = 0; i < 9; i++)num[1<<i] = i;int T; cin>>T;while(T--){//data infor(int i = 0; i < 9; i++)scanf("%s",str[i]);//初始化，都可以填。for(int i = 0; i < 9; i++)row[i] = col[i] = grid[i] = (1<<9)-1;tot = 0;//for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++)if(str[i][j] != '0')flip(i,j,str[i][j]-'1');else tot++;dfs(tot);//data outcout<<'\n';for(int i = 0; i < 9; i++)printf("%s\n",str[i]);}return 0;
}
