spoj 1771 NQUEEN Yet Another N-Queen Problem DLX

缘起

【1】中讲解了舞蹈链算法. 这里用它解决N皇后（N>8） spoj 1771 NQUEEN Yet Another N-Queen Problem

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N皇后 (N<=50)

【输入】
多样例. 每个样例开始于一个正整数N（N<=50）.然后是N个正整数. 表示每行皇后所在的列. 如果是0的话, 表明
此行尚没有放置皇后. 输入保证有解.

【输出】
对每个样例，输出一个解(即每个数代表逐行的皇后放置的位置). 如果有多个解, 任意输出一组解即可.

【样例输入】
4 0 0 0 0
8 2 0 0 0 4 0 0 0

【样例输出】
2 4 1 3
2 6 1 7 4 8 3 5

【限制】
Time limit:	    640ms
Source limit:	10000B
Memory limit:	1536MB

这里N太大以至于我们无法使用dfs求解N皇后. 所以只能用DLX求解. N皇后和舞蹈链之间的匹配问题之间的关系在【1】中已经说过了. 这里不再赘述.

本题的算法就是针对每个case初始化舞蹈链（确定要在i行j列放置皇后的话, 相当于是在舞蹈链对应01矩阵(n^2(6n-6))的i\j行, 某4列设置为1）

舞蹈链的注释没写, 详细注释见 【2】

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
//#include "stdafx.h"

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

const int maxn = 2505, maxm = 15000; // maxm应该是n^2*4+6n-6
int n,m, u[maxm],d[maxm], l[maxm], r[maxm],row[maxm], col[maxm], h[maxn], ans[maxn], t, cnt[maxn],tt;  // tt用于保存原来的n

void init()
{
	memset(h, 0, sizeof(h));
	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]]++; 
		}
	}
} 

bool dance()
{
	if (!(r[0]>=1&&r[0]<=2*tt)) // 如果[1,2*tt]这些列都被移除掉了, 表明行和列都移除干净了,则就得到了N皇后的一组解
	{
		for (int i =1; i<=tt; i++)
		{
			if (i>1)
			{
				putchar(' ');
			}
			printf("%d", ans[i]);
		}
		puts("");
		return true;
	}
	int _max = maxn, nxtCol;
	for (int i = r[0]; i; i = r[i])
	{
		if (_max>cnt[i] && i<=2*tt) // 注意, N皇后问题一定要覆盖掉的是前面2n列(即行或者列, 而不是后面的对角线部分, 对角线部分只需要没有超过1个的1出现即可, 即后面4n-6列, 每列的1的个数<=1即可),所以这里i<=2*tt
		{
			nxtCol = i;
			_max = cnt[i];
		}
	}
	remove(nxtCol); // 和【2】一样,要优先搜索1比较少的列, 这样dfs搜索的路径较少,速度更快——毕竟我们只需要搜索得到一个解即可,而不需要得到全部解
	for (int i = d[nxtCol]; i!=nxtCol; i = d[i]) 
	{
		ans[(row[i]-1)/tt+1] = (row[i]-1)%tt+1; // 比如8*8棋盘选了01矩阵的第16行, 则其实是让第2行((16-1)/8+1)的棋盘的第6((16-1)%8+1)列位置放置了皇后
		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 main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%d", &n))
	{
		m = 6*n-6;
		tt = n; // 保存原先的行数
		n = n*n; // n皇后对应n^2行 6n-6列01矩阵
		init();
		for (int i = 1;i<=tt;i++) // n^2*6n-6 矩阵每一行代表在某个棋盘格子放进皇后
		{
			for (int j = 1; j<=tt; j++) // 在棋盘第i行第j列放置皇后
			{
				link((i-1)*tt+j,i);  // 行
				link((i-1)*tt+j,tt+j);  // 列
				if (!((i==tt && j==1)||(i==1&&j==tt)))  // 左上角和右下角是不能参与左对角线的
				{
					link((i-1)*tt+j,2*tt+tt+(j-i)-1);  // 左对角线
				}
				if (!((i==1 && j==1)||(i==tt&&j==tt))) // 左下角和右上角不能参与右对角线
				{
					link((i-1)*tt+j,4*tt-3+i+j-2);  // 右对角线
				}
			} // 每行四个1, 分别位于行区域、列区域、左对角线区域、右对角线区域
		}
		for (int i = 1,j; i<=tt; i++)
		{
			scanf("%d", &j);
			if (j) // 第i行的皇后放在第j列, 则显然需要移除舞蹈链对应01矩阵的4列
			{
				ans[i] = j; // 第i行的皇后放在第j列
				remove(i);
				remove(tt+j);
				if (!((i==tt && j==1)||(i==1&&j==tt))) // 这里也是一样——左上角和右下角是不能参与左对角线的
				{
					remove(2*tt+tt+(j-i)-1);
				}
				if (!((i==1 && j==1)||(i==tt&&j==tt)))
				{
					remove(4*tt-3+i+j-2);
				}
			}
		} // 构建舞蹈链完毕
		dance(); // 起舞吧~
	}
	return 0;
}

ac情况

Status Accepted
Time 50ms
Memory 4301kB
Length 2993
Lang C++ (g++ 4.3.2)
Submitted 2019-09-16 11:31:11
Shared
RemoteRunId 24402252

从本题就可以看出, 使用DLX算法可以非常快的算出一个可行解. 但是如果要算出所有解或者解的个数, 则DLX相对dfs并没有太大优势,dfs算法当n达到16的时候，甚至无法给出一个可行解, 但是DLX可以秒出一个可行解. 这就是DLX的优势! 从本题就可以看出, 使用DLX算法可以非常快的算出一个可行解. 但是如果要算出所有解或者解的个数, 则DLX相对dfs并没有太大优势,dfs算法当n达到16的时候，甚至无法给出一个可行解, 但是DLX可以秒出一个可行解. 这就是DLX的优势!

其实想想就知道为什么DLX比dfs快的多~ 因为DLX选定一行能大幅缩减矩阵的规模, dfs缩减的很慢

参考

【1】https://yfsyfs.github.io/2019/09/14/%E8%88%9E%E8%B9%88%E9%93%BE%EF%BC%88dancing-links%EF%BC%89%E7%AE%97%E6%B3%95/

【2】https://yfsyfs.github.io/2019/09/15/%E6%B4%9B%E8%B0%B7-P4929-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E8%88%9E%E8%B9%88%E9%93%BE%EF%BC%88DLX%EF%BC%89-%E7%B2%BE%E7%A1%AE%E5%8C%B9%E9%85%8D/