Python解决八皇后问题并输出可视化结果 - CSDN文库

153 浏览量更新于2023-03-03 收藏 62KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

Python解决八皇后问题并输出可视化结果解决八皇后问题并输出可视化结果

八皇后问题:八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848

年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线

上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论

的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题（百度百科）。

最近在学习回溯递归的算法，所以试着用Python实现八皇后的求解问题，刚开始总是走不通，后来发现是走到死节点后，回

溯需要将前一步的操作还原，这是我学习过程中一直不太好理解的一点，这一点理解通后，回溯递归应该就掌握了基本了。

下面附上代码

画棋盘的方法参考了这篇博客，使用的是matplotlib库

https://blog.csdn.net/weixin_45405128/article/details/102510877

import matplotlib.pyplot as plt

import matplotlib

import numpy as np

# ------------------------

#设定中文字符集，解决绘图时中文乱码问题

matplotlib.rcParams['font.sans-serif'] = ['WenQuanYi Micro Hei']

#放置函数

def Queen_set(n):

global num

if n==8:

print("第"+str(num)+"种:",queen_list)

plot_chess(queen_list)

num+=1

return

else:

for i in range(8):

if check(n,i):

queen_list.append(i) #在当前位置放置皇后

Queen_set(n+1) #递归，进入下一层搜索

queen_list.pop() #回溯关键点，清除前一步的错误数据

#检测当前位置是否符合要求

#depth:搜索深度 index:目前的摆放情况

def check(depth,index):

if depth==0:

return True

else:

for i in range(depth):

if queen_list[i] == index: #判断列是否符合

return False

#判断对角线规则是否符合

elif index==queen_list[i]-depth+i or index==queen_list[i]+depth-i:

return False

return True

#绘制棋盘并保存求解结果

def plot_chess(result):

global num

mat=np.zeros((8,8))

for i in range(8):

for j in range(8):

if result[i]==j:

mat[i,j]=1

elif (i+j)%2==0:

mat[i,j]=-1

else:

mat[i,j]=0

my_cmap=matplotlib.colors.LinearSegmentedColormap.from_list('my_camp',['white','black','deeppink'],3)

plt.imshow(mat,cmap=my_cmap)

plt.title("第"+str(num)+"种解法",fontsize=16)

plt.xticks([])

plt.yticks([])

plt.savefig('/home/username/queen8/pic/'+str(num)+'.png') #保存图片的路径,自行修改

queen_list = [] num = 1

Queen_set(0)

将结果制作成gif图

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38665668

粉丝: 4
资源: 941

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈