HDU 3111 Sudoku ( Dancing Links 精确覆盖模型 )

推荐两篇学DLX的博文：

http://bbs.9ria.com/thread-130295-1-1.html（这篇对DLX的工作过程演示的很详细）

http://yzmduncan.iteye.com/blog/1151695（这篇对精确覆盖与重复覆盖解释的简洁清晰，模板来自这篇博文）

以下转载：

DLX解决9*9的数独问题，转化为729*324的精确覆盖问题

行：一共9 * 9 * 9 == 729行。一共9 * 9小格，每一格有9种可能性(1 - 9)，每一种可能都对应着一行。

列：一共(9 + 9 + 9) * 9 + 81 == 324 种前面三个9分别代表着9行9列和9小块，乘以9的意思是9种可能(1 - 9)，因为每种可能只可以选择一个。 81代表着81个小格，限制着每一个小格只放一个数字。

读入数据后，如果为'.'，则建9行，即有1-9种可能，否则建一行，表示某小格只能放确定的某个数字。

以下个人理解：

列：一共(9 + 9 + 9) * 9 + 81 == 324 种

对于这个（9+9+9）*9 我是这么理解的：一个数a，它在某一行有9个位置可以放，在某一列有9个位置可以放，在某一个3×3小格中有9个位置可以放，所以一共可以放的位置是（9+9+9）个，然后一共9个数字，所以是（9+9+9）*9 。

不知道这样理解是否正确，望大家指教！

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int INF =  << ;

const int SZ = ;

const int MAXR = SZ * SZ * SZ;

const int MAXC = ( SZ+SZ+SZ )*SZ + SZ*SZ;

char mat[SZ+][SZ+];

char str[SZ+];

bool maxtri[MAXR+][MAXC+];    //01矩阵

int C[(MAXR+)*(MAXC+)], cnt[MAXC+];

int U[(MAXR+)*(MAXC+)], D[(MAXR+)*(MAXC+)];

int L[(MAXR+)*(MAXC+)], R[(MAXR+)*(MAXC+)];

int head;

int ans[MAXR+];

int val[SZ+][SZ+];

void Remove( int c )

{

    int i, j;

    L[ R[c] ] = L[c];

    R[ L[c] ] = R[c];

    for ( i = D[c]; i != c; i = D[i] )

    {

        for ( j = R[i]; j != i; j = R[j] )

        {

            U[ D[j] ] = U[j];

            D[ U[j] ] = D[j];

            --cnt[ C[j] ];

        }

    }

    return;

}

void Resume( int c )

{

    int i, j;

    R[ L[c] ] = c;

    L[ R[c] ] = c;

    for ( i = D[c]; i != c; i = D[i] )

    {

        for ( j = R[i]; j != i; j = R[j] )

        {

            U[ D[j] ] = j;

            D[ U[j] ] = j;

            ++cnt[ C[j] ];

        }

    }

    return;

}

bool DFS( int cur )

{

    int i, j, c, minv;

    if ( R[head] == head )

        return true;

    minv = INF;

    for ( i = R[head]; i != head; i = R[i] )

    {

        if ( cnt[i] < minv )

        {

            minv = cnt[i];

            c = i;

        }

    }

    Remove(c);

    for ( i = D[c]; i != c; i = D[i] )

    {

        ans[cur] = (i - )/MAXC;

        for( j = R[i]; j != i; j = R[j] )

            Remove( C[j] );

        if ( DFS( cur +  ) ) return true;

        for( j = R[i]; j != i; j = R[j] )

            Resume( C[j] );

    }

    Resume(c);

    return false;

}

bool build()

{

    int i, j, cur, pre, first;

    head = ;

    for ( i = ; i < MAXC; ++i )

    {

        R[i] = i + ;

        L[i + ] = i;

    }

    R[ MAXC ] = ;

    L[] = MAXC;

    //列双向链表

    for ( j = ; j <= MAXC; ++j )

    {

        pre = j;

        cnt[j] = ;

        for ( i = ; i <= MAXR; ++i )

        {

            if ( maxtri[i][j] )

            {

                ++cnt[j];

                cur = i * MAXC + j;  //当前节点的编号

                C[cur] = j;          //当前节点所在列

                D[pre] = cur;

                U[cur] = pre;

                pre = cur;

            }

        }

        U[j] = pre;

        D[pre] = j;

        if ( !cnt[j] ) return false; //一定无解

    }

    //行双向链表

    for ( i = ; i <= MAXR; ++i )

    {

        pre = first = -;

        for ( j = ; j <= MAXC; ++j )

        {

            if( maxtri[i][j] )

            {

                cur = i * MAXC + j;

                if ( pre == - ) first = cur;

                else

                {

                    R[pre] = cur;

                    L[cur] = pre;

                }

                pre = cur;

            }

        }

        if ( first != - )

        {

            R[pre] = first;

            L[first] = pre;

        }

    }

    return true;

}

/**************以上DLX模板*****************/

void show()

{

    for ( int i = ; i <= MAXR; ++i )

    {

        for ( int j = ; j <= MAXC; ++j )

            printf( "%d", maxtri[i][j] );

        puts("");

    }

    return;

}

//得到该情况下的01矩阵

void init()

{

    memset( maxtri, false, sizeof(maxtri) );

    for ( int i = ; i <= SZ; ++i )

    {

        for ( int j = ; j <= SZ; ++j )

        {

            int col = ( i -  ) * SZ + j;  //格子编号（1-81）

            if ( mat[i][j] == '?' )

            {

                for ( int k = ; k <= SZ; ++k )

                {

                    maxtri[ (col - )*SZ + k ][col] = true;      //81保证不重复

                    maxtri[ (col - )*SZ + k ][  + (i - )*SZ + k ] = true;    //9行中哪一行

                    maxtri[ (col - )*SZ + k ][  + (j - )*SZ + k ] = true;   //9列中哪一列

                    maxtri[ (col - )*SZ + k ][  + ((i-)/* + (j-)/ )*SZ + k ] = true;//9小格中哪一个小格

                }

            }

            else

            {

                int k = mat[i][j] - '';

                maxtri[ (col - )*SZ + k ][col] = true;

                maxtri[ (col - )*SZ + k ][  + (i - )*SZ + k ] = true;

                maxtri[ (col - )*SZ + k ][  + (j - )*SZ + k ] = true;

                maxtri[ (col - )*SZ + k ][  + ((i-)/* + (j-)/ )*SZ + k ] = true;

            }

        }

    }

    //show();

    return;

}

void PrintAns()

{

    for ( int i = ; i < ; ++i )

    {

        int num = ans[i];

        int gird = num / SZ;

        if ( num % SZ ) ++gird;

        int aaa = num % SZ;

        if ( aaa ==  ) aaa = ;

        int x = (gird-)/SZ+;

        int y = (gird-)%SZ+;

        val[x][y] = aaa;

    }

    for ( int i = ; i <= SZ; ++i )

    {

        for ( int j = ; j <= SZ; ++j )

            printf( "%d", val[i][j] );

        puts("");

    }

    return;

}

int main()

{

    //freopen( "in.txt", "r", stdin );

    //freopen( "out.txt", "w", stdout );

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        for ( int i = ; i <= SZ; ++i )

            scanf( "%s", &mat[i][] );

        if ( T ) scanf( "%s", str );

        init();

        if ( build() )

        {

            if ( DFS() )

                PrintAns();

            else puts("impossible");

        }

        else puts("impossible");

        if ( T ) puts("---");

    }

    return ;

}

昨天比赛做到一个题，正解DLX，不过让薛薛位运算+剪枝直接暴过去了……跪。

为了保险起见，今天学了一下DLX。目前只明白了精确覆盖，对重复覆盖还不是很了解。

那个题似乎不是个很简单的DLX，需要精确覆盖+重复覆盖。orz，再接再厉吧。

不得不说，DLX的剪枝效果真是让人惊叹……

巴特西

HDU 3111 Sudoku ( Dancing Links 精确覆盖模型 )

最新文章

热门文章