首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

皇后问题Python实现

皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子。...在一个棋盘上如果要放皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式。 首先,我们想到递归和非递归两类算法来解决这个问题。...皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列。当然个列下标也都不能有相同,除此之外还要保证斜线上不能有重叠的皇后。   ...自然我们就可以想到,能不能将board转化为一个一维数组,下标本身就代表了board的某一行,然后值是指这一行皇后放在第几列。   ...■ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ ■ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ 所有结果 上面的程序多只是生成了一个结果,而实际上皇后可以有很多种可能的布局

1.2K20

皇后

概念 皇后问题,是一个古老而著名的问题,是回溯算法的经典案例。...该问题是国际西洋棋,棋手马克思·贝瑟尔1848念提出:在8*8格的国际象棋上摆放皇后,使其不能互相攻击,即:任意两个皇后不能处于同一行、同一列或同一斜线上,不能互相攻击;问有多少种摆法。...皇后问题思路分析 (1)第一个皇后先放第一行第一列 (2)第二个皇后放在第二行第一列,然后判断是否符合规则,不符合则继续放在第二列、第三列、一次把所有咧都放完,找到一个合适的位置。...(3)继续第三个皇后,还是第一列、第二列......直到第皇后也能放在一个不冲突的位置,算是找到了正解。...举个例子,arr[8]={0,4,7,5,2,6,1,3}对应arr下标表示第几行,即第几个皇后,arr[i]=val,val表示第i+1个皇后,放在第i+1行的第val+1列。

45130
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    皇后问题

    1.问题描述 皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。...2.解法一 2.1解题思路 首先我们分析一下问题的解,我们每取出一个皇后,放入一行,共有种不同的放法,然后再放第二个皇后,同样如果不考虑规则,还是有种放法。于是我们可以用一个叉树来描述这个过程。...从根节点开始,树每增加一层,便是多放一个皇后,直到第8层(根节点为0层),最后得到一个完全叉树。 紧接着我们开始用深度优先遍历这个叉树,在遍历的过程,进行相应的条件的判断。...由于皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8],数组第i个数字表示位于第i行的皇后的列号。...先把ColumnIndex的个数字分别用0-7初始化,接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组的数字,因此任意两个皇后肯定不同列。

    49940

    皇后问题

    然而,在有些应用程序,你不能马上得到答案。你必须尝试多次,且在每个递归层级中都如此。打个现实生活的比方吧,假设你要去参加一个很重要的会议。...---- 3.状态表示 可简单的使用元组(或列表)来表示可能的解(或其一部分),其中每个元素表示相应行皇后所在的位置(即列)。...5.基线条件 皇后问题解决起来有点棘手,但通过使用生成器并不太难。然而,如果你不熟悉递归,就很难自己想出这里的解决方案。另外,这个解决方案的效率不是特别高,因此皇后非常多时,其速度可能有点慢。...处理好基线条件后,可在递归条件假设来自更低层级(编号更大的皇后)的结果都是正确的。因此,只需在函数queens的前述实现给if语句添加一个else子句。 你希望递归调用返回什么样的结果呢?...另外,你还记得(pos,)的逗号必不可少(不能仅用圆括号将pos括起),这样得到的才是元组。 生成器queens提供了所有的解(即所有的合法皇后的位置组合)。 ?

    62110

    皇后问题

    问题描述: 皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。...问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行;若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可以放置皇后的位置...求所有解时,每找到一组解,就清除这一组解最后一个皇后的位置信息,开始探查该行另外一个可以放置皇后的位置,依次回溯求解。...public class ThreeQueen { /** * @param args */ private int[] a=new int[8]; //存储弟i行皇后位于第...=new ThreeQueen(); queen.Search(0); } public void Search(int m){ if(m>=8){ System.out.println(“皇后的一组解为

    29620

    皇后问题

    皇后问题就是在8×8的国际象棋棋盘上放置8个皇后,保证任意2个皇后都无法互相攻击的问题。...在第一行的可行位置放置皇后 在第二行的可行位置放置皇后 以此类推,在前i行放好i个皇后且保证他们不会互相攻击后,在第i+1行寻找皇后摆放的位置。...如果不存在满足上述条件的格子,则返回第i行继续寻找下一个不会被攻击的格子,如果不存在该格子,则继续返回第i-1行 为了记录格子[i,j]是否会被其他皇后攻击,我们需要以下数组: 变量 对应的状态 row...表明第x列受到攻击 dpos[2N-1] 当dpos[x]为true时,则满足x=i+j的格子受到攻击 dneg[2N-1] 当dneg[x]为true时,则满足x=i-j+N-1的格子受到攻击 在上表,...对于特定的格子而言,只要其满足上面四个bool数组均为false,则可以放置皇后

    36310

    皇后问题(python 生成器)

    问题: 在8×8格的国际象棋上摆放皇后,使其不能互相***,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。大致是下面这种样式: ?...也或是说 :皇后a. 列表值 - 皇后b.列表值 = 0 斜行问题: 斜行有两个方面考虑,一种是正斜45度,一种是反斜45度。 相当于汉字的撇捺。但不管那种情况。...如果两个皇后是同斜行,必然是这样: | 皇后a.行值 - 皇后b.行值  | == | 皇后a.列值 - 皇后b....列值  | 绝对值【皇后a.索引-皇后b.索引 】= 绝对值 【皇后a.列表值 - 皇后b.列表值。】 。如下图所示: 设计处理模型: 第一步:皇后摆放顺序 。...当摆放第N+1个时,整个棋盘状态: next = N+1 已摆放的位置放在列表 status : len ( status ) == N 。

    1.2K20

    应用Python递归求解“皇后”问题

    问题描述:如何能够在 8×8 的国际象棋棋盘上放置皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。...问题拓展:皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。 ?...皇后问题的一个解(网图侵删) 求解皇后问题,实际上,因为棋盘和皇后的维度不大,倘若采用暴力计算的方式其实也是可行的:因为皇后分布在8×8的棋盘上,那么从排列组合的角度上其实就是64个棋位中选择8...如果稍加筛选,那么其实皇后必定是每行1个且每列也是1个,这样对于皇后的分布位置实际上就是8!×8!...皇后递归求解流程(拙图) 按此思路,利用python实现,求得最终皇后的方案数有92种。

    1K20

    递归之皇后

    前言:   对于接触过编程的朋友来说,最开始了解的算法莫过于贪心或者递归;而提到递归,除了本博文前面介绍的汉诺塔问题以外,还有一个比较有趣的问题——皇后问题。...问题介绍: 皇后问题指如何能够在 8×8 的国际象棋棋盘上放置皇后,使得任何一个皇后都无法直接吃掉其他的皇后?即任两个皇后都不能处于同一条横行、纵行或斜线上。 2....) Step2 递归跳出边界 由于递归过程,每一种符合的方案都必须遍历到最后一行,因此判断边界为”i==8” Step3 放置皇后的向下递归规则 根据定义,“任两个皇后都不能处于同一条横行、纵行或斜线上...代码实现 3.1列出满足皇后问题的所有方案 1 #include 2 #include 3 #include 4 #define N 8...y || fabs(x-i)==fabs(y-q[i])){ 32 return 0; 33 } 34 return 1; 35 } 3.3结果展示: 结语: 关于皇后问题

    18410

    皇后问题-Java

    皇后问题 皇后问题(英文:Eight queens),是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。...问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。...皇后之间需满足: 不在同一行上 不在同一列上 不在同一斜线上 代码 /** * @BelongsProject: * @BelongsPackage: * @Author: tangshi...static int checkSize = 4; /** * 棋盘(一维数组:下标0开始) * 注释:数组下标表示行 值表示列 * 示例:check[4]=3 ->皇后在第.../** * 解法个数 */ private static int sum = 0; static { //生成棋盘,默认值-1表示这行没皇后

    39240

    皇后算法解析

    这里分析一波皇后算法来加深一下理解。 皇后算法描述如下:在8×8格的国际象棋上摆放皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法!...Queen(); queen.eightQueen(0); System.out.println("总共有 " +queen.count+ " 摆放方法"); } 所以结合皇后的实现来看看到底什么是回溯算法...但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法 比如皇后算法来说,我们根据约束条件判断某一列的某一行是否可以放置皇后,如果不可以就继续判断当前列的下一行是否可以放置皇后....如果可以放置皇后,就继续探寻下一列可以放置皇后的那个位置。...得到一个新的解之后继续循环数组的下一个数字,继续执行1,2,3步骤即可。

    73520

    python基础: 遍历与皇后问题浅析

    遍历思想与皇后问题       作为对《python基础教程》关于皇后一节的补充说明,本文旨在使人从直觉上理解皇后及其相关问题更进一步。       ...如图,在树的遍历,每一个从根节点到达叶子的路径,就是一个解。 用python解决皇后 步骤: 1. 判断皇后冲突 2. 递归得到结果 3....第二个参数是之前皇后的位置。 首先代码分为两部分,即if 的内容 和 else 的内容。 如果当前选择是最后一步, 遍历这一步能做出的所有选择,挑选出那些符合我们定义的选择。...看”else”第一个”for”语句,没错,还是遍历当前行的所有位置,(因为第一行放皇后,第二行放皇后,第三行放皇后。。。,恰好到不是最后一行的当前行)。...用yield而不用return的目的是我们想得到皇后的所有位置的情况。

    1.4K10

    【搜索】皇后「建议收藏」

    总的意思就是说在一个n*n的棋盘上放n个皇后,要求它们互不攻击,求解有多少种情况,并输出前三种。   ...如图,比方说现在在第二行第二列的位置上放了一个皇后,那么有哪些点永远不能放棋子呢?...如图,所有红色的格子(包括这个皇后所在的格子)都不能放置皇后了,乍一看,也看不出来什么规律,别着急,把整个图都以二维数组下标的形式标上序号就一目了然了。   ...按照国际象棋的规则,皇后所能控制的是它所在的行,列,左上到右下的对角线,右上到左下的对角线。...-1=2-2=3-3=4-4,(不一定非等于零,随着这个皇后位置的改变,差值是会改变的),所以和上文一样,我们定义一个数组duijiaoxian2,如果要判断(i,j)是否能摆放皇后,只需判断duijiaoxian2

    25920

    回溯法:皇后问题

    皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。...皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。...,从第一行确定第一个皇后位置,然后再在第二行搜索第二个 皇后位置……没前进一步检查是否满足约束条件,不满足的时候回溯到上一个皇后位置,尝试该行的其他列是否满足条件,直到找到问题的解。...C++参考代码: #include using namespace std; const int N = 8;//皇后的个数 int positon[N];//存放皇后的位置...基本思想: 在包含问题的所有解的解空间树,按照深度优先搜索的策略,从根结点出发深度探索解空间树。

    69620
    领券