There is really only one rule:

Fill in the grid so thatevery row,every column, andevery 3 x 3 boxcontains the digits 1 through 9.這個游戲只有一個規則：將格子填滿使得每一行，每一列，和每一個小的九宮格恰好包含1-9這9個數字正是由于規則簡單而又變化多端，數獨一時間風靡全球。現在，我們希望你能編寫一個程序解決數獨問題。

輸入格式：

輸出格式：

樣例輸入：

5????7??6?6????5?4?834????????182?4???1???9???7?369????????543?1?5????9?7??2????1
樣例輸出：
514927386967831524283456179659182743321574968478369215892615437135748692746293851
時間限制：
1000
空間限制：
32768有時間再寫一個dancinglinks。  讀入很難，大家仔細體會一下。還可以加一個優化就是按每個格子已排除的數的個數從小到大排序后再搜。codevs上用inti（）讀入，輸出時加一個空格#include<bits/stdc++.h>using namespace std;int n,m;int sz[10][10];int heng[10][10],shu[10][10],jiu[4][4][10];void init(){int count=0;while (count<81){bool pg=0;char c;scanf("%c",&c);if (c=='?') count++;if(c>='1'&&c<='9'){count++;sz[(count-1)/9+1][count-((count-1)/9+1)*9+9]=c-'0';}}}void inti(){cin>>n;int xx,yy,zz;for(int i=1;i<=n;i++){cin>>xx>>yy>>zz;sz[xx][yy]=zz;}}void inin(){for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)cin>>sz[i][j];}void PRepare(){for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){heng[i][sz[i][j]]+=1;shu[j][sz[i][j]]+=1;jiu[((i-1)/3)+1][((j-1)/3)+1][sz[i][j]]+=1;}}//READYvoid print(){for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)cout<<sz[i][j];cout<<"/n";}}void dfs(int depth){if(depth>81) {print();return;}int x=(depth-1)/9+1,y=depth-x*9+9;int aa=(x-1)/3+1;int bb=(y-1)/3+1;if(sz[x][y]) {dfs(depth+1);return;}for(int i=1;i<=9;i++){if(heng[x][i]||shu[y][i]||jiu[aa][bb][i])continue;heng[x][i]++;shu[y][i]++;jiu[aa][bb][i]++;sz[x][y]=i;dfs(depth+1);heng[x][i]--;shu[y][i]--;jiu[aa][bb][i]--;sz[x][y]=0;}}void doit(){dfs(1);}int main(){init();//inti();// inin();prepare();doit();}