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

Nissa ·

更新时间:2024-09-21

· 918 次阅读

八皇后问题:八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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图
求解结果