八皇后问题

  • 问题介绍
  • 解题思路
  • 实例代码

问题介绍(来源百度百科)

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有 76 种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出 92 种结果。计算机发明后,有多种计算机语言可以解决此问题。

解题思路

回溯算法

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

步骤

  1. 先选择棋盘中的一个点
  2. 判断该点是否满足放置要求
  3. 满足则将该位置设置标志位,不满足则不放置
  4. 寻找下一个点
  5. 循环 2,3,4 步骤直至遍历整个棋盘

实例代码(Python)

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
# 用于记录有多少种解法
count = 0
# 生成棋盘
arr = [[0 for i in range(8)] for j in range(8)]


# 检查这个坐标是否可以放棋子
def check(row, col):
# 设置全局可修改 arr
global arr
# 检查行列
for i in range(row):
if arr[i][col] == 1:
return False

# 检查左对角线
for (i, m) in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if arr[i][m] == 1:
return False

# 检查右对角线
for (i, m) in zip(range(row - 1, -1, -1), range(col + 1, 8)):
if arr[i][m] == 1:
return False

return True


# 开始布局
def findQueen(row):
global count
global arr
# 如果存在某一种情况则加一
if row > 7:
count = count + 1
return

for col in range(8):
if check(row, col):
# 棋子放置的位置设置为 1
arr[row][col] = 1
findQueen(row + 1)
# 将数据归 0 防止出现脏数据
arr[row][col] = 0


if __name__ == '__main__':
print("八皇后问题")
findQueen(0)
print(count)
坚持原创技术分享,您的支持将鼓励我继续创作!