8皇后问题

题目:

如何能够在8×8的国际象棋棋盘上放置8个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

因为在国际象棋中,皇后可以横、直或者斜着走,格数不限,所以棋盘中任意2个皇后都不能在同一行、同一列以及同一斜线。

思路:

依次检测同一行、同一列以及同一斜线有没有皇后,如果没有就检测下一行。累计检测满八个皇后就记一种解法。

一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉:

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

  2. y=col(横向)

  3. col + row = y+x;(斜向正方向)

  4. col - row = y-x;(斜向反方向)

我们用 queen[x]来表示 第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
#-*- coding:utf-8 -*-
# python Solution
# 检查有没有在同一列或者同一斜线
# 同一行不用检测因为后面皇后的行数是递增的
def available(row,col):
for x in range(row):
if queen[x]==col or x - queen[x] == row - col or queen[x] + x == row + col:
return False
return True

def find(row):
# 如果不冲突就记下当前的row和queen[row](列)
# 然后检查下一行
global count,queen
if row == 8:
count += 1
else:
for col in range(8):
if available(row,col):
queen[row] = col
# 递归
find(row+1)


if __name__ == '__main__':
global count,queen
count = 0
queen = [-1]*8
find(0)
print count
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
//Java Solution
public class Queen8 {

int[] queen = new int[8];

int count = 0;

public Queen8() {
find(0);
System.out.println(count);
}
// 检查有没有在同一列或者同一斜线
// 同一行不用检测因为后面皇后的行数是递增的
public boolean avaliable(int row,int col) {
for (int x = 0;x<row;x++){
if (queen[x]==col || x-queen[x]==row-col || x+queen[x]==row+col) {
return false;
}
}

return true;
}

public void find(int row) {
if (row == 8) {
count++;
}
else {
for (int col = 0;col<8;col++) {
if (avaliable(row, col)) {
queen[row] = col;
// 递归
find(row+1);
}
}
}
}

public static void main(String[] args)
{
Queen8 queen8 = new Queen8();
}

}

非递归(回溯法)

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

算法描述如下:

  1. 开始时清空棋盘,将当前行设为第零行,当前列设为第零列。
  2. 判断当前位置是否合法,若不合法到第4步。
  3. 当前位置合法,则在当前位置放置一棋子。
    • 若当前行为最后一行,则记录一个解。
      • 若当前列是最后一列,当前行设为前一行,当前列设为当前行对应列的下一列。
      • 若当前列不是最后一列,当前列设为下一列.
    • 若当前行不是最后一行,则将当前行设为下一行,当前列设为第零列。
      回至第2步。
  4. 当前位置不合法。
  • 若当前列不是最后最后一列,则当前列设为下一列,回到第2步。
  • 若当前列是最后一列
    • 若当前行为第零行,结束
    • 若当前不是第零行,当前行设为前一行,当前列设为当前行对应列的下一列。
      回至第2步。
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
#-*- coding:utf-8 -*-
def available(row,col):
for x in range(row):
if queen[x]==col or x - queen[x] == row - col or queen[x] + x == row + col:
return False
return True

def find():
count = 0
row = 0
global queen
queen[row] = 0
while row>=0: #当前行为 -1 时结束
if row < 8 and queen[row] < 8: #当前行、当前列均为到达最后
if available(row,queen[row]): #当前位置合法,则探索下一行
row += 1
queen[row] = 0
else:
queen[row] += 1
else: #当前位置不合法,探测当前行的下一个位置
if row>=8: #当前行、当前列均到了最后,记录一个解
count+=1
row -= 1 # 返回上一行,继续探索
queen[row] += 1
return count

if __name__ == '__main__':
global queen
queen = [-1]*9
print find()
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
public class Queen8 {

int[] queen = new int[9];

public Queen8() {

System.out.println(find());
}

public boolean avaliable(int row,int col) {
for (int x = 0;x<row;x++){
if (queen[x]==col || x-queen[x]==row-col || x+queen[x]==row+col) {
return false;
}
}

return true;
}

public int find() {
int count = 0;
int row = 0;
queen[row] = 0;
while (row >= 0) {
if (row<8 && queen[row]<8) {
if (avaliable(row, queen[row])) {
row++;
queen[row] = 0;
}
else {
queen[row]++;
}
}
else {
if (row>=8) {
count++;
}
row--;
System.out.println(row);
if (row>=0) {
queen[row]++;
}


}

}
return count;
}
public static void main(String[] args)
{
Queen8 q = new Queen8();
}

}

参考:
http://www.cnblogs.com/jillzhang/archive/2007/10/21/922830.html
https://baike.baidu.com/item/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://github.com/zhsj/nqueen/blob/master/N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98.md

打赏