原来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');
    }
}