题解 P1784 【数独】
3493441984zz
2019-01-23 09:56:59
# $Dancing$ $links$真是个好东西$qwq$
### 刚学完就来水题解。。。希望能给大家一些帮助
------------
# 回归正题：
其实舞蹈链就是模板，但是难在哪呢？就是怎么把问题转化为舞蹈链能解决的问题：精确覆盖，重复覆盖等
所以这篇题解详细讲一下舞蹈链对于数独问题的建模
#### 那么我们先思考，数独的要求有哪些？
$1$、每一格只能填一个数
$2$、每一行每种数只能填一个
$3$、每一列每种数只能填一个
$4$、每一宫每种数只能填一个
那么这就可以像舞蹈链解决精确覆盖问题一样解决了，那么重点来了，**怎么构造矩阵**
------------
### $1$、矩阵中的列：
#### 我们首先要解决第一个约束条件，那么$9*9$数独中一共有$81$格，我们转换为$81$列
第$1$列表示$(1,1)$填了一个数
第$2$列表示$(1,2)$填了一个数
第$3$列表示$(1,3)$填了一个数
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$10$列表示$(2,1)$填了一个数
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$81$列表示$(9,9)$填了一个数
这样的话，我们就用了$81$列完成了第一个约束条件
#### 我们接下来要解决第二个约束条件，那么$9*9$数独中一共有$9$行，每行可以填$9$个数字，我们又转换为$81$列
第$1$列表示第$1$行填了数字$1$
第$2$列表示第$1$行填了数字$2$
第$3$列表示第$1$行填了数字$3$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$10$列表示第$2$行填了数字$1$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$81$列表示第$9$行填了数字$9$
这样的话，我们就又用了$81$列完成了第二个约束条件
#### 我们接下来要解决第三个约束条件，与第二个条件类似的，$9*9$数独中一共有$9$列，每列可以填$9$个数字，我们又转换为$81$列
第$1$列表示第$1$列填了数字$1$
第$2$列表示第$1$列填了数字$2$
第$3$列表示第$1$列填了数字$3$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$10$列表示第$2$列填了数字$1$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$81$列表示第$9$列填了数字$9$
这样的话，我们就又用了$81$列完成了第三个约束条件
#### 我们接下来要解决最后一个约束条件，$9*9$数独中一共有$9$个宫，每宫可以填$9$个数字，我们又转换为$81$列
第$1$列表示第$1$宫填了数字$1$
第$2$列表示第$1$宫填了数字$2$
第$3$列表示第$1$宫填了数字$3$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$10$列表示第$2$宫填了数字$1$
$\qquad\qquad\quad\vdots$
$\qquad\qquad\quad\vdots$
第$81$列表示第$9$宫填了数字$9$
这样的话，我们就又用了$81$列完成了最后一个约束条件
### 最后，我们就用了$324$列来保证了每个约束条件
------------
### $2$、矩阵中的行
我们分两类，一种是一开始填了数字的，和没填的
#### 对于填了数字的格子
我们举个例子：$(2,1)$中填了一个数$7$
那么我们就要把这个转换为上面的限制条件,即：
$1$、$(2,1)$中填了一个数字
$2$、第$2$行填了一个数字$7$
$3$、第$1$列填了一个数字$7$
$4$、第一宫填了一个数组$7$
我们分别与相应的列相连就可以了
#### 对于没填数字的格子
我们举个例子：$(4,5)$中数字为$0$
那么我们就要枚举这个格子的所有情况：
这个格子填 $1$，像上面一样与矩阵中对应列相连
这个格子填 $2$，像上面一样与矩阵中对应列相连
这个格子填 $3$，像上面一样与矩阵中对应列相连
$\qquad\qquad\qquad\quad\quad\vdots$
$\qquad\qquad\qquad\quad\quad\vdots$
那么最后，表示$(4,5)$这个格子填了一个数的列的所有元素都是$1$，这就保证了，我填了一个数$1$后，这个点就不会再填其他数了（删除列操作，不多$bb$）
### 那么$9*9$数独一共有$81$个格子，最坏的的情况下，每个格子都是$0$，那么每个格子都要有$9$种情况，所以就会有$729$行
------------
# 总结：
我们最后把一个$9*9$的数独转换为了一个$729*324$的矩阵，最后就开始舞蹈链模板啦~~~（岂不是美滋滋~~~）
#### 接下来是美滋滋的代码时间~~~
~~~cpp
#include<iostream>
#include<cstdio>
#include<vector>
#define N 11
#define M 236200
using namespace std;
int head,cnt;
int g[N][N],u[M],d[M],l[M],r[M],row[M],col[M],num[M],ans[M];
vector<int> v[M];
void Init()
{
for(int i=0;i<=324;++i)
{
u[i]=i;
d[i]=i;
l[i]=i-1;
r[i]=i+1;
}
l[head]=324;
r[324]=head;
cnt=325;
}
void Addrow(int x)
{
int first=cnt;
for(int i=0;i<v[x].size();++i)
{
int j=v[x][i];
u[cnt]=u[j];
d[u[j]]=cnt;
u[j]=cnt;
d[cnt]=j;
l[cnt]=cnt-1;
r[cnt]=cnt+1;
col[cnt]=j;
row[cnt]=x;
++num[j];
++cnt;
}
l[first]=cnt-1;
r[cnt-1]=first;
}
void Remove(int x)
{
r[l[x]]=r[x];
l[r[x]]=l[x];
for(int i=d[x];i!=x;i=d[i])
for(int j=r[i];j!=i;j=r[j])
{
u[d[j]]=u[j];
d[u[j]]=d[j];
--num[col[j]];
}
}
void Restore(int x)
{
for(int i=u[x];i!=x;i=u[i])
for(int j=l[i];j!=i;j=l[j])
{
d[u[j]]=j;
u[d[j]]=j;
++num[col[j]];
}
r[l[x]]=x;
l[r[x]]=x;
}
bool Dance(int dep)
{
if(r[head]==head)
{//cout<<"sdadad\n";
int x,y,z;
//cout<<"dep:"<<dep<<endl;
for(int i=0;i<dep;++i)
{
//printf("%d ",ans[i]);
x=(ans[i]-1)/9/9;
y=(ans[i]-1)/9%9;
z=ans[i]%9;
if(!z)
z=9;//cout<<x<<" "<<y<<" "<<z<<endl;
g[x][y]=z;
}
return 1;
}
int now=r[head];
for(int i=r[head];i!=head;i=r[i])
if(num[i]<num[now])
now=i;
// cout<<now<<" ";
Remove(now);
for(int i=d[now];i!=now;i=d[i])
{
//cout<<"as\n";
ans[dep]=row[i];
for(int j=r[i];j!=i;j=r[j])
Remove(col[j]);
if(Dance(dep+1))
return 1;
for(int j=l[i];j!=i;j=l[j])
Restore(col[j]);
}
Restore(now);
return 0;
}
int main()
{
Init();
for(int i=0;i<9;++i)
for(int j=0;j<9;++j)
{
scanf("%d",&g[i][j]);
for(int k=1;k<=9;++k)
{
if(g[i][j]!=k&&g[i][j])
continue;
int x=i*9*9+j*9+k;
v[x].push_back(i*9+j+1);
v[x].push_back(i*9+81+k);
v[x].push_back(j*9+81*2+k);
v[x].push_back(81*3+(i/3*3+j/3)*9+k);
Addrow(x);
}
}
Dance(0);
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)
printf("%d ",g[i][j]);
printf("\n");
}
return 0;
}
~~~