poj 2676 Sudoku DLX

缘起

继续研究 DLX的应用. 这里是关于DLX在数独上的应用. poj 2676 Sudoku

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
给出一个残缺的数独，求解.

【输入】
第一行是样例数. 对每个测试用例，给出一个残缺数独.

【输出】
对每个样例, 输出一个解.

【样例输入】
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

【样例输出】
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

【限制】
2s

【是否接受special judge】
是

数独如何转换为精确匹配问题呢? 本题给出的是一个标准的数独（9*9）. 【1】中的伤脑筋的12块已经给出了转换的思路. 转换的思路这里总结一下

DLX中的01矩阵的行就是状态, 而列就是约束条件.

怎么理解呢? 就拿本题的数独来讲. 约束条件是

  1. 每个格子填的值只能是1种（即只能填写1~9中的一个）.这就有81个约束条件.
  2. 每行1的个数. 这就有9个约束（第一行1的个数, 第二行1的个数）, 9个数字就有81个约束（第1行9的个数,…,第9行9的个数）.
  3. 每列每种数字的个数, 同上也有81个约束.
  4. 每个九宫格中各个数字的个数. 同上，也是81个约束条件

综上，一共4*n^2 个约束条件. n=9

那么有多少行呢? 行即表示状态. 显然就是每个格子填什么数字. 一共81个格子. 每个格子有9种填法. 一共 n^3行.

所以这个01矩阵的大小是 4*n^2*n^3

然后在此矩阵上跑DLX算法. 具体讲就是新建01矩阵的时候，要使用link函数不断的往舞蹈链上加节点. 然后读入已经存在的数字的时候, 要调用remove方法移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
//#define LOCAL

const int maxn = 800, maxm = 25000, N=9; // N是数独的阶数
int m, u[maxm],d[maxm], l[maxm], r[maxm],row[maxm], col[maxm], h[maxn], ans[15][15], t, cnt[maxn]; 

void init()
{
	for (int i = 0; i<=m; i++)
	{
		l[i+1]=i, r[i] = i+1, d[i]=u[i]=i, cnt[i] = 0;
	}
	l[0] = m, r[m] = 0;
	t = m+1; 
}

void link(int i, int j)
{
	cnt[j]++,row[t] = i,col[t] = j; 
	d[t] = d[j],u[t] = j,u[d[j]] = t,d[j] = t; 
	if (!h[i]) 
	{
		h[i]=l[t]=r[t]=t;
	}
	else 
	{
		l[t]=h[i], r[t]=r[h[i]], l[r[h[i]]]=t, r[h[i]]=t;
	}
	t++;
}

void remove(int c) 
{
	r[l[c]] = r[c], l[r[c]]=l[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], cnt[col[j]]--; 
		}
	}
}

void resume(int c) 
{
	l[r[c]] = r[l[c]] = c; 
	for (int i = u[c]; i!=c; i = u[i])
	{
		for (int j = l[i]; j!=i; j = l[j])
		{
			d[u[j]] = u[d[j]] = j, cnt[col[j]]++; 
		}
	}
} 

void kkk(int num, int &tr, int &tc) // 第num个(1<=num<=81)格子位于第几行第几列
{
	tr = (num-1)/N+1;
	tc = (num-1)%N+1;
}

bool dance() 
{
	if (!r[0]) 
	{
		for (int i = 1; i<=N; i++)
		{
			for (int j = 1;j<=N; j++)
			{
				printf("%d",ans[i][j]);
			}
			puts("");
		}
		return true;
	}
	int _max = maxn, nxtCol;
	for (int i = r[0]; i; i = r[i]) 
	{
		if (_max>cnt[i])
		{
			nxtCol = i;
			_max = cnt[i];
		}
	}
	remove(nxtCol); 
	for (int i = d[nxtCol]; i!=nxtCol; i = d[i]) 
	{
		int tr, tc;
		kkk((row[i]-1)/N+1, tr, tc); // 得到 第(row[i]-1)/9+1 个格子位于的行与列tr和tc
		ans[tr][tc] = (row[i]-1)%N+1; // 选择i所在的这一行,即row[i]行, 这一行表示第(row[i]-1)/9+1个格子填写(row[i]-1)%9+1这个数字(这就是我们说的01矩阵的行表示的是状态,列表示的是约束)
		for (int j = r[i]; j!=i; j = r[j]) 
		{
			remove(col[j]); 
		}
		if (dance())
		{
			return true;
		}
		for (int j = l[i]; j!=i; j = l[j])
		{
			resume(col[j]); 
		}
	}
	resume(nxtCol); 
	return false;
}

int kk(int i, int j) // 返回i行j列的小格子所在宫的前面有多少个宫，例如4行6列的格子在第5宫, 它前面有4个宫, 则kk应该返回4
{
	int p = (int)(sqrt(N*1.0)+0.5); // 防止丢失精度
	return (i-1)/p*p+(j-1)/p;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	m = 4*N*N;
	while (kase--)
	{
		init();
		for (int i = 1; i<=N; i++)
		{
			for (int j = 1; j<=N; j++)
			{
				for (int k = 1,rr; k<=N; k++) // i行j列填写k
				{
					rr = ((i-1)*N+j-1)*N+k;
					link(rr, (i-1)*N+j); // i行j列格子只能填写一个数
					link(rr, N*N+(i-1)*N+k); // 第i行只能填写一个k
					link(rr, 2*N*N+(j-1)*N+k); // 第j列只能填写一个k
					link(rr, 3*N*N+kk(i,j)*N+k); // 第xxx个宫只能有一个k
				}
			}
		}
		for (int i = 1; i<=N; i++)
		{
			getchar(); // 吸收多余换行符
			for (int j = 1,k; j<=N; j++)
			{
				char c = getchar();
				if (c!='0')
				{
					k = c-'0'; // 第i行第j列写了k
					ans[i][j] = k;
					remove((i-1)*N+j); // 第i行第j列只能填写一个数字
					remove(N*N+(i-1)*N+k); // 第i行只能填写一个k
					remove(2*N*N+(j-1)*N+k); // 第j列只能填写一个k
					remove(3*N*N+kk(i,j)*N+k); // 第xxx个宫只能有一个k
				}
			}
		}
		dance();
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 212kB
Length 2894
Lang C++
Submitted 2019-09-16 19:47:46
Shared
RemoteRunId 20865890

类似的题目还有 poj 3076 Sudoku 、poj 3074 Sudoku

都是一样的做法.

使用本程序去解骨灰级的数独题目. 答案是秒出的~ ^_^~

例如下面的骨灰级数独难题

1
2
3
4
5
6
7
8
9
10
1
000009000
290003100
000000680
001002003
570000012
900800700
068000000
004500076
000200000

程序秒出一组答案

1
2
3
4
5
6
7
8
9
815679234
296483157
437125689
681752493
573946812
942831765
768394521
324518976
159267348

参考

【1】https://yfsyfs.github.io/2019/09/16/fzu-1686-%E7%A5%9E%E9%BE%99%E7%9A%84%E9%9A%BE%E9%A2%98-%E9%87%8D%E5%A4%8D%E8%A6%86%E7%9B%96-DLX/