python 非递归解决n皇后问题的方法
作者:skrrrr__ 时间:2023-07-06 09:38:05
复杂度可能高了点- - 也没太注意
我想了好久 也找了好久 没看到什么能够用python解决n皇后问题而且不调用递归的 因为我不太能理解递归(尤其是到n层时) 智商受限- -
import copy
def check(A,x,y):
B=[]
flag=True
for i in range(len(A)):
for j in range(len(A)):
if A[i][j]==1:
B.append([i,j])
for m in range(len(B)):
p = B[m][0]
q = B[m][1]
if y == q or (x-p)==abs(y-q):
flag=False
return flag
def queen(n):
A=[[0 for __ in range(n)] for _ in range(n)]
answer=[]
for _ in range(n):
stack=[[0,_,A]]
while stack:
judge = 0
obj=stack.pop(-1)
x=obj[0]
y=obj[1]
array=obj[2]
flag=check(array,x,y)
if not flag:
while 1:
if check(array, x, y):
break
else:
if stack:
b=stack.pop(-1)
x=b[0]
y=b[1]
array=b[2]
else:
judge=1
break
if judge==1:
break
array=copy.deepcopy(array)
array[x][y]=1
for m in range(n):
if m!=y and m!=y-1 and m!=y+1 and x+1<n :
stack.append([x+1,m,array])
# print(array)
for j in range(len(array[n-1])):
if array[n-1][j]==1:
answer.append(array)
print(len(answer))
queen(8)
answer中存放的就是最后所有的可行组合
当前解决的是8皇后问题
我的想法是用dfs 在每次搜索时 带上该次搜索需要摆放的位置 x,y,以及待摆放的棋盘 即[x,y,A]
这样不会导致所有的操作都在一个矩阵上进行
来源:https://blog.csdn.net/skrrrr__/article/details/114829636
标签:python,非递归,n皇后
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Django中Forms的使用代码解析
2022-03-20 08:06:56
![](https://img.aspxhome.com/file/2023/9/84079_0s.png)
OpenCV模板匹配matchTemplate的实现
2021-08-09 15:51:51
![](https://img.aspxhome.com/file/2023/3/112423_0s.jpg)
tornado 多进程模式解析
2021-01-20 10:56:44
Vim中查找替换及正则表达式的使用详解
2023-11-06 11:42:44
将图片读入到Dom中,并将其存为xml文件
2008-09-04 11:24:00
使用keras做SQL注入攻击的判断(实例讲解)
2024-01-25 12:40:36
![](https://img.aspxhome.com/file/2023/3/104423_0s.png)
Vue中this.$nextTick()的具体使用
2023-07-02 16:59:30
![](https://img.aspxhome.com/file/2023/4/139874_0s.png)
MySQL两种识别是否有中文字符的方法
2011-01-04 20:11:00
python 实现两个npy档案合并
2022-08-20 13:29:55
详解JS几种变量交换方式以及性能分析对比
2024-04-10 16:13:58
![](https://img.aspxhome.com/file/2023/0/136750_0s.png)
mysql常用命令行操作语句
2024-01-12 23:51:20
django template实现定义临时变量,自定义赋值、自增实例
2021-05-24 09:16:46
利用Python实现获取照片位置信息
2022-12-07 06:58:16
![](https://img.aspxhome.com/file/2023/1/134641_0s.png)
python的exec、eval使用分析
2022-05-26 18:38:25
python random从集合中随机选择元素的方法
2023-07-05 08:29:45
canvas时钟效果
2024-05-05 09:14:22
![](https://img.aspxhome.com/file/2023/7/129577_0s.png)
asp我对后台安全的一些做法
2011-09-01 19:22:09
php实现的单一入口应用程序实例分析
2023-11-22 08:00:26
Go语言中内存管理逃逸分析详解
2024-05-08 10:13:48
MySQL 5.7.14 net start mysql 服务无法启动-“NET HELPMSG 3534” 的奇怪问题
2024-01-12 17:19:38