N皇后

序言

N皇后问题一直是一个百炼不厌的题目写着一篇主要是为了深入理解和学会N皇后
学习N皇后的主要思想和解题思路
主要运用到的方法有,递归,DFS,遗传算法和CSP最小冲突法
要说的一点是,因为本人比较菜,所以遗传算法和最小冲突法还没有学会

N皇后问题:

描述:

1
2
3
4
N皇后问题是一个古老而著名的问题,是回溯算法的典型案例。该问题由西洋棋棋手马克斯·贝瑟尔于1848年提出。
在国际象棋上,N皇后问题变成了8皇后问题,著名的数学家高斯认为有76种方案,后来有人用图论的知识解出92种结果,计算机发明后,
可以通过算法实现问题的求解。8皇后问题是指在8*8的棋盘上摆放8个皇后,使得任意两个皇后都不在同一行、同一列或者同一斜线上,
求满足这种摆放的解为多少个。(答案是92种)学会了8皇后以后,N皇后自然就迎刃而解了。

提交问题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2553

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input 
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。

Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

Sample Input
1
8
5
0

Sample Output
1
92
10

解题思路:

首先要模拟一下:

1.递归算法:

1
2
3
我们逐列放皇后(从小到大逐列摆放),现在先给第一列放皇后,很显然我们会把它放在第一行,
接下来,给第二列放皇后,那么第二列的皇后能放在哪些位置?这时候需要一个判断函数来判断第二列的皇后能放在那里。
如果第二列找到放皇后的某一行,那么就进行第三列的摆放,这里就是递归。

2.回溯法:

1
2
3
如果还没有进行到最后一列的摆放时就已经不能再放皇后,那么此时需要怎么做?就返回递归的前面一次,
把当前列的前面一列的皇后放在后面的行数上(从小到大逐行检验)。如果此时逐行检验已经遍历完所有的行数还是出现上面不能摆放的情况,
那就在再返回上一次的递归,在进行逐行检验。这里就是回溯。

3.递归算法的终止条件:

1
2
3
4
由初始条件知道,第一行第一列放皇后,那么会不会有第一行第一列不放皇后的情况呢?
我们能不能把这个位置放空,然后把第一列的皇后放在第二行上,或者更后面的一行。答案是肯定能的。那么问题来了,程序在运行到什么时候会进行这样的处理?
当第一行第一列放皇后的所有情况都已经遍历完之后,就会把第一列的皇后放在第二行上,再把这个情况都遍历完,然后又把第一列的皇后放在第三行上,依次类推,
直到把第一列的皇后放在最后一行上,当遍历完成时,递归终止。

4.遗传算法:

1
2
3
4
5
6
7
8
9
10
是随机剪枝搜索的一个变化形式。它通过把两个父状态结合来生成后继。算法模拟大自然的自然选择、基因杂交和变异。
其中自然选择依据适应值的大小来评估被选中的概率,让更加优质的父状态更有可能传给下一代。生成种群、杂交、和变异
都是依赖随机数和概率来模拟“物竞天择,适者生存”的自然法则。算法不断Select, Crossover, Mutate直到产生了一个最优解。

一个棋盘可以看成是一条染色体,统称为“状态”,一个棋盘中的皇后可以看成一个基因。我不断调整种群数量的大小、适应值函数、杂交的策略、还有变异的概率,
逐渐发现了更加优秀的参数。以下是我的实验结论:
假设是N皇后,那么种群的数量最优是4N
课本《人工智能:一种现代的方法》上的适应值函数不好,稍微改进一点的适应值函数 f = 冲突皇后对的个数的倒数,这样能够拉开优质和劣质个体被选的概率。
课本上面的“单点+双侧”杂交(随机选择单个杂交点,这个杂交点的两侧都交换)的效果不佳,不如“单点+单侧”杂交,也不如“双点+双点之间”杂交。
单个基因(一个皇后)变异的概率小于0.05,比如0.04的时候,效果较好。

5.CSP最小冲突法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
局部搜索对求解不少constraint satisfy problem有着很棒的效果。N皇后问题就是一个约束满足问题,这里的约束,就是指“皇后之间不能冲突”。
该算法使用完全状态的形式化:初始状态每个变量都赋一个值,后继函数每一次改变一个变量的取值,改变取值的依据是使冲突最小化——最小冲突启发式。
如果最小冲突值有多个,那么按照一定的概率选择。(经过大量反复实验发现,CSP最小冲突法存在极小概率的不完备性,即永远也找不到满足约束条件的最优解,
当遇到此情况的时候,可以选择退出当前的求解,重新生成一个新的初始状态再来一次)

该算法最精彩的地方,是时间复杂度可以优化到O(n^2),于是可以在几秒内解决1万皇后的问题,在几十分钟内解决几万甚至10万皇后的问题!
这是前两种算法完全无法比拟的。时间复杂度优化到O(n^2)有一点代价,那就是多付出一些空间复杂度。多出来的空间复杂度是O(n),
这个和优化的时间复杂度(从O(n^4 ) 到O(n^2))相比,可以说是微不足道的,完全值得的。多出来三个vector,分别用来存储一个棋盘上的(以 8 皇后为例):

8个垂直方向的皇后数量
15个主对角线方向的皇后数量
15个反对角线方向的皇后数量

那么,一个皇后的冲突数量,就是这三个vector中的相应的值相加,利用下标转换关系可以做到。
这样计算一个皇后的冲突数量,就可以在常数时间内完成。这是十分吸引人的!当然,每一次放置皇后和移开皇后的时候,
需要更新上述三个vector的相应值,维护这三个vector也需要时间开销,不过这也是常数。

检测一个状态是否达到最优状态的时候,只需要判断每一个垂直方向(列)上面的皇后数量是否为1,主对角线和反对角线方向上的皇后数量是否是0或者1即可,这个时间复杂度是O(n)

6.思路实现:

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
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

#define Max 20 //表示最大的棋盘边长,可以自定义为其它数据
int pos[Max+1]; //为什么只需要定义一个一维数组就能描述二维的棋盘?
//pos[i]是这样定义的:即第i列的皇后放在第pos[i]行上,
// 也就是说,pos[i]的索引i代表皇后所在的列,它的值pos[i]代表皇后所在的行
int n; //棋盘的边长和皇后的数量
int sum; //可以成功摆放的数量,每次遍历成功就加1

bool checkNQ(int col){ //对第col之前的列进行逐列检查,pos[i]中i的值为列,pos[i]的值为行
for(int i=1;i<col;i++)
if(pos[i]==pos[col]||abs(i-col)==abs(pos[i]-pos[col])) //如果行数相同,或者行数相减的绝对值等于列数相减的绝对值 //此时都不能放皇后,因为对第col列之前的列进行逐列检查, //所以不需要再进行列是否相同的判断
return false;
return true;
}

void dfsNQ(int col,int n){
if(col==n+1) //成功遍历一次,sum加1,然后继续探索其他情况
sum++;
for(int i=1;i<=n;i++){
pos[col]=i;//假设第col列的皇后放在第i行上,然后利用checkNQ()函数检查是否能放入
//第一种情况,如果能放入,则继续假设下一列也放在第i行(实际上第i行此时已经不能放了,
//所以cheakNQ()函数就会直接返回false,
//然后上面的for循环中的i自动加1,即假设第col+1列放在第i+1行,然后又继续检查能否放入。
//第二种情况,如果不能放入,for循环中的i就自动加1,即假设第col列的皇后放在第i+1行上,
//又继续检查能否放入
//如果当col<=n时(即列还没有遍历完)再也不能在任何一行放皇后,那么此时dfsNQ中的for循环的i已经
//遍历完,dfsNQ就会返回到上一级的dfsNQ(col+1,n),此时col就会自动减1(因为每次递归都是加1),
//然后,尝试第col列的皇后能否放在第i+1行上,如此进行回溯。
if(checkNQ(col))
dfsNQ(col+1,n); //进行递归
}
}
int main()
{
cout<<"请输入皇后的数量:";
cin>>n;
dfsNQ(1,n); //传入第一列和n,从第一列开始放皇后。
cout<<endl<<"满足条件的所有摆放次数为:";
cout<<sum;
return 0; //说明:dfsNQ函数完全退出的条件是所有满足条件的情况都已经遍历过,再也没有满足条件的遍历
//根据递归的初始化分析得知,前面的遍历都会默认第一行第一列的位置会放皇后,
//然而实际情况是这个位置不放皇后也能满足条件的次数甚至更多,那么程序在运行到什么时候会把
//第一行第一列的位置放空呢?答案是当第一行第一列放皇后的满足条件的所有遍历都结束时,
//就会把第一列的皇后放在第二行,而把第一行第一列的位置放空。
//如此进行到最后,最后面是把第一列的皇后放在最后一行,
//然后再全部遍历,结束时整个dfsNQ函数递归运行结束。主函数return 0.
}

7.代码实现

希望看到这里的你不要只是复制粘贴来过题(ctrl+cv),因为这样做,没有任何意义

1
2
3
4
5
6
7
8
9
10
11
12
13
简单方法之打表法(极度不推荐,如果这样做,将学不会N皇后的精髓算法如DFS/回溯法/递归算法)
#include <iostream>
using namespace std;
int n=1,x[11]={0,1,0,0,2,10,4,40,92,352,724};
int main()
{
while(n!=0)
{
cin >> n;
if(n!=0) cout << x[n] << endl;
}
return 0;
}
1.C语言实现
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

#include<stdio.h>
int a[15],ans[15],num,l,m,n,k,r;

void dfs(int x)//搜索第x行可不可以放皇后
{
if(x==n+1)//当查找到第n+1行是结束
{
l++;
return;
}
else
{
for(int i=1;i<=n;i++)//搜索第x行的第i列可不可以放皇后
{
a[x]=i;//假设将皇后放在第i列,标记
r=1;
for(int j=1;j<x;j++)
{
if(a[j]==i||i-x==a[j]-j||i+x==a[j]+j)//第一句查询第j列是否已经放了皇后,第二三句查询对角线上是否放了皇后,算一遍就清楚了
{
r=0;//如果有,就退出去进行下一次循环,代表这个地方不能放皇后
break;
}
}
if(r==1) dfs(x+1);
}
}
}

int dabiao()//题目中说了n不大于10,所以可以直接打表
{
for(n=1;n<=10;++n)
{
l=0;
dfs(1);
ans[n]=l;
}
}

int main()
{
dabiao();
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
printf("%d\n",ans[n]);
}
return 0;
}
2.C++语言实现
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

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int vis[3][50], P[15];//三个方向 ↖↑↗在此三个方向都不能有皇后
int n, sum;

void DFS(int row);

int main()
{
for(n = 1; n <= 10; n++)//先打表不然会超时的
{
memset(vis,0,sizeof(vis));
sum = 0;
DFS(1);
P[n] = sum;
}
while(scanf("%d",&n), n)
{
printf("%d\n",P[n]);
}
return 0;
}

void DFS(int row)
{
int i;
if(row == n + 1)//已经够n行了
{
sum ++;
return ;
}
for(i = 1; i <= n; i++)
{
if(vis[0][row-i+n] == 0 && vis[1][i] == 0 && vis[2][row+i] == 0)
{//不会回溯的应该好好看看学习学习
vis[0][row-i+n] = vis[1][i] = vis[2][row+i] = 1;//变值
DFS(row + 1);//深搜
vis[0][row-i+n] = vis[1][i] = vis[2][row+i] = 0;//回溯
}
}
}
3.遗传算法伪代码:
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
//主循环 
void Genetic::GeneticAlgorithm()
while m_NotSuccess为真
Select
Crossover
Mutate
End while
打印最优解
End

//计算一个state(棋盘)的适应值
//适应值采用“互相攻击皇后对的个数的倒数”,这比书上直接计算不互相攻击的皇后对数作为适应值的方法相比,更能拉开不同状态之间的差距。
//@para state:一个状态的引用
double Genetic::CalcuAdaptive(vector &state)
counter←0
For i: 0 to QueenNum-1 do
For i: 0 to QueenNum-1 do
If 对角线方向互相攻击,或者垂直方向互相攻击
counter++
End if
End for
End for
If counter等于0
m_NotSucess←false,程序的循环终止条件
m_BestOne←state,保存当前的状态
End if
Return 1.0/counter
End

//自然选择,大体思路是轮盘赌选择
void Genetic::Select()
创建一个新的空种群newPopulation
For i: 1 to populationSize-1 do
m_accumuAdaptive[i]←m_accumuAdaptive[i - 1] + m_adaptive[i]
End for
totalAdaptive←m_accumuAdaptive的最后一个元素
For i: 0 to populationSize-1 do
先把totalAdaptive(这是一个实数)放大成一个整数
产生一个随机数 ,对totalAdaptive求模,得到 ran
按相同比例缩小成一个实数
用二分查找的方法,在m_ accumuAdaptive内进行查找 ran,找出位置 j
把m_population的第 j 个状态push_back到newPopulation中
End for
m_population←newPopulation
End

杂交有多种思路:


选择两个state状态,随机产生一个杂交点,然后对这个杂交点的右(左)边的“基因”进行交换
选择两个state状态,随机产生一个杂交点,然后再对这个杂交点两边的“基因”都进行交换。
选择两个state状态,随机产生两个杂交点,然后再对这两个杂交点之间的“基因”进行交换。


变异:
通过伪随机数,使每一个基因有0.0几的概率进行突变。突变就是用伪随机数赋值。

??:

4.CSP最小冲突法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
以下是主循环的伪代码 
void MinConflict::MinConflictAlgorithm()
While 没有找到最优解
For row: 0 to QueenNum-1 do
移开棋盘row这一行的皇后
更新相应的三个保存皇后数量的vector
For column: 0 to QueenNum do
计算(row, column)位置的冲突值,常数时间
If 比之前的 min 更小
更新最小值 min, 更新此时的 columnMin
Else if 和之前的最小值相等
50%概率更新最小值min,更新此时的 columnMin
End if
End for
放置皇后到冲突最小的地方(row, columnMin)
更新相应的三个保存皇后数量的vector
如果检测达到了最优状态,即找到了最优解,break For
End for
End while
打印最优解
End

比较效果:

遗传算法和CSP最小冲突法的比较:

---------------- The End ----------------
0%