上QQ阅读APP看书，第一时间看更新
3.5.2 实践演练——解决“八皇后”问题
为了说明试探算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解试探法算法思想在编程中的基本应用。
1．问题描述
“八皇后”问题是一个古老而著名的问题，是试探法的典型例题。该问题由19世纪的数学家高斯于1850年手工解决：在8×8的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
2．算法分析
首先将这个问题简化，简化为4×4的棋盘，你知道有两种摆法，每行摆在列2、4、1、3或列3、1、4、2上。
输入：无。
输出：显示一种可行方案，可以随时调整并显示新的方案。例如，［7,3,0,2,5,1,6,4］就是一种正确的方案。
试探算法将每行的可行位置入栈（就是放入数组a[5]，用的是a[1]～a[4]），不行就退栈换列重试，直到找到一套方案并输出。接着从第一行换列重试其他方案。
3．具体实现
在下面的实例文件bahuang.py中，演示了使用试探法解决八皇后问题的过程。为了简化问题，考虑到8个皇后不同行，则每一行放置一个皇后，每一行的皇后可以放置于第0～7列，我们认为每一行的皇后有8种状态。那么，我们只要套用子集树模板，从第0行开始，自上而下，对每一行的皇后，遍历它的8个状态即可。
源码路径：daima\第3章\bahuang.py
n = 8
x = [] # 一个解（n元数组）
X = [] # 一组解
# 冲突检测：判断 x[k] 是否与前面的x[0]~x[k-1]冲突
def conflict(k):
global x
for i in range(k): # 遍历前面的x[0]~x[k-1]]
if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k): # 判断是否与x[k] 冲突
return True
return False
# 套用子集树模板
def queens(k): # 到达第k行
global n, x, X
if k >= n: # 超出最底行
# print(x)
X.append(x[:]) # 保存（一个解），注意x[:]
else:
for i in range(n): # 遍历第 0~n−1 列（即n个状态）
x.append(i) # 皇后置于第i列，入栈
if not conflict(k): # 剪枝
queens(k + 1)
x.pop() # 回溯，出栈
# 解的可视化（根据一个解x，复原棋盘。'X'表示皇后）
def show(x):
global n
for i in range(n):
print('. ' * (x[i]) + 'X ' + '. ' * (n - x[i] - 1))
# 测试
queens(0) # 从第0行开始
print(X[-1], '\n')
show(X[-1])
执行后会输出：
[7, 3, 0, 2, 5, 1, 6, 4] . . . . . . . X . . . X . . . . X . . . . . . . . . X . . . . . . . . . . X . . . X . . . . . . . . . . . . X . . . . . X . . .