Ea5ter's Bolg

八皇后问题

字数统计: 824阅读时长: 3 min
2018/09/15 Share

之前在学搜索算法时的时候知道了这个经典问题,今早有点闲就来做了一下。明天考计算机二级,顺便复习下C语言。

问题描述

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

问题分析

先想想我们该如何走?

第一步先在第一行第一列放一颗子:

因为没有其它棋子,这样摆是没问题的,然后再在第二行第一列摆一颗:

当然,这样出错了,因为不能摆同列所以应该换到下一列,直到满足我们的约束条件。

然后继续下一行……

代码实现

继续想想,如果出现一行没有一个位置可以摆的情况该怎么办?那么就要回溯到上一行,将棋子移到下一个可行位置。
如此一来我们可以用递归的思想写出一个 demo :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Queen_N(int x, int y){ // x、y为上个棋子的行、列
int i, j;// i 为当前处理行,j 为当前处理列

i = x + 1;
if (x == N - 1){ // 摆完最后一行的棋子回溯
return ;
}
for (j = 0; j < N; j++){ //
if (){ // 判断约束条件
Queen_N(i, j); // 满足约束条件递归,到下一行
}
}
return ; // 所有情况都不满足,回溯。

}

这样以来问题就清晰了许多,现在我们要解决的问题就是约束条件。
我们知道二维数组中同一条斜线上的元素脚标之和、脚标之差相等。于是我们可以创建一个二位数组 a[N][3] 用来记录每一行的脚标和(a[N][0])、脚标差(a[N][1])、列坐标(a[N][2])。
接下来我们就可以写出比较函数Compare() 。

1
2
3
4
5
6
7
8
9
10
11
12
int Compare(int x, int y){
int i;

for (i = 0; i < x; i++) // 比较x行之前的棋子
{
if (x + y == a[i][0] || x - y == a[i][1] || y == a[i][2])
{
return 0;
}
}
return 1;
}

于是我们就可以写出完整代码:

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
#include<stdio.h>
#define N 8

int a[N][3];
int b[N][2];

void display(){
int i, j;
static kk = 0;

printf("\n--------- %d --------\n", ++kk);
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{

if (i == b[i][0] && j == b[i][1])
{
printf(" #");
}
else
printf(" 0");
}
printf("\n");
}
printf("\n---------------------\n");
}

int Compare(int x, int y){
int i;

for (i = 0; i < x; i++)
{
if (x + y == a[i][0] || x - y == a[i][1] || y == a[i][2])
{
return 0;
}
}
return 1;
}

void Queen_four(int x, int y){
int i, j;

i = x + 1;
if (x == N - 1){
display();
return ;
}
for (j = 0; j < N; j++){
if (x == -1 || Compare(i, j)){
a[i][0] = i + j;
a[i][1] = i - j;
a[i][2] = j;
b[i][0] = i;
b[i][1] = j;
Queen_four(i, j);
}
}
return ;

}

int main(){
Queen_four(-1, -1);
return 0;
}

总的来说还是很简单的,网上应该还有更优解,不过我这没有搜。在知乎上瞟到了一个“如何在十行内解决八皇后问题”,这还真是阔怕……

CATALOG
  1. 1. 问题描述
  2. 2. 问题分析
  3. 3. 代码实现