数独问题可以转换为729行324列的exact cover 问题。每一行代表每个方格的可选值，每一列代表每个格的限制，建立双向十字链表，即可用dancing links算法优化求解。
1
Source 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