gpt4 book ai didi

python 非递归解决n皇后问题的方法

转载 作者:qq735679552 更新时间:2022-09-29 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python 非递归解决n皇后问题的方法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

复杂度可能高了点- - 也没太注意 。

我想了好久 也找了好久 没看到什么能够用python解决n皇后问题而且不调用递归的 因为我不太能理解递归(尤其是到n层时) 智商受限- - 。

?
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
49
50
51
52
53
54
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] 这样不会导致所有的操作都在一个矩阵上进行 。

到此这篇关于python 非递归解决n皇后问题的方法的文章就介绍到这了,更多相关python 非递归n皇后内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。

原文链接:https://blog.csdn.net/skrrrr__/article/details/114829636 。

最后此篇关于python 非递归解决n皇后问题的方法的文章就讲到这里了,如果你想了解更多关于python 非递归解决n皇后问题的方法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com