【dfs】n皇后两种解法

本当迷

2022 年 03 月 15 日

979 次浏览

暂无评论

492字数

算法认知

N 皇后问题是指将 N 个皇后放置在 N×N 棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

## 第一种解法：

我们可以把n皇后变换成全排列问题，每一行都有皇后，每一列只能有一个皇后，我们对列进行全排列的问题就可转换成n皇后问题了！

```cpp
#include<bits/stdc++.h>
using namespace std;

const int L = 12;

int n;
char arr[L][L];
bool lie[L], z_x[2 * L], n_z_x[2 * L];

bool check(int x, int y){
	if(!lie[x] && !z_x[n + y - x] && !n_z_x[y + x])return true;
	return false;
}

void dfs(int y){
	if(y == n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cout << arr[i][j];
			}
			cout << endl;
		}
		cout << endl;
		return;
	}
	for(int x = 0; x < n; x++){
		if(check(x, y)){
			lie[x] = z_x[n + y - x] = n_z_x[y + x] = true;
			arr[y][x] = '&';
			dfs(y+1);
			arr[y][x] = '*';
			lie[x] = z_x[n + y - x] = n_z_x[y + x] = false;
		}
	}
}

int main(){

cin >> n;
	for(int i = 0; i < n; i++)
	    for(int j = 0; j < n; j++)
		    arr[i][j]='*';
	dfs(0);

return 0;
} 
```

## 第二种解法：

我们直接暴搜，每一行，每一列的搜！

```cpp
#include<bits/stdc++.h>

using namespace std;
int n;

bool row[100], col[100], dg[100], udg[100];
char a[100][100];

void dfs(int x, int y, int k) {
	if(y == n) y = 0, x ++;
	if(x == n) {
		if(k == n) {
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					cout << a[i][j];
				}
				cout << endl;
			}
			cout << endl;
		}
		return;
	}
	dfs(x, y + 1, k);
	if(!row[x] && !col[y] && !dg[x+y] && !udg[x - y + n]){
		a[x][y] = 'Q';
		row[x] = col[y] = dg[x+y] = udg[x - y + n] = true;
		dfs(x, y + 1,  k + 1);
		row[x] = col[y] = dg[x+y] = udg[x - y + n] = false;
		a[x][y] = '.';
	}
}

int main() {

cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			a[i][j] = '.';
		}
	}
	dfs(0, 0, 0);
	return 0;
}
```

最后修改：2022 年 03 月 15 日