python爬山算法解决八皇后问题

问题表述为：在8×8的国际象棋棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法

使用爬山算法解决八皇后问题，思路：

1. 先初始化皇后位置，使得每一行每一列一个有且仅有一个皇后

2. 计算冲突的皇后数量(计做冲突值)，比如同一行、同一列、同一斜线的数量

3. 准备移动皇后，但是往哪移动呢？每一行皇后只能在自己所在行移动，所以只有列会改变

    比如把第一行皇后从（0,1）移动到（0,0），那么整个棋局的冲突值会发生改变（假设冲突值变小了6->5），此时记录为(0,0):5

   然后遍历所有空位，记录移动到此空位时所有皇后的对应冲突值

4. 找到棋盘中所有空位的冲突值最小的位置，随机选择一个冲突值最小空位置，移动所在行皇后此位置，然后重复上一步3的动作，重新计算棋盘上所有皇后冲突值和所有空位冲突值，循环动作3，直到所有皇后的冲突值为0，此时已经找到一组正确的8皇后位置

5.到第四步已经完成了爬山算法，但是爬山算法有个缺点，有可能找到局部最优，而不是全局最优

   以本案为例他只找到了一组最佳位置，但事实上有很多组。此时可以随机生成多个初始位置(也就是爬山起点分散多个地方)，就可以找到不同的最佳答案了

代码如下：

import random, copy, time

"""
解决8皇后问题
初始化
随机生成皇后位置,使其不同列、不同行只有一个
"""


def init():
    # 随机生成皇后位置,使其不同列、不同行只有一个
    status = []
    for r in range(8):
        while len(status) <= 8:
            c = random.randint(0, 7)
            if c not in [mm[1] for mm in status]:
                status.append((r, c))
                break
    return status


"""
遍历所有皇后
计算有冲突的皇后坐标(同一行，同一列，斜边)
计算整个棋盘冲突的数量
假设初始化传入皇后位置：
[(0, 3), (1, 6), (2, 7), (3, 0), (4, 2), (5, 1), (6, 4), (7, 5)]
"""


def conflict(status):
    num = 0  # 存储冲突数量
    conflict_chess = []
    for pos in status:
        for other_pos in status:
            if pos == other_pos or pos in conflict_chess:
                continue
            elif pos[0] == other_pos[0] or pos[1] == other_pos[1] or abs(pos[0] - other_pos[0]) == abs(
                    pos[1] - other_pos[1]):
                num += 1
                conflict_chess.append(pos)

    return num, conflict_chess


"""
遍历所有空位