八皇后问题 早在1848年就已提出，可谓是历史悠久，经久不衰，曾一度难倒了高斯之流的顶级数学大师，但是，在计算机发明之后，这道曾经的世界难题被以无数种方式轻松解决，这也不由得令我们广大程序猿们大为振奋。
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
The Sultan's Successors(Eight Queens)拓展要求:努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。
8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。
输入格式
输入一个数字 k(k≤20)，代表棋盘的数量。
接下来有 k 个棋盘，每个棋盘有 64 个数字，分成 8 行 8 列出入，具体可见样例，每一个数字均小于 100。
输出格式每一个棋盘对应输出最大的数值， 一共输出 k 行。
Input :1
Output :
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64260
同时输出8*8的矩阵以表示八皇后分布位置,用 'X' 表示皇后， ' . ' 表示未放置棋子。
且可加强为 n问题皇后（ n*n 的棋盘数放置n个皇后，规则同上）
鉴于CSDN上多为C++语言，小编特撰此文以补python之空缺。
算法思路：1. 从棋盘的第一行，第一个位置开始，依次判断当前位置是否能够放置皇后， 判断的依据为：同该行之前的所有行中皇后的所在位置进行比较，如果在同一列， 或者在同一条对角线上，都不符合要求， 继续试探后续的位置。
2.每一行只有可能放置一个皇后，当前行放置皇后之后应直接跳转至下一行深入搜索。同样因为这个原因，列表中只需记录皇后横坐标即可，配合列表索引即可得到相应的完整坐标 。
3. 若当前行所有位置均已试探完毕，则回溯到前一行，改变皇后的位置，继续试探。
4. 如果试探到最后一行，所有皇后摆放完毕，则记录下当前皇后坐标及得分。最后一定要记得将棋盘初始化，避免影响下一次摆放。
本篇代码主要由三部分组成：Queens 函数，place 函数，主程序（main）。
Queens函数通过DFS，即深度优先搜索找出所有可能的放置结果，以及最高得分。
place函数则用于输出得分最高时的摆放方式。
主程序负责重复实现和相关数据的初始化。
源代码：下有史上最全注释，没有之一，绝对自信。保证大家绝对能看懂，再看不懂私聊。（QQ：3524575922）
# -*- mode:python ; coding=UTF-8 -*-
# @Date:2022.2.13 20:50
# @Author:Forever_Sirius
from random import randint
def Queens(n,y=0):
global sum #声明sum为全局变量,以避免不同作用域同名变量引起的纠纷
if y==n :
resn.append(sum);res.append(temp[:])
'''
切记,不可直接追加temp,
否则列表元素将始终为同一个列表,即会随temp的改变而改变,
应当用切片或copy函数创建新列表
'''
return #触碰递归边界,回溯
for x in range(n): #依次试探当前行每一个位置
if not (cols[x] or left[y+x] or right[y-x]):
#若该位置可放置,则放置皇后并记录得分
temp[y]=x;sum+=l[y][x]
'''
由于一行只可能有一个皇后,故记下皇后横坐标即可,
纵坐标即为横坐标索引
'''
cols[x]=1;left[y+x]=1;right[y-x]=1
'''
标记该列,该左右对角线为 '已放置'
左右对角线定位方法:
根据一点一方向确定一直线的原理,
利用各平行直线纵截距的唯一性
通过 y+x 或 y-x 来定位对角线
'''
Queens(n,y+1) #进入下一行试探
temp[y]=0;sum-=l[y][x]
cols[x]=0;left[y+x]=0;right[y-x]=0
'''
回溯后当解除标记,扣除得分,
恢复初始状态以免影响下一轮试探
'''
def place():
for i in range(len(res)):
if resn[i]==maxn: #遍历resn,若得分为最高,则打印相应摆放方式
for y in range(len(res[i])):
x=res[i][y] #配合纵坐标获取横坐标
for j in range(n):
'''
用 'X' 表示皇后,
' . ' 表示未放置棋子.
'''
if j==x:
print('X',end=' ')
else:
print('.',end=' ')
print() #一行打印完毕后换行
print() #由于可能有多种情况,每种情况打印完毕后空一行
if __name__=='__main__' :
k=int(input('请输入棋盘数量:'))
n=8
temp=[0]*n;sum=0
res=[];resn=[]
cols=[0]*n;left=[0]*(2*n+1);right=[0]*(2*n+1)
'''
初始化相关数据,
各列表回溯时会自动归零,不必重新赋值
'''
while k :
'''
n=int(input('请输入皇后数量:'))
temp=[0]*n;sum=0
res=[];resn=[]
cols=[0]*n;left=[0]*(2*n+1);right=[0]*(2*n+1)
'''
#取消以上注释后可加强为n皇后问题
l=[[randint(1,99) for i in range(n)] for j in range(n)]
#解析列表以初始化二维列表
Queens(n)
#调用递归函数,DFS试探出所有解
maxn=max(resn)
print('n最大得分为:',maxn)
#找出并输出最高得分
print('n摆放方式如下:')
place()
#调用函数打印得分最高的摆放方式
k-=1
#余下的棋盘数减1
input('n请按任意键退出') #界面悬停,无特定意义
算法要点：
1.左右对角线的定位方法
根据一点一方向确定一直线的原理,
利用各平行直线纵截距的唯一性
通过 y+x 或 y-x 来定位对角线
#上略
for x in range(n): #依次试探当前行每一个位置
if not (cols[x]or left[y+x]or right[y-x]):
#若该位置可放置,则放置皇后并记录得分
temp[y]=x;sum+=l[y][x]
cols[x]=1;left[y+x]=1;right[y-x]=1
'''
标记该列,该左右对角线为 '已放置'
左右对角线定位方法:
根据一点一方向确定一直线的原理,
利用各平行直线纵截距的唯一性
通过y+x 或 y-x 来定位对角线
'''
#以下代码略
2.回溯时恢复改变量
回溯后当解除标记,扣除得分,
恢复初始状态以免影响下一轮试探
#上略
if not (cols[x]or left[y+x]or right[y-x]):
#若该位置可放置,则放置皇后并记录得分
temp[y]=x;sum+=l[y][x]
cols[x]=1;left[y+x]=1;right[y-x]=1
Queens(n,y+1) #进入下一行试探
temp[y]=0;sum-=l[y][x]
cols[x]=0;left[y+x]=0;right[y-x]=0
'''
回溯后当解除标记,扣除得分,
恢复初始状态以免影响下一轮试探
'''
#下略
3. 皇后坐标的记录以及图像的绘制
根据同一行只能有一个皇后，故可通过横坐标及其索引定位皇后，取用时配合索引获取完整坐标。纵坐标即为横坐标索引。
#上略
if not (cols[x]or left[y+x]or right[y-x]):
#若该位置可放置,则放置皇后并记录得分
temp[y]=x;sum+=l[y][x]
'''
由于一行只可能有一个皇后,故记下皇后横坐标即可,
纵坐标即为横坐标索引
'''
#以下略去部分代码
if resn[i]==maxn:
for y in range(len(res[i])):
x=res[i][y] #配合纵坐标获取横坐标
for j in range(n):
if j==x:
print('X',end=' ')
else:
print('.',end=' ')
print()
print()
#下略
4.temp变量的添加方式
若直接追加temp，将导致res中所有元素均指向同一内存地址，即temp的内存地址，可谓牵一发而动全身，最终res中所有元素将会全部重置为 [0]*n 。
为了避免这种情况出现，我们应该使用全切片（temp[:]）或者 temp.copy() 来创建内容相同的新列表，使其各指向不同内存地址。
本部分内容若有疑问，详情请访问鄙人相关博文《探秘python内存机制之指针》https://blog.csdn.net/Forever_Sirius/article/details/122921817
def Queens(n,y=0):
global sum
if y==n :
resn.append(sum);res.append(temp[:])
'''
切记,不可直接追加temp,
否则列表元素将始终为同一个列表,即会随temp的改变而改变,
应当用切片或copy函数创建新列表
'''
return #触碰递归边界,回溯
#下略
5.全局变量sum的声明
为了以避免不同作用域同名变量引起的纠纷，最好声明sum为全局变量。
def Queens(n,y=0):
global sum #声明sum为全局变量,以避免不同作用域同名变量引起的纠纷
#下略
为了方便起见，本代码中用生成随机数来代替矩阵输入。
测试效果： 普通版（8皇后）： 加强版（n皇后）：谨以此篇献给广大有需求的读者们。感谢各位读者的支持，希望能对你们有所帮助，这将是我最大的荣耀与动力。若有错误，欢迎大佬指出，小编当及时更正，有幸承蒙醍醐灌顶之教，鄙人不胜感激之至。
若喜欢，请点赞or收藏，谢谢！
更多博文欢迎访问我的CSDN主页https://blog.csdn.net/Forever_Sirius?type=blog
