Python 解决八皇后问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python 解决八皇后问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1695字，纯文字阅读大概需要3分钟。

内容图文

问题介绍

八皇后问题是一个以国际象棋为背景的问题：如何能够在 \(8\times8\) 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题。

要解决 n 皇后问题，首先在棋盘中放入一个新皇后，且这个位置不会被先前放置的皇后吃掉，将这个新皇后的位置压入堆栈。但是，如果放置新皇后的该行（或该列）的 8 个位置都没有办法放置新皇后（放入任何一个位置，都会被先前放置的旧皇后给吃掉），此时就必须从堆栈中弹出前一个皇后的位置，并在该行（或该列）中重新寻找另一个新的位置来放，再将该位置压入堆栈中，而这种方式就是一种回溯 (Backtracking) 算法的应用。

代码示例

代码来自于 References[2] 。

global queen
global number
EIGHT=8 #定义堆栈的最大容量
queen=[None]*8 #存放8个皇后的行位置

number=0    #计算总共有几组解的总数
#决定皇后存放的位置
#输出所需要的结果
def print_table():
    global number
    x=y=0
    number+=1
    print('')
    print('八皇后问题的第%d组解\t' %number)
    for x in range(EIGHT):
        for y in range(EIGHT):
            if x==queen[y]:
                print('<q>',end='')
            else:
                print('<->',end='')
        print('\t')
    input('\n..按下任意键继续..\n')

#测试在(row,col)上的皇后是否遭受攻击
#若遭受攻击则返回值为1,否则返回0
def attack(row,col):
    global queen
    i=0
    atk=0
    offset_row=offset_col=0
    while (atk!=1)and i<col:
        offset_col=abs(i-col)
        offset_row=abs(queen[i]-row)
        #判断两皇后是否在同一行或在同一对角线上
        if queen[i]==row or offset_row==offset_col:
            atk=1
        i=i+1
    return atk

def decide_position(value):
    global queen
    i=0
    while i<EIGHT:
        if attack(i,value)!=1:
            queen[value]=i
            if value==7:
                print_table()
            else:
                decide_position(value+1)
        i=i+1

#主程序
decide_position(0)

运行结果如下所示：

【References】

[1] 百度百科：八皇后问题

[2] 吴灿铭. 图解数据结构 : 使用Python[M]. 北京 : 清华大学出版社, 2018

内容总结

以上是互联网集市为您收集整理的Python 解决八皇后问题全部内容，希望文章能够帮你解决Python 解决八皇后问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---