poj 3074 Sudoku(Dancing Links)

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

题意：

就是经典的数独问题。

思路：

搜索。

可是得借助Dancing Links加速。关键就在于如何把数独问题抽象成一个精确覆盖问题了。

我们首先考虑数独的游戏规则。

1.每一个格子都必须填一个数字。

2.每一行1-9这几个数字都必须出现一次。

3.每一列1-9这几个数字都必须出现一次。

4.每一宫格1-9这几个数字都必须出现一次。

我们知道Dancing Links的精确覆盖智能处理0,1的序列覆盖每一列为一个约束条件。

那么我们就必须把上述约束转换成0,1矩阵。

对于1。

我们用第(i-1)*9+j列为1表示i行j列的已经填数。一共占用81列。

对于2.我们用81+(i-1)*9+v列表示第i行已经有v这个值。一共占用81列。

对于3.我们用162+(j-1)*9+v列表示第j列已经有v这个值。一共占用81列。

对于3.我们用243+(3*((i-1)/3)+(j+2)/3-1)+v列表示第3*((i-1)/3)+(j+2)/3宫格已经有v这个值。一共占用81列。

ps:i,j都从1開始。3*((i-1)/3)+(j+2)/3为通过i,j确定的宫格数。

这样就会为每一个宫格确定一个01序列约束。

然后建好矩阵后。

套上精确覆盖模板后就ok了。

具体见代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int INF=0x3f3f3f3f;const int maxn=3645;//每一个格子可能有9个取值。
所以最多有81*9行。然后243列。
int U[maxn],D[maxn],L[maxn],R[maxn],C[maxn],row[maxn];//上下左右指针。c[i]结点i相应的列。row[i]结点i相应的行号。
int S[350],H[800],ans[100];//S[i]为i列1的个数。
H[i]为i行的尾指针。
int n,m,cnt,deep;struct node{    int x,y,v;} st[maxn];char maze[150],path[150];void init(){    int i;    for(i=1;i<=800;i++)        H[i]=-1;    for(i=0;i<=324;i++)    {         S[i]=0;         L[i+1]=i;         R[i]=i+1;         U[i]=D[i]=i;    }    R[324]=deep=0;    cnt=325;}void Insert(int r,int c){                        //头插法建链表    U[cnt]=c,D[cnt]=D[c];//确定新增结点上下指针信息    U[D[c]]=cnt,D[c]=cnt;//恢复链表信息    if(H[r]==-1)         //确定左右指针信息        H[r]=L[cnt]=R[cnt]=cnt;//增加头    else    {        L[cnt]=H[r],R[cnt]=R[H[r]];//头插法        L[R[H[r]]]=cnt,R[H[r]]=cnt;    }    S[c]++;//更新附加信息    row[cnt]=r;    C[cnt++]=c;}void Remove(int c)//移除c列。{    int i,j;    R[L[c]]=R[c],L[R[c]]=L[c];    for(i=D[c];i!=c;i=D[i])        for(j=R[i];j!=i;j=R[j])            D[U[j]]=D[j],U[D[j]]=U[j],S[C[j]]--;}void Resume(int c)//还原c列。{    int i,j;    R[L[c]]=L[R[c]]=c;    for(i=D[c];i!=c;i=D[i])        for(j=R[i];j!=i;j=R[j])            D[U[j]]=U[D[j]]=j,S[C[j]]++;}bool dfs(){    if(R[0]==0)        return true;    int i,j,c,miv=INF;    for(i=R[0];i;i=R[i])        if(S[i]<miv)            miv=S[i],c=i;    Remove(c);//处理第c列    for(i=D[c];i!=c;i=D[i])    {        for(j=R[i];j!=i;j=R[j])            Remove(C[j]);        ans[deep++]=row[i];        if(dfs())            return true;        for(j=L[i];j!=i;j=L[j])            Resume(C[j]);        deep--;    }    Resume(c);    return false;}int main(){    int i,j,v,r,p;    while(gets(maze))    {        if(maze[0]=='e')            break;        init();        r=1;        for(i=1;i<=9;i++)//每行为一个格子的一种选择。
        {            for(j=1;j<=9;j++)            {                if(maze[(i-1)*9+j-1]=='.')                {                    for(v=1;v<=9;v++)                    {                        Insert(r,(i-1)*9+j);                        Insert(r,81+(i-1)*9+v);                        Insert(r,162+(j-1)*9+v);                        Insert(r,243+(((i-1)/3)*3+(j+2)/3-1)*9+v);                        st[r].x=i,st[r].y=j,st[r].v=v;                        r++;                    }                }                else                {                    v=maze[(i-1)*9+j-1]-'0';                    Insert(r,(i-1)*9+j);                    Insert(r,81+(i-1)*9+v);                    Insert(r,162+(j-1)*9+v);                    Insert(r,243+(((i-1)/3)*3+(j+2)/3-1)*9+v);                    st[r].x=i,st[r].y=j,st[r].v=v;                    r++;                }            }        }        dfs();        for(i=0;i<deep;i++)        {            p=ans[i];            path[(st[p].x-1)*9+st[p].y-1]='0'+st[p].v;        }        path[deep]=0;        printf("%s\n",path);    }    return 0;}