n皇后学习

洛谷P1219

回溯

#include
const int N = 13;
int n, cnt, ans[N];
void dfs(int row) {
	if (row == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; ++i) {
				if (i > 0)printf(" ");
				printf("%d", ans[i] + 1);
			}
			printf("\n");
		}
		++cnt;
		return;
	}
	for (int i = 0; i < n; ++i) {
		bool flag = true;
		for (int j = 0; j < row; ++j) {
			if (ans[j] == i || row - j == i - ans[j] || j - row == i - ans[j]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			ans[row] = i;
			dfs(row + 1);
		}
	}
}
int main() {
	scanf("%d", &n);
	dfs(0);
	printf("%d\n", cnt);
	return 0;
}
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

但是最后13的时候会T

优化1

简单来说就是哪列哪一对角线被占了先缓存一下，到时候直接查表

#include
const int N = 13;
bool col[N], sub_diag[2 * N - 1], main_diag[2 * N - 1];
int n, cnt, ans[N];
void dfs(int row) {
	if (row == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; ++i) {
				if (i > 0)printf(" ");
				printf("%d", ans[i] + 1);
			}
			printf("\n");
		}
		++cnt;
		return;
	}
	for (int col_idx = 0; col_idx < n; ++col_idx) {
		int sub_diag_idx = col_idx + row, main_diag_idx = col_idx - row + n - 1;
		if (col[col_idx] || sub_diag[sub_diag_idx] || main_diag[main_diag_idx])continue;
		col[col_idx] = sub_diag[sub_diag_idx] = main_diag[main_diag_idx] = true;
		ans[row] = col_idx;
		dfs(row + 1);
		col[col_idx] = sub_diag[sub_diag_idx] = main_diag[main_diag_idx] = false;

	}
}
int main() {
	scanf("%d", &n);
	dfs(0);
	printf("%d\n", cnt);
	return 0;
}
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

位运算

其实就是优化1改成用位运算

#include
const int N = 13;
int n, cnt, ans[N], col, sub_diag, main_diag;
void dfs(int row) {
	if (row == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; ++i) {
				if (i > 0)printf(" ");
				printf("%d", ans[i] + 1);
			}
			printf("\n");
		}
		++cnt;
		return;
	}
	for (int col_idx = 0; col_idx < n; ++col_idx) {
		int sub_diag_idx = col_idx + row, main_diag_idx = col_idx - row + n - 1;
		if (((col >> col_idx) | (sub_diag >> sub_diag_idx) | (main_diag >> main_diag_idx)) & 1)continue;
		
		col ^= 1 << col_idx;
		sub_diag ^= 1 << sub_diag_idx;
		main_diag ^= 1 << main_diag_idx;
		ans[row] = col_idx;
		
		dfs(row + 1);
		
		col ^= 1 << col_idx;
		sub_diag ^= 1 << sub_diag_idx;
		main_diag ^= 1 << main_diag_idx;

	}
}
int main() {
	scanf("%d", &n);
	dfs(0);
	printf("%d\n", cnt);
	return 0;
}
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

位运算2

每一行的副对角线：row->row+n-1
所以只要右移row位，就能找到能一列被占用了

每一行主对角线：-row+n-1->-row+n-1+n-1
所以只要右移-row+n-1位，就能找到能一列被占用了

col | (sub_diag >> row) | (main_diag >> (n - 1 - row))就是被占用的列
~(col | (sub_diag >> row) | (main_diag >> (n - 1 - row)))就是可以用的列（当然还包括一些超过n的列）

#include
const int N = 13;
int n, cnt, ans[N], col, sub_diag, main_diag;
void dfs(int row) {
	if (row == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; ++i) {
				if (i > 0)printf(" ");
				printf("%d", ans[i] + 1);
			}
			printf("\n");
		}
		++cnt;
		return;
	}
	int available = ((1 << n) - 1) & ~(col | (sub_diag >> row) | (main_diag >> (n - 1 - row)));
	while (available) {
		int p = available & (-available);
		available ^= p;
		
		col ^= p;
		sub_diag ^= p << row;
		main_diag ^= p << (n - 1 - row);
		
		for (int i = 0; i < n; ++i) {
			if ((1 << i) == p) {
				ans[row] = i;
				break;
			}
		}

		dfs(row + 1);

		col ^= p;
		sub_diag ^= p << row;
		main_diag ^= p << (n - 1 - row);
	}
}
int main() {
	scanf("%d", &n);
	dfs(0);
	printf("%d\n", cnt);
	return 0;
}
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

位运算3

col的第i位代表这一行第i列是否被占用
sub_diag的第i位代表这一行第i个副对角线是否被占用
main_diag的第i位代表这一行第i个主对角线是否被占用

dfs到下一层的时候，col不变
在第i行，假设第k个副对角线被占用了
那么在i+1行，第k-1个副对角线就被占用了
同理
在第i行，假设第k个主对角线被占用了
那么在i+1行，第k+1个主对角线就被占用了

#include
const int N = 13;
int n, cnt, ans[N];
void dfs(int row, int col, int sub_diag, int main_diag) {
	if (row == n) {
		if (cnt < 3) {
			for (int i = 0; i < n; ++i) {
				if (i > 0)printf(" ");
				printf("%d", ans[i] + 1);
			}
			printf("\n");
		}
		++cnt;
		return;
	}
	int available = ((1 << n) - 1) & ~(col | sub_diag | main_diag);
	while (available) {
		int p = available & (-available);
		available ^= p;
		
		for (int i = 0; i < n; ++i) {
			if ((1 << i) == p) {
				ans[row] = i;
				break;
			}
		}
		dfs(row + 1, col | p, (sub_diag | p) >> 1, (main_diag | p) << 1);
	}
}
int main() {
	scanf("%d", &n);
	dfs(0, 0, 0, 0);
	printf("%d\n", cnt);
	return 0;
}
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

舞蹈链

https://blog.csdn.net/qq_39942341/article/details/126681667?spm=1001.2014.3001.5501
行：$n\ast n$个格子
列：$\left[1,n\right]$用来记录这个数字填在了哪行
$\left[n+1,2n\right]$用来记录这个数字填在了哪列
$\left[2n+1,4n-1\right]$用来记录这个数字填在了哪条副对角线(从$(0,0)$开始)
$\left[4n,6n-2\right]$用来记录这个数字填在了哪条主对角线(从$(n-1,0)$开始)

但是注意一点，对角线是无法完全覆盖的
比如下面的图，第3条副对角线就没有覆盖

所以如果行和列覆盖完了就可以返回了

#include
#include
#include

const int H = 13;
const int M = H * H, N = 6 * H - 2;
int n, board_cnt;
struct A {
	int a[H];
}board[100000];
bool cmp(const A& a, const A& b) {
	int i = 0;
	while (i < n && a.a[i] == b.a[i])++i;
	return a.a[i] < b.a[i];
};
class DLX {
public:
	static const int MAXN = M * 4 + N + 5;
	int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
	int row[MAXN], col[MAXN], head[M+5], col_size[N+5], cnt;
	int ans, ans_row[H];
	DLX() :cnt(0), ans(0) {}
	void init(const int& N) {
		cnt = ans = 0;
		for (int i = 0; i <= N; ++i) {
			left[i] = i - 1;
			right[i] = i + 1;
			up[i] = down[i] = i;
		}
		left[0] = N;
		right[N] = 0;
		memset(head, -1, sizeof(head));
		memset(col_size, 0, sizeof(col_size));
		cnt = N + 1;
	}
	void link(const int& r, const int& c) {
		++col_size[c];
		row[cnt] = r;
		col[cnt] = c;
		up[cnt] = c;
		down[cnt] = down[c];
		up[down[c]] = cnt;
		down[c] = cnt;
		if (head[r] == -1) {
			head[r] = left[cnt] = right[cnt] = cnt;
		}
		else {
			right[cnt] = head[r];
			left[cnt] = left[head[r]];
			right[left[head[r]]] = cnt;
			left[head[r]] = cnt;
		}

		++cnt;
	}
	void remove(const int& c) {
		right[left[c]] = right[c];
		left[right[c]] = left[c];
		for (int i = down[c]; i != c; i = down[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = up[j];
				down[up[j]] = down[j];
				--col_size[col[j]];
			}
		}
	}
	void resume(const int& c) {
		for (int i = up[c]; i != c; i = up[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = j;
				down[up[j]] = j;
				++col_size[col[j]];
			}
		}
		right[left[c]] = c;
		left[right[c]] = c;
	}
	void dance(int dep) {
		if (right[0]>n) {
			for (int i = 0; i < n; ++i) {
				int x = (ans_row[i] - 1) / n;
				int y = (ans_row[i] - 1) % n + 1;
				board[board_cnt].a[x] = y;
			}
			++board_cnt;
			return;
		}
		int c = right[0];
		for (int i = right[c]; i != 0 && i <= n; i = right[i]) {
			if (col_size[i] < col_size[c]) {
				c = i;
			}
		}
		remove(c);
		for (int i = down[c]; i != c; i = down[i]) {
			ans_row[ans++] = row[i];
			for (int j = right[i]; j != i; j = right[j]) {
				remove(col[j]);
			}
			dance(dep + 1);
			for (int j = left[i]; j != i; j = left[j]) {
				resume(col[j]);
			}
			--ans;
		}
		resume(c);
		return;
	}
};
int main() {
	scanf("%d", &n);
	DLX solver;
	solver.init(6 * n - 2);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int idx = i * n + j + 1;
			solver.link(idx, i + 1);
			solver.link(idx, n + j + 1);
			solver.link(idx, 2 * n + 1 + i + j);
			solver.link(idx, 4 * n + n + j - i - 1);
		}
	}
	solver.dance(0);
	std::sort(board, board + board_cnt, cmp);
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < n; ++j) {
			if (j > 0)printf(" ");
			printf("%d", board[i].a[j]);
		}
		printf("\n");
	}
	printf("%d\n", board_cnt);
	return 0;
}

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

参考
https://zhuanlan.zhihu.com/p/22846106