一种高效的剪枝解数独策略

一种高效的剪枝解数独策略

引用

CSDN

1.

https://blog.csdn.net/Leo_h1104/article/details/88780120

数独是一种经典的逻辑游戏，其解法多种多样。本文介绍了一种基于回溯法与剪枝策略的高效数独求解算法。该算法通过维护一个支持快速执行、撤销操作和查询最小选择数操作集的数据结构，实现了与DLX算法相当甚至更优的效率。

数独是一种经典的智力游戏。数独可以转化为精确覆盖问题，从而使用精确覆盖问题的通用解法：舞蹈链(DLX)来解决。本文将介绍一种通过通过回溯法与剪枝来解决数独的方法。经OJ测验，其效率与DLX相差无几，甚至比DLX略快。

人工解数独常用的方法

9*9的数独是最常见的数独，因此用它举例

看每个格子能填入什么数

通常我们会主动关心那些周围填好的数比较多的格子，看能否推理出其中应该填什么。比如对于上图中第五行第一列的元素，只有填入4才是合法的。

看一个数能填在哪些地方

当某个数已经填了8次，我们总能快速推理出剩下的一个在哪里。当填了6或7次的时候也总能找到一些线索。比如上图中可以推理出第四行第二列、第五行第三列，必定有一个位置填入3

剪枝

概念定义

为了叙述方便，我们做如下定义

1. 格子：能填入一个数字的最小单元
2. n:问题的规模，指数独表的边长
3. 区域：n个不能填入相同数字的格子，包括方块、列、行三种
4. 方块：形状为( n ) ∗ ( n ) \sqrt(n)*\sqrt(n)( n)∗( n)的区域
5. 列：从上到下连续n个格子组成的区域
6. 行：从左到右连续n个格子组成的区域
7. 操作：在某个格子中填入某个数字
8. 合法操作：指不违背所处区域性质的操作
9. 互斥：两个操作，当做了一个操作后，另一个操作不是合法操作
10. 操作集：一些从规则上可以直接看出两两互斥，但是其中必须执行一个的操作的集合
11. 完成：一个操作集中有某个操作被执行
12. 选择数：一个操作集中合法操作的个数

剪枝策略

结合人工解决数独的经验，我使用了以下策略进行剪枝：

1. 因为一个格子要填一个数，所以在每个格子中填1~16的操作，构成操作集。枚举所有这样的未完成操作集
2. 因为一个区域每个数要填一次，所以在区域中不同位置填同一值的操作，构成操作集。枚举所有这样的未完成操作集
3. 对上述步骤枚举得到的操作集按选择数排序
4. 若选择数最少的为0，说明存在无法完成的操作集，之前执行的操作有误，回溯。否则进入步骤5
5. 选取选择数最少的未完成操作集S。当取法不唯一时任取一个即可
6. 执行S中的一个合法操作，并递归到下一层重复上述步骤。若没有找到解，撤销该操作。重复此步骤直到找到解或S中合法操作全都被尝试过

复杂度分析

朴素的上述过程，枚举操作集并统计选择数的复杂度为O ( n 3 ) O(n^3)O(n3)，排序的复杂度为O ( n 2 ) O(n^2)O(n2)。寻找S的复杂度为O ( n ) O(n)O(n)。枚举S中合法操作并执行的复杂度为O ( n ) O(n)O(n)（不考虑下一层递归所花的时间）。以上四个步骤没有嵌套关系，故每次调用递归回溯函数的时间复杂度为它们相加的结果O ( n 3 ) O(n^3)O(n3)。事实上，因为S的选择数是所有未完成操作集中最小的， S中合法操作的个数，即需要执行操作的次数，基本上是O ( 1 ) O(1)O(1)的。

优化

显然，我们应该将枚举操作集，排序操作集的复杂度转移到执行操作上，以此降低单次递归的时间复杂度。也就是说，我们要维护一个支持执行操作，撤销操作和查询选择数最小的操作集的数据结构。

每次执行和撤销操作，选择数发生变化的操作集的数量是O(n)的。如果有(n+1)个桶，分别表示选择数为0~n的操作集，那么我们在执行操作的时候，只需要把受到影响的操作集从一个桶里拿出来，放到另外一个桶里，然后将完成的操作集从桶中拿出，不放回。撤销操作的步骤与执行相反。而查询操作集的时候，只需从小到大依次查看每个桶里是否有操作集。我们可以通过维护(n+1)个操作集双向链表来实现这(n+1)个桶。这样，每次移动操作集都是O(1)的，每次执行或撤销操作的复杂度为O(n)，查询的复杂度也是O(n)。

于是，仅剩的问题是，如何高效地枚举受到影响的操作集？一个直观的思路是：每执行一个操作（格子=g，填入值=v），g中填入任何数的操作，以及g所在区域中所有格子填入v的操作，都会变成非法。那么当一个操作变为非法的时候，就将该操作所属的4个操作集（一个第一类和三个第二类）的选择数都减1。当撤销时再将这些操作变回合法，把操作集的选择数都加1就行了。

然而这个想法是错误的。一个操作是非法，可能是多个因素的限制。比如下图中，左上角的位置不能填入3。我们撤销它右面的3，它仍然不能填3。我们撤销它里面的5，它还是不能填3。

让我们设想，每个操作（格子=g，填入值=v）之上都可以加若干个“盖子”，每个盖子表示g所属的某个区域中填入了v，或者g中已经填入了数。显然，一个操作合法当且仅当它没有被盖住。当盖子从少变多或者从多变少，该操作所属的4个操作集均不受影响。当盖子从无到有或从有到无，则该操作合法性发生改变，会影响其所属的4个操作集。每次执行操作会为O(n)个操作加上盖子，加盖子是O(1)的，故执行操作在O(n)时间内就可以完成对所有被影响的操作集的移动。撤销操作会拿掉O(n)个操作的盖子，复杂度同理。

以上，我们成功地维护了一个支持以O(n)复杂度执行操作，撤销操作和查询选择数最小的操作集的数据结构。这使得每次递归的复杂度为O(n)。

一些讨论

与DLX的联系

本方法在维护的数据结构方面，与DLX有极大的相似之处。每个操作集实际上对应精确覆盖问题中的一个列。每次执行操作，实际上就是DLX中移除若干列的过程。

与朴素DLX不同的是，本方法将操作集按选择数这一指标桶排序。DLX中应当也可用类似的方法，对列进行排序。

效率

代码

#include<ctime>
#include<cstdio>
#include<cstring>
int maxv,e;
//Copyright 1800013060 
bool victory;
char ans[36][37];
struct option
{
    const bool isGrid;
    int level;
    option *l,*r;
    option(bool b):isGrid(b){}
    void remove();
    void insert();
};
option* opRank[37];
void option::remove()
{
    if(l)
        l->r=r;
    else opRank[level]=r;
    if(r) r->l=l;
}
void option::insert()
{
    l=NULL;
    r=opRank[level];
    if(opRank[level])
        opRank[level]->l=this;
    opRank[level]=this;
}
struct cell;
struct area;
struct areaValue;
struct areaValue:public option
{
    area* src;
    areaValue():option(false){}
    void init(area*s)
    {
        src=s;
        level=maxv;
        insert();
    }
    void inc()
    {
        remove();
        ++level;
        insert();
    }
    void dec()
    {
        remove();
        --level;
        insert();
    }
};
struct area
{
    cell* member[36];
    areaValue val[36];
    void allow(int v);
    void limit(int v);
    void init()
    {
        for(int i=0;i<maxv;i++)
            val[i].init(this);
    } 
}row[36],col[36],sqr[36];
struct cell:public option
{
    int limit[36];
    area *row;
    area *col;
    area *sqr;
    cell():option(true){}
    void init()
    {
        memset(limit,0,sizeof(limit));
        level=maxv;
        insert();
    }
    void add(int v)
    {
        if(!limit[v])
        {
            remove();
            --level;
            insert();
            row->val[v].dec();
            col->val[v].dec();
            sqr->val[v].dec();
        }
        ++limit[v];
    }
    void minus(int v)
    {
        --limit[v];
        if(!limit[v])
        {
            remove();
            ++level;
            insert();
            row->val[v].inc();
            col->val[v].inc();
            sqr->val[v].inc();
        }
    }
    void fill(int v)
    {
        ans[row-(::row)][col-(::col)]=v+'A';
        for(int i=0;i<maxv;i++)
            add(i);
        row->limit(v);
        col->limit(v);
        sqr->limit(v);
        remove();
    }
    void unfill(int v)
    {
        insert();
        ans[row-(::row)][col-(::col)]='-';
        row->allow(v);
        col->allow(v);
        sqr->allow(v);
        for(int i=0;i<maxv;i++)
            minus(i);
    }
}g[36][36];
void area::limit(int v)
{
    for(int i=0;i<maxv;i++)
        member[i]->add(v);
    val[v].remove();
}
void area::allow(int v)
{
    val[v].insert();
    for(int i=0;i<maxv;i++)
        member[i]->minus(v);
}
void init()
{
    victory=false;
    for(int i=0;i<maxv;i++)
        for(int j=0;j<maxv;j++)
        {
            g[i][j].init();
            g[i][j].row=row+i;
            row[i].member[j]=&g[i][j];
            g[i][j].col=col+j;
            col[j].member[i]=&g[i][j];
            g[i][j].sqr=sqr+(i/e)*e+j/e;
            sqr[(i/e)*e+j/e].member[i%e*e+j%e]=&g[i][j];
        }
    for(int i=0;i<maxv;i++)
    {
        row[i].init();
        col[i].init();
        sqr[i].init();
    }
}
void dfs(int dep)
{
    if(dep==maxv*maxv)
    {
        victory=true;
        for(int i=0;i<maxv;i++)
            puts(ans[i]);
        putchar('\n');
        return;
    }
    if(opRank[0])
        return;
    for(int i=1;i<=maxv;i++)
    {
        if(opRank[i])
        {
            switch(opRank[i]->isGrid)
            {
                cell *cp;
                areaValue *vp;
                case true:
                    cp=(cell*)opRank[i];
                    for(int j=0;j<maxv;j++)
                        if(!cp->limit[j])
                        {
                            cp->fill(j);
                            dfs(dep+1);
                            if(victory) return;
                            cp->unfill(j);
                        }
                    break;
                case false:
                    vp=(areaValue*)opRank[i];
                    for(int j=0;j<maxv;j++)
                    {
                        cp=vp->src->member[j];
                        if(!cp->limit[vp-(vp->src->val)])
                        {
                            cp->fill(vp-(vp->src->val));
                            dfs(dep+1);
                            if(victory) return;
                            cp->unfill(vp-(vp->src->val));
                        }
                    }
                    break;
            }
            return;
        }
    }
}
        
int main()
{
    bool flag=false;
    while(flag!=true)
    {
        scanf("%d",&e);
        maxv=e*e;
        init();
        int cnt=0;
        for(int i=0;i<maxv;i++)
        {
            if(scanf("%s",ans[i])==EOF)
            {
                flag=true;
                break;
            }
            for(int j=0;j<maxv;j++)
                if(ans[i][j]!='-')
                {
                    g[i][j].fill(ans[i][j]-'A');
                    cnt++;
                }
        }
        if(flag) break;
        int st=clock();
        dfs(cnt);
        printf("%.3f\n",1.0*(clock()-st)/CLOCKS_PER_SEC);
    }
    return 0;
}