算法之八皇后问题的解决方法
算法之八皇后问题的解决方法
问题描述： 在国际象棋棋盘上，棋盘是8*8的，皇后可以吃掉其同一行列以及斜线方向的棋子，在这张棋盘上可以有多少种8个皇后的摆放方法，能够让各个皇后都不能吃掉其他皇后。
求解思路：回溯与递归算法 python
1.确定并调试检测函数，检测函数的作用是检查当前加入的新皇后是否符合要求
1 def check(quene_list ,listnum): 2 for i in range(listnum): 3 if abs(quene_list[listnum]-quene_list[i]) == listnum - i or quene_list[listnum] == quene_list[i]: 4 # 当条件成立时说明新加入的皇后会被攻击到 5 return 0 6 return 1
2.递归回溯 判断终止条件是当计算到最后一列时，首先确定第n列加入棋盘不会产生冲突，在第n+1列加入皇后，若不冲突则递归计算下一个。在思想上有点像数学归纳法。
1 def quene(quene_list, listnum, num): 2 global solve_num 3 if listnum == num: 4 solve_num = solve_num + 1 5 print(quene_list) 6 return 1 7 else: 8 for i in range(num): 9 quene_list[listnum] = i 10 if check(quene_list, listnum): 11 quene(quene_list,listnum+1,num)
3.用python实现八皇后问题的完整代码
1 # -*- coding: utf-8 -*- 2 # 八皇后问题的求解，递归回溯问题 3 4 import math 5 6 solve_num = 0 7 8 def check(quene_list ,listnum): 9 for i in range(listnum): 10 if abs(quene_list[listnum]-quene_list[i]) == listnum - i or quene_list[listnum] == quene_list[i]: 11 # 当条件成立时说明新加入的皇后会被攻击到 12 return 0 13 return 1 14 15 def quene(quene_list, listnum, num): 16 global solve_num 17 if listnum == num: 18 solve_num = solve_num + 1 19 print(quene_list) 20 return 1 21 else: 22 for i in range(num): 23 quene_list[listnum] = i 24 if check(quene_list, listnum): 25 quene(quene_list,listnum+1,num) 26 27 if __name__ == "__main__": 28 quene_list = [0, 0, 0, 0, 0, 0, 0, 0,0] 29 num = 9 30 quene(quene_list,0, 8) 31 print(solve_num)
View Code
版权声明：本文为hustyan原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。