赞
踩
问题表述为:在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
-
-
- """
- 遍历所有空位
- 计算当行的皇后移动到此空位时整个棋盘的冲突值
- 会得出8*8-8 = 56个冲突值
- 也就是56种移动方法
- 选择冲突值最小的一种进行移动
- """
-
-
- def move_chess(status):
- empty_pos = {} # 用字典保存所有空位冲突值
-
- for r in range(8):
- for c in range(8):
- if (r, c) not in status:
- new_status = copy.deepcopy(status)
- new_status[r] = (r, c)
- empty_pos[(r, c)] = conflict(new_status)[0]
- else:
- continue
- return empty_pos
-
-
- """
- 循环获取冲突数量
- 若数量>1,执行move_chess
- 指导冲突数量=0,此时寻找到最佳位置
- """
-
-
- def climbing(status):
- # 获取当前皇后位置的冲突值
- conflict_num = conflict(status)[0]
- # 设置循环次数,避免一直循环,冲突值一直无法降到最低0时,自动跳出循环
- # 设置移动皇后500次,如果找不到正确位置就重新初始化皇后位置
- loop_cnt = 0
- while conflict_num != 0 and loop_cnt < 500:
- # 获取所有空位冲突值
- empty_pos = move_chess(status)
- min_value = min(empty_pos.values())
- # 获取最小冲突值对应的key 即坐标pos
- min_pos_ls = []
- for k, v in empty_pos.items():
- # print(v, min_value)
- if v == min_value and (k not in min_pos_ls):
- min_pos_ls.append(k)
-
- # print(min_pos_ls, min_value)
- # print(status)
- # 随机取一个空位点,与当前同一行皇后交换位置,然后计算所有空位置的冲突值和当前棋局内皇后自身冲突值
- i = random.randint(0, len(min_pos_ls) - 1)
- status[min_pos_ls[i][0]] = min_pos_ls[i]
- conflict_num = conflict(status)[0]
- loop_cnt += 1
- return status, loop_cnt
-
-
- if __name__ == '__main__':
-
- # 这一个随机数会导致一直找不到最高点
- # status = [(0, 0), (1, 2), (2, 4), (3, 3), (4, 1), (5, 5), (6, 7), (7, 6)]
- # climbing(status)
-
- """
- 生成随机位置,迭代600次尽可能多的找出八皇后不同位置
- """
- start = time.time()
- all_pos = []
- for i in range(600):
- status = init()
- # 设置loop_cnt防止一直陷入死循环无法找到最佳点
- # 如果一直找不到就跳出来并且重新生成初始位置
- status, loop_cnt = climbing(status)
- # print(loop_cnt)
- if loop_cnt == 500:
- continue
- elif status not in all_pos:
- all_pos.append(status)
- end = time.time()
- print("一共找到{}组八皇后位置,共耗时{}s".format(len(all_pos), end - start))
- for pos in all_pos:
- print(pos)
运行结果如下:
- C:\Users\LU\.conda\envs\ai_course\python.exe C:/Users/LU/PycharmProjects/ai_course/eight_queens_2d.py
- 一共找到92组八皇后位置,共耗时31.383877515792847s
- [(0, 5), (1, 3), (2, 1), (3, 7), (4, 4), (5, 6), (6, 0), (7, 2)]
- [(0, 1), (1, 4), (2, 6), (3, 0), (4, 2), (5, 7), (6, 5), (7, 3)]
- [(0, 5), (1, 2), (2, 0), (3, 6), (4, 4), (5, 7), (6, 1), (7, 3)]
- [(0, 6), (1, 3), (2, 1), (3, 7), (4, 5), (5, 0), (6, 2), (7, 4)]
- [(0, 4), (1, 2), (2, 0), (3, 5), (4, 7), (5, 1), (6, 3), (7, 6)]
- [(0, 4), (1, 2), (2, 0), (3, 6), (4, 1), (5, 7), (6, 5), (7, 3)]
- [(0, 3), (1, 7), (2, 0), (3, 4), (4, 6), (5, 1), (6, 5), (7, 2)]
- [(0, 3), (1, 6), (2, 0), (3, 7), (4, 4), (5, 1), (6, 5), (7, 2)]
- [(0, 4), (1, 6), (2, 0), (3, 2), (4, 7), (5, 5), (6, 3), (7, 1)]
- [(0, 5), (1, 1), (2, 6), (3, 0), (4, 3), (5, 7), (6, 4), (7, 2)]
- [(0, 3), (1, 1), (2, 7), (3, 5), (4, 0), (5, 2), (6, 4), (7, 6)]
- [(0, 5), (1, 7), (2, 1), (3, 3), (4, 0), (5, 6), (6, 4), (7, 2)]
- [(0, 2), (1, 5), (2, 1), (3, 6), (4, 0), (5, 3), (6, 7), (7, 4)]
- [(0, 3), (1, 6), (2, 4), (3, 2), (4, 0), (5, 5), (6, 7), (7, 1)]
- [(0, 4), (1, 1), (2, 3), (3, 5), (4, 7), (5, 2), (6, 0), (7, 6)]
- [(0, 1), (1, 3), (2, 5), (3, 7), (4, 2), (5, 0), (6, 6), (7, 4)]
- [(0, 4), (1, 2), (2, 7), (3, 3), (4, 6), (5, 0), (6, 5), (7, 1)]
- [(0, 3), (1, 5), (2, 7), (3, 1), (4, 6), (5, 0), (6, 2), (7, 4)]
- [(0, 4), (1, 1), (2, 7), (3, 0), (4, 3), (5, 6), (6, 2), (7, 5)]
- [(0, 5), (1, 2), (2, 6), (3, 1), (4, 3), (5, 7), (6, 0), (7, 4)]
- [(0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2)]
- [(0, 5), (1, 3), (2, 0), (3, 4), (4, 7), (5, 1), (6, 6), (7, 2)]
- [(0, 2), (1, 5), (2, 1), (3, 4), (4, 7), (5, 0), (6, 6), (7, 3)]
- [(0, 2), (1, 5), (2, 7), (3, 1), (4, 3), (5, 0), (6, 6), (7, 4)]
- [(0, 4), (1, 6), (2, 1), (3, 3), (4, 7), (5, 0), (6, 2), (7, 5)]
- [(0, 3), (1, 0), (2, 4), (3, 7), (4, 1), (5, 6), (6, 2), (7, 5)]
- [(0, 6), (1, 1), (2, 5), (3, 2), (4, 0), (5, 3), (6, 7), (7, 4)]
- [(0, 6), (1, 1), (2, 3), (3, 0), (4, 7), (5, 4), (6, 2), (7, 5)]
- [(0, 2), (1, 7), (2, 3), (3, 6), (4, 0), (5, 5), (6, 1), (7, 4)]
- [(0, 3), (1, 5), (2, 7), (3, 2), (4, 0), (5, 6), (6, 4), (7, 1)]
- [(0, 2), (1, 4), (2, 6), (3, 0), (4, 3), (5, 1), (6, 7), (7, 5)]
- [(0, 2), (1, 4), (2, 1), (3, 7), (4, 0), (5, 6), (6, 3), (7, 5)]
- [(0, 4), (1, 1), (2, 5), (3, 0), (4, 6), (5, 3), (6, 7), (7, 2)]
- [(0, 6), (1, 0), (2, 2), (3, 7), (4, 5), (5, 3), (6, 1), (7, 4)]
- [(0, 2), (1, 5), (2, 7), (3, 0), (4, 4), (5, 6), (6, 1), (7, 3)]
- [(0, 4), (1, 7), (2, 3), (3, 0), (4, 2), (5, 5), (6, 1), (7, 6)]
- [(0, 2), (1, 0), (2, 6), (3, 4), (4, 7), (5, 1), (6, 3), (7, 5)]
- [(0, 5), (1, 2), (2, 6), (3, 3), (4, 0), (5, 7), (6, 1), (7, 4)]
- [(0, 4), (1, 7), (2, 3), (3, 0), (4, 6), (5, 1), (6, 5), (7, 2)]
- [(0, 5), (1, 3), (2, 6), (3, 0), (4, 7), (5, 1), (6, 4), (7, 2)]
- [(0, 3), (1, 1), (2, 4), (3, 7), (4, 5), (5, 0), (6, 2), (7, 6)]
- [(0, 5), (1, 2), (2, 6), (3, 1), (4, 7), (5, 4), (6, 0), (7, 3)]
- [(0, 5), (1, 3), (2, 6), (3, 0), (4, 2), (5, 4), (6, 1), (7, 7)]
- [(0, 3), (1, 6), (2, 4), (3, 1), (4, 5), (5, 0), (6, 2), (7, 7)]
- [(0, 2), (1, 5), (2, 1), (3, 6), (4, 4), (5, 0), (6, 7), (7, 3)]
- [(0, 6), (1, 4), (2, 2), (3, 0), (4, 5), (5, 7), (6, 1), (7, 3)]
- [(0, 1), (1, 6), (2, 4), (3, 7), (4, 0), (5, 3), (6, 5), (7, 2)]
- [(0, 5), (1, 0), (2, 4), (3, 1), (4, 7), (5, 2), (6, 6), (7, 3)]
- [(0, 5), (1, 2), (2, 4), (3, 6), (4, 0), (5, 3), (6, 1), (7, 7)]
- [(0, 5), (1, 2), (2, 0), (3, 7), (4, 4), (5, 1), (6, 3), (7, 6)]
- [(0, 2), (1, 5), (2, 3), (3, 0), (4, 7), (5, 4), (6, 6), (7, 1)]
- [(0, 2), (1, 5), (2, 3), (3, 1), (4, 7), (5, 4), (6, 6), (7, 0)]
- [(0, 1), (1, 5), (2, 7), (3, 2), (4, 0), (5, 3), (6, 6), (7, 4)]
- [(0, 2), (1, 6), (2, 1), (3, 7), (4, 4), (5, 0), (6, 3), (7, 5)]
- [(0, 4), (1, 6), (2, 3), (3, 0), (4, 2), (5, 7), (6, 5), (7, 1)]
- [(0, 5), (1, 2), (2, 4), (3, 7), (4, 0), (5, 3), (6, 1), (7, 6)]
- [(0, 5), (1, 2), (2, 0), (3, 7), (4, 3), (5, 1), (6, 6), (7, 4)]
- [(0, 2), (1, 5), (2, 7), (3, 0), (4, 3), (5, 6), (6, 4), (7, 1)]
- [(0, 1), (1, 7), (2, 5), (3, 0), (4, 2), (5, 4), (6, 6), (7, 3)]
- [(0, 3), (1, 5), (2, 0), (3, 4), (4, 1), (5, 7), (6, 2), (7, 6)]
- [(0, 1), (1, 5), (2, 0), (3, 6), (4, 3), (5, 7), (6, 2), (7, 4)]
- [(0, 6), (1, 2), (2, 7), (3, 1), (4, 4), (5, 0), (6, 5), (7, 3)]
- [(0, 0), (1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3)]
- [(0, 3), (1, 7), (2, 4), (3, 2), (4, 0), (5, 6), (6, 1), (7, 5)]
- [(0, 3), (1, 1), (2, 6), (3, 2), (4, 5), (5, 7), (6, 0), (7, 4)]
- [(0, 3), (1, 6), (2, 2), (3, 7), (4, 1), (5, 4), (6, 0), (7, 5)]
- [(0, 4), (1, 0), (2, 3), (3, 5), (4, 7), (5, 1), (6, 6), (7, 2)]
- [(0, 4), (1, 0), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3)]
- [(0, 5), (1, 1), (2, 6), (3, 0), (4, 2), (5, 4), (6, 7), (7, 3)]
- [(0, 6), (1, 3), (2, 1), (3, 4), (4, 7), (5, 0), (6, 2), (7, 5)]
- [(0, 4), (1, 1), (2, 3), (3, 6), (4, 2), (5, 7), (6, 5), (7, 0)]
- [(0, 3), (1, 7), (2, 0), (3, 2), (4, 5), (5, 1), (6, 6), (7, 4)]
- [(0, 4), (1, 0), (2, 7), (3, 3), (4, 1), (5, 6), (6, 2), (7, 5)]
- [(0, 3), (1, 1), (2, 6), (3, 4), (4, 0), (5, 7), (6, 5), (7, 2)]
- [(0, 2), (1, 4), (2, 1), (3, 7), (4, 5), (5, 3), (6, 6), (7, 0)]
- [(0, 2), (1, 6), (2, 1), (3, 7), (4, 5), (5, 3), (6, 0), (7, 4)]
- [(0, 1), (1, 4), (2, 6), (3, 3), (4, 0), (5, 7), (6, 5), (7, 2)]
- [(0, 0), (1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4)]
- [(0, 3), (1, 1), (2, 7), (3, 4), (4, 6), (5, 0), (6, 2), (7, 5)]
- [(0, 4), (1, 6), (2, 1), (3, 5), (4, 2), (5, 0), (6, 7), (7, 3)]
- [(0, 3), (1, 0), (2, 4), (3, 7), (4, 5), (5, 2), (6, 6), (7, 1)]
- [(0, 6), (1, 2), (2, 0), (3, 5), (4, 7), (5, 4), (6, 1), (7, 3)]
- [(0, 4), (1, 6), (2, 0), (3, 3), (4, 1), (5, 7), (6, 5), (7, 2)]
- [(0, 0), (1, 6), (2, 4), (3, 7), (4, 1), (5, 3), (6, 5), (7, 2)]
- [(0, 2), (1, 4), (2, 7), (3, 3), (4, 0), (5, 6), (6, 1), (7, 5)]
- [(0, 7), (1, 1), (2, 3), (3, 0), (4, 6), (5, 4), (6, 2), (7, 5)]
- [(0, 7), (1, 3), (2, 0), (3, 2), (4, 5), (5, 1), (6, 6), (7, 4)]
- [(0, 7), (1, 1), (2, 4), (3, 2), (4, 0), (5, 6), (6, 3), (7, 5)]
- [(0, 1), (1, 6), (2, 2), (3, 5), (4, 7), (5, 4), (6, 0), (7, 3)]
- [(0, 4), (1, 6), (2, 1), (3, 5), (4, 2), (5, 0), (6, 3), (7, 7)]
- [(0, 3), (1, 1), (2, 6), (3, 2), (4, 5), (5, 7), (6, 4), (7, 0)]
- [(0, 7), (1, 2), (2, 0), (3, 5), (4, 1), (5, 4), (6, 6), (7, 3)]
-
- Process finished with exit code 0
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。