python 使用递归回溯完美解决八皇后的问题
82 浏览量
2020-09-17
20:00:25
上传
评论
收藏 122KB PDF 举报
python 使用递归回溯完美解决八皇后的问题使用递归回溯完美解决八皇后的问题
今天小编就为大家分享一篇python 使用递归回溯完美解决八皇后的问题，具有很好的参考价值，希望对大家有
所帮助。一起跟随小编过来看看吧
八皇后问题描述：在一个8✖️8的棋盘上，任意摆放8个棋子，要求任意两个棋子不能在同一行，同一列，同一斜线上，问有多
少种解法。
规则分析：规则分析：
任意两个棋子不能在同一行比较好办，设置一个队列，队列里的每个元素代表一行，就能达到要求
任意两个棋子不能在同一列也比较好处理，设置的队列里每个元素的数值代表着每行棋子的列号，比如（0，7，3），表示第
一行的棋子放在第一列，第二行的棋子放在第8列，第3行的棋子放在第4列（从0开始计算列号）
任意两个棋子不能在同一斜线上，可以把整个棋盘当作是一个XOY平面，原点在棋盘的左上角，斜线的斜率为1或者-1，X为
列号，Y为行号，推出斜线的表达式为Y=X+n或者Y=-X+n（n为常数，斜线确定下来之后n就确定了），进而可以推导出Y-
X=n或者Y+X=n。也就是说在同一斜线上的两个棋子行号与列号之和或者之差相等。X1+Y1=X2+Y2或者X1-Y1=X2-Y2。再进
行变换能够得到X1-X2=Y2-Y1或者X1-X2=Y1-Y2，也就是说|X1-Y1|=Y1-Y2。即判断两个棋子是否在同一斜线上，只要判断
出两个棋子的列号之差是否等于两个棋子的行号之差的绝对值就行了。
如下图：
将上述文字分析转化为代码，就可以判断棋子之间是否符合规则了（abs(num)表示取num的绝对值）
def is_rule(queen_tup, new_queen):
"""
:param queen_tup: 棋子队列，用于保存已经放置好的棋子，数值代表相应棋子列号
:param new_queen: 被检测棋子，数值代表列号
:return: True表示符合规则，False表示不符合规则
"""
num = len(queen_tup)
for index, queen in enumerate(queen_tup):
if new_queen == queen: # 判断列号是否相等
return False
if abs(new_queen-queen) == num-index: # 判断列号之差绝对值是否与行号之差相等
return False
return True
资源评论
