扣丁学堂Python培训简述如何解决八皇后问题

八皇后问题一度困扰了不少的Python开发工程师们，今天扣丁学堂Python在线学习小编就给大家分享一下Python解决八皇后问题示例，希望对小伙伴们有所帮助。

Python培训

本篇文章简单描述了八皇后问题的原理，并结合实例形式分析Python基于递归算法解决八皇后问题的相关操作技巧，对八皇后问题感兴趣的小伙伴可以仔细阅读，具体如下：

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解。

这是一个典型的回溯算法，我们可以将问题进行分解：

首先，我们要想到某种方法来解决冲突检测问题，即不能令棋子处于能相互吃掉的位置——相邻、左右对角线。

其次，运用回溯的方法，求得问题的解。此处具体为函数的递归调用，当调用到棋盘的最后一行，便跳出，求得解。

最后，将我们的解打印出来。难点在于对递归调用函数的理解。

这仅仅是思路，是我们必须要解决的问题，但并不代表程序的运行流程。

具体代码如下：

#-*- coding:utf-8 -*-
import random
#冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上
def conflict(state, nextX):
 nextY = len(state)
# print(nextY),
 for i in range(nextY):
 #如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放
 if abs(state[i]-nextX) in (0, nextY-i):
#纵坐标减去下一个皇后的横坐标的绝对值 处于 0到下一皇后纵坐标减i则冲突
 return True
 return False
#采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。
def queens(num, state=()):
 #num = 8
# print("%d "%len(state)),
 for pos in range(num):
 if not conflict(state, pos): #如果没有冲突
 #产生当前皇后的位置信息
 if len(state) == num-1:
 yield (pos, ) #生成元组
 #否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
 else:
 for result in queens(num, state+(pos,)):
 yield (pos, ) + result
 #result这个变量代表的是quees返回的元组
#若是最后一行 对于 pos in range(num)调用conflict(state, num) ,
#如果没有冲突,生成元组
#若不是最后一行 对于pos in range(num)调用conflict(state, pos),
#如果没有冲突,state更新,递归调用queens(num, state) state将更新
#为了直观表现棋盘，用X表示每个皇后的位置
def prettyprint(solution):
 def line(pos, length=len(solution)):
 return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
 for pos in solution:
 print line(pos)
if __name__ == "__main__":#来判断是否是在直接运行该.py文件
 prettyprint(random.choice(list(queens(8))))

以上就是小编给大家分享的如何解决八皇后问题，希望对小伙伴们有所帮助，想要了解更多内容的小伙伴可以登录扣丁学堂官网咨询。扣丁学堂是专业的Python培训机构，扣丁学堂不仅有专业的老师和与时俱进的课程体系，还有大量的Python在线视频供学员观看学习，想要学好Python的小伙伴现在就行动吧。