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

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

我想了好久 也找了好久 没看到什么能够用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]
这样不会导致所有的操作都在一个矩阵上进行

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

赞 (0)

相关推荐

  • Python基于生成器迭代实现的八皇后问题示例

    本文实例讲述了Python基于生成器迭代实现的八皇后问题.分享给大家供大家参考,具体如下: 问题:有一个棋盘和8个要放到上面的皇后,唯一的要求是皇后之间不能形成威胁.也就是说,必须把他们防止成每个皇后都不能吃掉其他皇后的状态. # -*- coding: utf-8 -*- #python 2.7.13 __metaclass__ = type def confict(state, nextX): nextY = len(state) for i in range(nextY): if abs(

  • python八皇后问题的解决方法

    本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上.竖线上.斜线上.一般我们都讨论8皇后,但是只要N > 4,都会存在解的. 分析: 方法1:根据定义来处理,即每往棋盘中放置皇后的时候,都要判断哪些位置可以放新加入的皇后,而哪些地方如果放置皇后的话,会造成冲突.我下面写的这个代码就是基于此. 方法2.我看了下别人的优化,主要是采用位运算来实现计算复杂度降低的,我没有用Py

  • python 使用递归回溯完美解决八皇后的问题

    八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法. 规则分析: 任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表一行,就能达到要求 任意两个棋子不能在同一列也比较好处理,设置的队列里每个元素的数值代表着每行棋子的列号,比如(0,7,3),表示第一行的棋子放在第一列,第二行的棋子放在第8列,第3行的棋子放在第4列(从0开始计算列号) 任意两个棋子不能在同一斜线上,可以把整个棋盘当作是一个XOY平面,原点在

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • Python解决八皇后问题示例

    Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • Python实现八皇后问题示例代码

    八皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子.皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子.在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式. 首先,我们想到递归和非递归两类算法来解决这个问题.首先说说递归地算法. 很自然的,我们可以基于行来做判断标准.八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列.当然八个列下

  • Python八皇后问题解答过程详解

    最近看Python看得都不用tab键了,哈哈.今天看了一个经典问题--八皇后问题,说实话,以前学C.C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上又碰到,只是学会了思想,应该是学回溯法的时候碰到的.八皇后问题是说要在一个棋盘上放置8个皇后,但是不能发生战争,皇后们都小心眼,都爱争风吃醋,如果有人和自己在一条线上(水平.垂直.对角线)就会引发撕13大战,所以我们就是要妥当的安排8位娘娘,以保后宫太平. 言归正传,首先,我们得想好解决方案怎么表示,这种事首先想到列表,当然规模小的话用元

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

    复杂度可能高了点- - 也没太注意 我想了好久 也找了好久 没看到什么能够用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

  • python非递归全排列实现方法

    刚刚开始学习python,当前看到了函数这一节.结合数组操作,写了个非递归的全排列生成.原理是插入法,也就是在一个有n个元素的已有排列中,后加入的元素,依次在前,中,后的每一个位置插入,生成n+1个新的全排列.因为Python切割数组或者字符串,以及合并比较方便,所以,程序会节省很多代码. def getArrayInsertCharToStr(STR,CHAR): arr =[] s_len = len(STR) index =0 while index <= s_len: #分割字符串 ar

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • C语言基于回溯算法解决八皇后问题的方法

    C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • Java非递归实现删除任意目录的方法

    Java非递归实现删除任意目录的方法

    最近在学C#的文件系统, 发现C#的文件系统貌似比java的东西少一点, 居然连删除目录都直接做好封装了, 想到学java的时候还要自己写递归删除, 好像没写过非递归的,就在网上查了下, 关于非递归删除目录代码没几个, 我就写了一个,递归网上一大堆, 就不粘上来了. 下面是代码非递归的方法: package demo1; import java.io.File; import java.util.ArrayList; public class Demo1 { /** * 不使用递归删除目录 *

  • python使用递归解决全排列数字示例

    第一种方法:递归 复制代码 代码如下: def perms(elements):    if len(elements) <=1:        yield elements    else:        for perm in perms(elements[1:]):            for i in range(len(elements)):                yield perm[:i] + elements[0:1] + perm[i:] for item in li

  • python基于递归解决背包问题详解

    递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单.一个很复杂的问题,几行代码就能搞定. 最简单的递归问题:现有重量为weight的包,有若干重量分别为W1,W2.....Wn的物品,试问能否从物品中选出若干件而且重量刚好为weight? weight具体是怎么构成的,有下面两种情况(假设挑选到Wn时,刚好够weight): 1. 从Wn-1开始就已经够weight,那weight=W1+W2+......+Wn=W1+W2+......+Wn-1. 2.加上Wn后刚好够weig

  • 分析python动态规划的递归、非递归实现

    概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar

随机推荐