n皇后问题

Posted on | In , |

回溯法

a数组 填入一个元素开始向列，正对角线，反对角线试探
disp 数组记录一组成功的解

基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉

1）x=row(在纵向不能有两个皇后)

2) y=col（横向）

3）col + row = y+x;（斜向正方向）

4) col - row = y-x;（斜向反方向）

遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。

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
#include<iostream>
#include<cstring>
using namespace std;
//tot解决方案
int n,tot=0; 
int a[100];
int disp[16];
void search(int cur){
	if(cur==n){
		for(int i=0;i<n;i++)
			cout<<disp[i]<<" ";
		cout<<endl;
		tot++;
	} 
else for(int i=0;i<n;i++)
	{
	bool ok=true;
	a[cur]=i;
	for(int j=0;j<cur;j++){
	if(a[cur]==a[j]||a[cur]-a[j]==cur-j||a[cur]+cur==a[j]+j)
	{
		ok=false;
		break;
	}
}
	if(ok) {
		disp[cur]=i;
		search(cur+1);
	}
	}
}
int main()
{
	cin>>n;
 memset(a, 0, sizeof(a));
	search(0);
	cout<<tot<<endl;
}

也可以不用disp数组

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
#include<iostream>
#include<cstring>
using namespace std;
int n,tot=0; 
int a[100];

void search(int cur){
	if(cur==n){
		for(int i=0;i<n;i++)
			cout<<a[i]<<" ";
		cout<<endl;
		tot++;
	} 
else for(int i=0;i<n;i++)
	{
	bool ok=true;
	a[cur]=i;
	for(int j=0;j<cur;j++){
	if(a[cur]==a[j]||a[cur]-a[j]==cur-j||a[cur]+cur==a[j]+j)
	{
		ok=false;
		break;
	}
}

	if(ok) {
		a[cur]=i;
		search(cur+1);/递归深度优先搜索解空间树
		
	}
	else{
	a[cur]=0;////这句代码就是实现回溯到上一层
	}
	}

	
}

int main()
{
	cin>>n;
 memset(a, 0, sizeof(a));
	search(0);
	cout<<tot<<endl;
}

类似解法
直接用vis数组判断三个条件;

  • 当前要填的是否与之前列冲突

  • 行+列是否为定值

  • 行-列是否为定值

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
#include <bits/stdc++.h>
using namespace std;

const int MaxN = 50;
int n, tot, pos[MaxN];
bool vis[3][MaxN];

void dfs(int cur)
{
    int i, j;
    if (cur == n) tot++;

    {
        if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
        {
            pos[cur] = i;
            vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
            dfs(cur + 1);
            vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
        }
    }
}

int main()
{
    #define QUERY(X) { \
                n = X, tot = 0; \
                memset(vis, 0, sizeof(vis)); \
                dfs(0); cout << tot << endl; \
                }
    QUERY(8);
    return 0;
}

参考网站
http://www.cnblogs.com/jillzhang/archive/2007/10/21/922830.html
https://github.com/zhsj/nqueen/blob/master/N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.md
http://www.cnblogs.com/grandyang/p/4377782.html
https://blog.csdn.net/qinghezhen/article/details/17849837