Python 解决八皇后问题
2024-08-29 20:34:27
问题介绍
八皇后问题是一个以国际象棋为背景的问题:如何能够在 \(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
最新文章
- QuickFlow UI 控件之 NamedFormAttachment
- 转自pnljs 委托(Func<;int,bool>;)
- C# 微信v3退款
- Linux 下的常用工具
- [深入浅出Windows 10]布局原理
- 妙味5:document.cookie 操作
- sql: table,view,function, procedure created MS_Description in sql server
- 程序员的sql金典
- leetcode 6
- ionic获取事件中的对象
- 《WPF程序设计指南》读书笔记——第6章 Dock与Grid
- PHP+jQuery实现翻板抽奖
- Jquery对select下拉框的操作
- Tornado 网站demo 二
- react native( rn) 中关于navigationOptions中headerRight 获取navigation的问题 rn
- Vue(三十二)SSR服务端渲染Nuxt.js
- Android应用开发中三种常见的图片压缩方法
- Angular2入门:TypeScript的类 - 定义、继承和作用域
- java——线程
- malloc()函数(Linux程序员手册)及函数的正确使用【转】