提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  工具

当前栏目

n皇后学习

学习 皇后
2023-09-14 09:06:47 时间

洛谷P1219

回溯

#include<cstdio>
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;
}

但是最后13的时候会T
在这里插入图片描述

优化1

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

#include<cstdio>
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改成用位运算

#include<cstdio>
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;
}

位运算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<cstdio>
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;
}

位运算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<cstdio>
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;
}

舞蹈链

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

但是注意一点，对角线是无法完全覆盖的
比如下面的图，第3条副对角线就没有覆盖
在这里插入图片描述
所以如果行和列覆盖完了就可以返回了

#include<cstdio>
#include<cstring>
#include<algorithm>

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;
}

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

相关文章