文档章节

8皇后问题

沉默的懒猫
 沉默的懒猫
发布于 2017/04/07 14:17
字数 1379
阅读 9
收藏 0
点赞 0
评论 0

 首先,可归纳问题的条件为,8皇后之间需满足:

             1.不在同一行上

             2.不在同一列上

             3.不在同一斜线上

             4.不在同一反斜线上

 

     这为我们提供一种遍历的思路,我们可以逐行或者逐列来进行可行摆放方案的遍历,每一行(或列)遍历出一个符合条件的位置,接着就到下一行或列遍历下一个棋子的合适位置,这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行(或列)。接下来,我们只要判断当前位置是否还符合其他条件,如果符合,就遍历下一行(或列)所有位置,看看是否继续有符合条件的位置,以此类推,如果某一个行(或列)的所有位置都不合适,就返回上一行(或列)继续该行(或列)的其他位置遍历,当我们顺利遍历到最后一行(或列),且有符合条件的位置时,就是一个可行的8皇后摆放方案,累加一次八皇后可行方案的个数,然后继续遍历该行其他位置是否有合适的,如果没有,则返回上一行,遍历该行其他位置,依此下去。这样一个过程下来,我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程,同时也是经典的递归思路。

     

      接下来,我们以逐列遍历,具体到代码,进一步说明。首先,从第一列开始找第一颗棋子的合适位置,我们知道,此时第一列的任何一个位置都是合适的,当棋子找到第一个合适的位置后,就开始到下一列考虑下一个合适的位置,此时,第二列的第一行及第二行显然就不能放第二颗棋子了,因为其与第一个棋子一个同在一行,一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置,以此类推,第三列的第5行又会是一个合适位置,这个过程中,我们注意到,每一列的合适位置都是受到前面几列的位置所影响,归纳如下:

       

      假设前面1列的棋子放在第3行,那当前列不能放的位置就一定是3行,2行,4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上,不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数,数组下标从0开始,其中数组下标表示列数,数组的元素值表示该列棋子所在行数,当前列为N(N>=0,N<8),即cols[N-1]=3,则有:

                          

                      cols[N] != cols[N-1](=3,表示不在同一行)

                     

                      cols[N] != cols[N-1]-1(=3-1=2,表示不在同一斜线上)

                     

                      cols[N]!=cols[N-1]+1(=3+1,表示不在同一反斜线上)

 

      这里我们注意到,如果N-2列存在的话,那么我们还要考虑当前列N不与N-2列的棋子同行,同斜线,同反斜线。把当前列N的前面的某一列设为m,则m的所有取值为{m>=0,m<N}的集合,故又可在上面式子的基础,归纳为如下:

                   

                    cols[N] != cols[m](与第m列的棋子不在同一行)

                   

                    cols[N] != cols­­[m] -(N-m)(>=0 ,与第m列的棋子不在同一斜线上)

                   

                    cols[N] != cols­­[m] + (N-m)  (<=8-1,与第m列的棋子不在同一反斜线上)          

 

           具体到代码,很显然,取m的所有值只需要一句循环,同时我们为每一列定义一个长度为8的布尔数组row[],下标同样是从0开始,我们规定当row[i]=true时,表示该列第i行不能放棋子。这样我们就能写成下列程序段了:

public class Queen8 {  
    public static int num = 0; //累计方案总数  
    public static final int MAXQUEEN = 8;//皇后个数,同时也是棋盘行列总数  
    public static int[] cols = new int[MAXQUEEN]; //定义cols数组,表示8列棋子摆放情况  
    public Queen8() {  
       //核心函数  
      getArrangement(0);  
      System.out.println(MAXQUEEN+"皇后问题有"+num+"种摆放方法。");  
    }  
      
    public void  getArrangement(int n){  
     //遍历该列所有不合法的行,并用rows数组记录,不合法即rows[i]=true  
     boolean[] rows = new boolean[MAXQUEEN];  
     for(int i=0;i<n;i++){  
       rows[cols[i]]=true;  
        int d = n-i;  
        if(cols[i]-d >= 0)rows[cols[i]-d]=true;  
        if(cols[i]+d <= MAXQUEEN-1)rows[cols[i]+d]=true;   
        
     }  
     for(int i=0;i<MAXQUEEN;i++){  
       //判断该行是否合法    
       if(rows[i])continue;  
       //设置当前列合法棋子所在行数  
      cols[n] = i;  
       //当前列不为最后一列时  
       if(n<MAXQUEEN-1){  
        getArrangement(n+1);  
      }else{  
  
       //累计方案个数  
        num++;  
        //打印棋盘信息  
        printChessBoard();  
      }   
       
        
     }  
       
    }  
    public void printChessBoard(){  
         
      System.out.println("第"+num+"种走法 ");  
        
      for(int i=0;i<MAXQUEEN;i++){  
       for(int j=0;j<MAXQUEEN;j++){  
          if(i==cols[j]){  
           System.out.print("0 ");  
          }else  
            System.out.print("+ ");  
        }  
        System.out.println("");  
      }  
       
   }  
    public static void main(String args[]){  
     Queen8 queen = new Queen8();  
   }  
     
} 

 

本文转载自:http://blog.csdn.net/zhong317/article/details/4586131

共有 人打赏支持
沉默的懒猫
粉丝 7
博文 90
码字总数 32568
作品 0
海淀
程序员
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

silenceyawen ⋅ 03/04 ⋅ 0

迭代回溯 ---8皇后

八皇后问题 就是在8*8格子上放8个皇后 皇后是可以横行竖行斜行行走 他们之间不能存在可以被吃的关系 算法 迭代回溯法 思路是这样 红色框代表put 函数里的if没有通过 就不再有进一步迭代(子树...

Ink_cherry ⋅ 2017/05/16 ⋅ 0

剑指Offer(java版)-8皇后问题

题目:在8*8的国际象棋上摆放8个皇后,使其不能相互攻击,及任意两个皇后不得处于同一行,同一列或者同意对角线上,请问总共有多少种符合条件的摆法。 思路一: 由于八个皇后的任意两个不能处...

一贱书生 ⋅ 2016/07/28 ⋅ 0

hdu 2553 n皇后问题

N皇后问题Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21779 Accepted Submission(s): 9744 Problem Description 在N*N的方格......

singular__point ⋅ 2017/03/08 ⋅ 0

N皇后问题摆法算法描述

题目说明: 在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。 题目要求: (1)依次输出各种成功的放置方法。 (2)最好能画出棋盘的图形形式,并动态的演示试探...

邪恶的小Y ⋅ 2011/08/24 ⋅ 0

八皇后问题的python实现,附带输出图解

利用python实现八皇后问题,输出图解。 bahuanghou.py #!/usr/local/bin/python3.5 -u def checkAvaliable(occupiedPoints, point): for i in range(len(occupiedPoints)): if occupiedPoint......

李艳青1987 ⋅ 2016/11/17 ⋅ 0

n皇后问题算法

//* //n皇后问题经典算法 //作者:不详 //备注:此代码为大学时间整理的代码,出处不详。对原文作者说声抱歉! //* #include<iostream> #include"time.h" using namespace std; bool PlaceQue...

viwii ⋅ 2011/06/22 ⋅ 0

练习N皇后问题,老是报错

package test.com; public class Queen { /** * @param args * @author *@since 1.0 *@version 1.0 */ private final int size;//棋盘的大小,也表示皇后的数目 private int[] location;//皇......

撸大师 ⋅ 2013/02/06 ⋅ 0

回溯法/深度优先遍历的简单优化技巧

深度优先遍历配合回溯,是解决很多问题的好方法,比如八皇后问题。 皇后的排布规则:n个皇后放在n*n的矩阵里,要求一列只有一个,一行只有一个,任一斜线上只有一个(/和)。 通常,我们会把...

刘地 ⋅ 2012/11/17 ⋅ 0

DFS算法

DFS算法 三个经典例子 1 排列数 问题: 生成1~n的排列 思路: 一颗N层的树 每层节点为n^n个 在生成结果数组前把重复的去掉 DFS出口: 遍历到排列结果数组长度 DFS实现: 尝试安排数字给结果数组 ...

hakase ⋅ 2016/10/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 13分钟前 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 29分钟前 ⋅ 0

eclipse酷炫大法之设置主题、皮肤

eclipse酷炫大法 目前两款不错的eclipse 1.系统设置 Window->Preferences->General->Appearance 2.Eclipse Marketplace下载【推荐】 Help->Eclipse Marketplace->搜索‘theme’进行安装 比如......

anlve ⋅ 37分钟前 ⋅ 0

vim编辑模式、vim命令模式、vim实践

vim编辑模式 编辑模式用来输入或修改文本内容,编辑模式除了Esc外其他键几乎都是输入 如何进入编辑模式 一般模式输入以下按键,均可进入编辑模式,左下角提示 insert(中文为插入) 字样 i ...

蛋黄Yolks ⋅ 42分钟前 ⋅ 0

大数据入门基础:SSH介绍

什么是ssh 简单说,SSH是一种网络协议,用于计算机之间的加密登录。 如果一个用户从本地计算机,使用SSH协议登录另一台远程计算机,我们就可以认为,这种登录是安全的,即使被中途截获,密码...

董黎明 ⋅ 今天 ⋅ 0

web3j教程

web3j是一个轻量级、高度模块化、响应式、类型安全的Java和Android类库提供丰富API,用于处理以太坊智能合约及与以太坊网络上的客户端(节点)进行集成。 汇智网最新发布的web3j教程,详细讲解...

汇智网教程 ⋅ 今天 ⋅ 0

谷歌:安全问题机制并不如你想象中安全

腾讯科技讯 5月25日,如今的你或许已经对许多网站所使用的“安全问题机制”习以为常了,但你真的认为包括“你第一个宠物的名字是什么?”这些问题能够保障你的帐户安全吗? 根据谷歌(微博)安...

问题终结者 ⋅ 今天 ⋅ 0

聊聊spring cloud gateway的RedisRateLimiter

序 本文主要研究下spring cloud gateway的RedisRateLimiter GatewayRedisAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springframework/cloud/gateway/con......

go4it ⋅ 今天 ⋅ 0

169. Majority Element - LeetCode

Question 169. Majority Element Solution 思路:构造一个map存储每个数字出现的次数,然后遍历map返回出现次数大于数组一半的数字. 还有一种思路是:对这个数组排序,次数超过n/2的元素必然在中...

yysue ⋅ 今天 ⋅ 0

NFS

14.1 NFS介绍 NFS是Network File System的缩写 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netapp公司参与并主导开发,最新为4.1版本 NFS数据传输基于RPC协议,RPC...

派派菠菜 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部