雪竹的天空

theorix

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  34 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks

 数独问题可以转换为729行324列的exact cover 问题。每一行代表每个方格的可选值,每一列代表每个格的限制,建立双向十字链表,即可用dancing links算法优化求解。

  1Source Code
  2
  3Problem: 3074  User: theorix 
  4Memory: 308K  Time: 47MS 
  5Language: C++  Result: Accepted 
  6
  7Source Code 
  8#include<iostream>
  9using namespace std;
 10#define RR 729
 11#define CC 324
 12#define INF 1000000000
 13int mem[RR+9];
 14int ans[RR+9];
 15char ch[RR+9];
 16int cnt[CC+9];
 17struct node
 18{
 19    int r,c;
 20    node *up;
 21    node *down;
 22    node *left;
 23    node *right;
 24}
head,all[RR*CC+99],row[RR],col[CC];int all_t;
 25inline void link(int r,int c)
 26{
 27    cnt[c]++;
 28    node *t=&all[all_t++];
 29    t->r=r;
 30    t->c=c;
 31    t->left=&row[r];
 32    t->right=row[r].right;
 33    t->left->right=t;
 34    t->right->left=t;
 35    t->up=&col[c];
 36    t->down=col[c].down;
 37    t->up->down=t;
 38    t->down->up=t;
 39}

 40inline void remove(int c)
 41{
 42    node *t,*tt;
 43    col[c].right->left=col[c].left;
 44    col[c].left->right=col[c].right;
 45    for(t=col[c].down;t!=&col[c];t=t->down)
 46    {
 47        for(tt=t->right;tt!=t;tt=tt->right)
 48        {
 49            cnt[tt->c]--;
 50            tt->up->down=tt->down;
 51            tt->down->up=tt->up;
 52        }

 53        t->left->right=t->right;
 54        t->right->left=t->left;
 55    }

 56}

 57inline void resume(int c)
 58{
 59    node *t,*tt;
 60    for(t=col[c].down;t!=&col[c];t=t->down)
 61    {        
 62        t->right->left=t;
 63        t->left->right=t;
 64        for(tt=t->left;tt!=t;tt=tt->left)
 65        {
 66            cnt[tt->c]++;
 67            tt->down->up=tt;
 68            tt->up->down=tt;
 69        }

 70    }
    
 71    col[c].left->right=&col[c];
 72    col[c].right->left=&col[c];
 73}

 74bool solve(int k)
 75{
 76    if(head.right==&head)
 77        return true;
 78    node*t,*tt;
 79    int min=INF,tc;
 80    for(t=head.right;t!=&head;t=t->right)
 81    {
 82        if(cnt[t->c]<min)
 83        {
 84            min=cnt[t->c];
 85            tc=t->c;
 86            if(min<=1)break;
 87        }

 88    }

 89    remove(tc);
 90    for(t=col[tc].down;t!=&col[tc];t=t->down)
 91    {
 92        mem[k]=t->r;
 93        t->left->right=t;
 94        for(tt=t->right;tt!=t;tt=tt->right)
 95        {
 96            remove(tt->c);
 97        }

 98        t->left->right=t->right;
 99        if(solve(k+1))
100            return true;
101        t->right->left=t;
102        for(tt=t->left;tt!=t;tt=tt->left)
103        {
104            resume(tt->c);
105        }

106        t->right->left=t->left;
107    }

108    resume(tc);
109    return false;
110}

111int main()
112{
113    double ss=0;
114    while(gets(ch))
115    {
116        int i,j,k;
117        if(ch[0]=='e')break;
118        all_t=1;
119        memset(cnt,0,sizeof(cnt));
120        head.left=&head;
121        head.right=&head;
122        head.up=&head;
123        head.down=&head;
124        head.r=RR;
125        head.c=CC;
126        for(i=0;i<CC;i++)
127        {
128            col[i].c=i;
129            col[i].r=RR;
130            col[i].up=&col[i];
131            col[i].down=&col[i];
132            col[i].left=&head;
133            col[i].right=head.right;
134            col[i].left->right=&col[i];
135            col[i].right->left=&col[i];
136        }

137        for(i=0;i<RR;i++)
138        {
139            row[i].r=i;
140            row[i].c=CC;
141            row[i].left=&row[i];
142            row[i].right=&row[i];
143            row[i].up=&head;
144            row[i].down=head.down;
145            row[i].up->down=&row[i];
146            row[i].down->up=&row[i];
147        }

148        for(i=0;i<RR;i++)
149        {
150            int r=i/9/9%9;
151            int c=i/9%9;
152            int val=i%9+1;
153            if(ch[r*9+c]=='.'||ch[r*9+c]==val+'0')
154            {
155                link(i,r*9+val-1);
156                link(i,81+c*9+val-1);
157                int tr=r/3;
158                int tc=c/3;
159                link(i,162+(tr*3+tc)*9+val-1);
160                link(i,243+r*9+c);
161            }

162        }

163        for(i=0;i<RR;i++)
164        {
165            row[i].left->right=row[i].right;
166            row[i].right->left=row[i].left;
167        }

168        solve(1);
169        for(i=1;i<=81;i++)
170        {
171            int t=mem[i]/9%81;
172            int val=mem[i]%9+1;
173            ans[t]=val;
174        }

175        for(i=0;i<81;i++)
176            printf("%d",ans[i]);
177        printf("\n");
178    }

179}

180
181

 

posted on 2008-09-01 02:01 雪竹的天空( theorix ) 阅读(5688) 评论(8)  编辑 收藏 引用 所属分类: 解题报告

评论

# re: 数独的 Dancing links 解法(源代码) 2008-09-01 02:12 <font color="red">雪竹的天空( theorix )
TLE了几天终于把这道数独题过了
呵呵 写的还不错  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2008-11-27 16:39 梅雪香
您好,向您请教一下,这个程序的输入数据格式是怎么样的呢?
另外,我基本了解了dancing links的求解算法,但不太清楚如何把数独问题转化为精确覆盖问题,也就是怎么初始化成为729行324列的exact cover 问题。
能不能把这个转换过程的思想描述一下呢?
如肯赐教请发邮件到: mxx@vip.qq.com
先谢谢您了.  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2009-02-08 23:18 stranger
http://en.wikipedia.org/wiki/Exact_cover  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2009-02-25 14:37 ttylikl
我将上面的代码移植到C#竟然出了问题,真晕啊。。。  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2009-06-03 20:41 doxi
想问问,但如何把数独问题转化为精确覆盖问题 谢谢大牛指点  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2009-06-03 20:42 doxi

想问问,但如何把数独问题转化为精确覆盖问题 谢谢大牛指点 doxi
我的邮箱 ; fanxicai2000@163.com  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2010-05-08 15:46 批你
靠啊,你确定你是对的吗  回复  更多评论
  

# re: 数独的 Dancing links 解法(含源代码) 2010-09-26 15:02 LitIce
我认真研究了下你的程序,用他做noip2009靶形数独。
发现
102 for(tt=t->left;tt!=t;tt=tt->left)
如果把left改成right。。(其他对应)改动。
也就是恢复的顺序和删除的顺序相同,会Tle。
而你现在这样原路退回去恢复会快很多,并且不会Tle.
能否解释下。
邮箱:13559542150@139.com
期待你的回复……
90 for(t=col[tc].down;t!=&col[tc];t=t->down)
91 {
92 mem[k]=t->r;
93 t->left->right=t;
94 for(tt=t->right;tt!=t;tt=tt->right)
95 {
96 remove(tt->c);
97 }
98 t->left->right=t->right;
99 if(solve(k+1))
100 return true;
101 t->right->left=t;
102 for(tt=t->left;tt!=t;tt=tt->left)
103 {
104 resume(tt->c);
105 }
106 t->right->left=t->left;
107 }
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理