原来dancing links解数独也是把数独转换为精确覆盖问题.
精确覆盖问题是指一个01矩阵,选择某些行使得每一列都有且只有一个1(既选行精确覆盖列).
(1)设问题为m^2 * m^2的规模,且n=m^2,则矩阵大小为n*n.
(2)用行来记录选出的结果,既第i行j列填k,使用n进制,所以行号为n*n*i + n*j + k.
输入时若M[i][j]为空,则k可取1~9,否则k只能取M[i][j].
(3)用列来避免碰撞,把列分为四个区:
[0~1*n*n)是第i,j行是否有数,所以其序号为n*i+j
[1*n*n~2*n*n)是第i行是否有k,所以其序号为n*i+k
[2*n*n~3*n*n)是第j列是否有k,所以其序号为n*j+k
[3*n*n~4*n*n)是第b个盒子(m*m)是否有k,所以其序号为n*b+k
(3)对每一个可取的行,设置对应的四个列为1,就构造好了,然后代到dancing links解精确覆盖的模板里解出来,把选择的行号(共n*n个)按照n进制解析出来就知道在M[i,j]填几(k)了.
因为模板里,行列都是从1开始的,所以叹号处有一些诡异的转换......
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAX 0x3f3f3f3f
#define MAXM 4
#define MAXN MAXM*MAXM
#define MAXR MAXN*MAXN*MAXN+20
#define MAXC 4*MAXN*MAXN+20
int M[MAXN][MAXN];
bool arr[MAXR][MAXC];
#define SIZE MAXR*MAXC
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
Col[SIZE], Row[SIZE];//所在列 所在行
int S[MAXC]; //列元素数
int sel[MAXR],seln;//选择的行
struct Dancer
{
void init(int height,int width)
{
int p/*节点编号*/, x, y, last;
for (p = 1; p <= width; p++) //初始化列头指针
{
L[p] = p - 1; R[p] = p + 1; //左右相邻
U[p] = D[p] = p; //只有一列
S[p] = 0; //列元素数
}
p = width + 1;
for (y = 1; y <= height; y++) //行
{
last = R[0] = L[0] = 0;//暂作为每行虚拟头指针
for (x = 1; x <= width; x++) //列
{
if (arr[y-1][x-1] != 0) // 0~n-1 -> 1~n !!!!!!!!!!!!!!!
{
//添到行链表尾部
L[p] = last; R[last] = p;
//添到列链表尾部
U[p] = U[x]; D[p] = x; U[x] = D[U[x]] = p;
////记录所在行列
Row[p]=y; Col[p]=x;
S[x]++; last=p++;
}
}
// 去虚头,构成行循环链表
R[last] = R[0]; L[R[0]] = last;
}
R[width] = 0; L[0] = width; R[0] = 1;
S[0] = MAX;
}
//删除c列上所有1元素所在的行
void remove(const int &c)
{
L[R[c]] = L[c]; R[L[c]] = R[c];//经典删除
for (int i = D[c]; i != c; i = D[i])
for (int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[Col[j]];
}
}
//恢复c列上所有1元素所在的行
void resume(const int &c)
{
for (int i = U[c]; i != c; i = U[i])
for (int j = L[i]; j != i; j = L[j])
{
U[D[j]] = j;
D[U[j]] = j;
++S[Col[j]];
}
L[R[c]] = c; R[L[c]] = c;//经典恢复
}
bool dance()
{
if (R[0] == 0) return true;//没有列了
int c=0, i, j;
for (i = R[0]; i != 0; i = R[i])//找元素最少的列c
if (S[i] < S[c]) c = i;
remove(c);
for (i = D[c]; i != c; i = D[i])//删除与c相连的行i
{
for (j = R[i]; j != i; j = R[j])//删除行元素所在的列j
remove(Col[j]);
sel[seln]=Row[i];//选择此行 保存行号
seln++;
if (dance()) return true;
seln--;
for (j = L[i]; j != i; j = L[j])
resume(Col[j]);
}
resume(c); return false;
}
} dc;
///////////////////////////////////////////////////////////////
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int i,j,k,m=4,n=16;
char c;
while((c=getchar())!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(c=='\n') c=getchar();
M[i][j]=(c=='-')?0:c-'A'+1;//!!!
c=getchar();
}
}
memset(arr,false,sizeof(arr));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
int b=i/m*m+j/m;//i,j的盒子号
if(M[i][j]==0)
{
for(k=0;k<n;k++)
{
int r=n*n*i+n*j+k;
arr[r][0*n*n + n*i+j ]=1;//i,j里有数
arr[r][1*n*n + n*i+k ]=1;//i行里有k
arr[r][2*n*n + n*j+k ]=1;//j列里有k
arr[r][3*n*n + n*b+k ]=1;//b盒里有k
}
}
else
{
k=M[i][j]-1;//!!!
int r=n*n*i+n*j+k;
arr[r][0*n*n + n*i+j ]=1;//i,j里有数
arr[r][1*n*n + n*i+k ]=1;//i行里有k
arr[r][2*n*n + n*j+k ]=1;//j列里有k
arr[r][3*n*n + n*b+k ]=1;//b盒里有k
}
}
///////////////////////////////////
seln=0;
dc.init(n*n*n,n*n*4);
if(dc.dance())
{
for(int h=0;h<seln;h++)
{
int t=sel[h]-1;//!!!
k=t%n; t/=n;
j=t%n; t/=n;
i=t%n;
M[i][j]=k;//!!!
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
putchar('A'+M[i][j]);
putchar('\n');
}
}
else
puts("INCORRECT");
putchar('\n');
}
}