马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 yinda_peng 于 2023-5-24 23:04 编辑
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
def solveNQueens(n):
def DFS(queens, xy_dif, xy_sum):
p = len(queens)
if p == n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([], [], [])
return [[ "."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]#列表推导式创建二维列表
n = int(input("请输入n的值："))
count = 0
for solution in solveNQueens(n):
print('\n'.join(solution))
count += 1
print()#空行分隔
print("总共有{}个解".format(count))
我之前把自己在知乎的一篇有关代数的文章搬过来了，有兴趣的朋友可以看看https://fishc.com.cn/thread-228674-1-1.html
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-5-24 23:01:20
置顶卡
千斤顶
显身卡
楼主
发表于 2023-5-24 23:13:37
