文档章节

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

一贱书生
 一贱书生
发布于 2016/07/28 09:59
字数 2457
阅读 16
收藏 0

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

 

思路一:

由于八个皇后的任意两个不能处在同一行,那么这肯 定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8],数组中第i个数字表示位于第i行的皇后的列号。先把 ColumnIndex的八个数字分别用0-7初始化,接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数 组中的数字,因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上,也就是数组的两个下标i和j,是不是 i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。

 

package cglib;

 

public class DeleteNode{
    static int g_number = 0;
    
    public static void EightQueen( )  
    {  
          
        final int queens = 8;  
        int[] ColumnIndex=new int[queens];  
        for(int i = 0 ; i < queens ; ++i)  
            {ColumnIndex[i] = i;    //初始化
            System.out.println("ColumnIndex[i="+i+"]="+ColumnIndex[i]);  
            }
         
        perm(ColumnIndex ,  0,queens-1);  
    }  
    
    public static boolean Check(int ColumnIndex[] , int length)  
    {  
        int i,j;  
        for(i = 0 ; i <= length; ++i)  
        {  
            for(j = i + 1 ; j <= length; ++j)  
            {  
                if( i - j == ColumnIndex[i] - ColumnIndex[j] || j - i == ColumnIndex[i] - ColumnIndex[j])   //在正、副对角线上  
                    return false;  
            }  
        }  
        return true;  
    }  
    
    
    public static void main(String[] args) {  
          
        EightQueen();
       
    }
    
   
    
    public static void Print(int buf[] , int length)  
    {  
        
        System.out.println("g_number="+g_number);
        /*for(int i = 0 ; i <= length; ++i)  
            System.out.print("buf[i="+i+"]="+buf[i]);  
        System.out.println();  */
    }  

    public static void perm(int[] buf,int start,int end){  
        
          
        if(buf==null || end!=buf.length-1)  
           return ;
        
        if(start==end){
              
            if( Check(buf , end) )   //检测棋盘当前的状态是否合法  
            {  
                ++g_number;  
                Print(buf , end);  
            }  
                          
                }  
             
        else{
              
            for(int i=start;i<=end;i++){  
                //System.out.println("交换前:buf[start="+start+"]="+buf[start]);
                //System.out.println("交换前:buf[i="+i+"]="+buf[i]);
                int temp=buf[start];
               
                buf[start]=buf[i];                
                buf[i]=temp;                 
                
                perm(buf,start+1,end);
                  
                temp=buf[start];

       
                buf[start]=buf[i];  

                buf[i]=temp;
                //System.out.println("变回来:buf[start="+start+"]="+buf[start]);
                //System.out.println("变回来:buf[i="+i+"]="+buf[i]);  

            }  

        }
          

    }
   

     }

 

思路2:

   首先,可归纳问题的条件为,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行不能放棋子。这样我们就能写成下列程序段了:

 

       

[java] view plain copy

 

  1. boolean[] rows = new boolean[8];  
  2.          
  3.   
  4.       for(int m=0;m<N;i++){  
  5.          
  6.   
  7.          rows[cols[m­]]=true;//当前列N的棋子不能放在前面列m的棋子所在行。  
  8.           
  9.   
  10.          int d = N-m;  
  11.   
  12.          
  13.   
  14.         //该句用于设置当前列N的棋子不能放在前面列m的棋子的斜线上  
  15.   
  16.          
  17.   
  18.         if(cols­­-d >= 0)rows[cols­-d]=true;   
  19.   
  20.        
  21.   
  22.        // 该句用于设置当前列N的棋子不能放在前面列m的棋子的反斜线上  
  23.   
  24.         
  25.   
  26.         if(cols+d <=8-1)rows[cols­+d]=true;    
  27.   
  28.   }   
  29.   
  30.          

           

 

 

       好了,到此为止,我们程序的核心内容都具备了,一个基于深度优先的遍历流程和一个判断位置是否合适的算法。下面贴出运行后算出的所有可行方案(即92种,“+”号代表空棋位,“0”代表皇后所在位置)

 

打印结果

 

 

 

 

package cglib;

 

public class DeleteNode{
       public static int num = 0; //累计方案总数  
        public static final int MAXQUEEN = 8;//皇后个数,同时也是棋盘行列总数  
        public static int[] cols = new int[MAXQUEEN]; //定义cols数组,表示8列棋子摆放情况  
        public  DeleteNode() {  
           //核心函数  
          getArrangement(0);  
          System.out.println("综上所述");  
          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+"种走法 /n");  
             
           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("/n");  
           }  
             
        }  
        public static void main(String args[]){  
            DeleteNode queen = new DeleteNode();  
        }
   

     }

 

/**
 * 功能:打印八皇后在8*8棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。
 * 这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。

 */

 

 

[java] view plain copy

 

  1. static int GRID_SIZE=8;  
  2.   
  3. /** 
  4.  * 思路:每一行只能摆放一个皇后,因此不需要将棋盘存储为完整的8*8矩阵,只需一维数组,其中columns[r]=c表示有个皇后位于r行c列。 
  5.  * @param row 
  6.  * @param columns 
  7.  * @param results 
  8.  */  
  9. public static void placeQueen(int row,Integer[] columns,ArrayList<Integer[]> results){  
  10.     if(row==GRID_SIZE){  
  11.         /*Creates and returns a copy of this object. The precise meaning of "copy" may depend on the class of the object. 
  12.          *  The general intent is that, for any object x, the expression:  
  13.             x.clone() != x              will be true. 
  14.          *  and that the expression:  
  15.             x.clone().getClass() == x.getClass()    will be true.  
  16.          *  but these are not absolute requirements. While it is typically the case that:  
  17.             x.clone().equals(x) will be true, this is not an absolute requirement. */  
  18.         results.add(columns.clone());             
  19.     }else{  
  20.         for(int col=0;col<GRID_SIZE;col++){  
  21.             if(checkValid(columns,row,col)){  
  22.                 columns[row]=col;//摆放皇后  
  23.                 placeQueen(row+1, columns, results);  
  24.             }  
  25.         }  
  26.     }  
  27. }  
  28.   
  29. /** 
  30.  * 检查(row,column)是否可以摆放皇后,方法: 
  31.  * 检查有无其他皇后位于同一列或对角线,不必检查是否在同一行上,因为调用placeQueen时,一次只会摆放一个皇后。由此可知,这一行是空的。 
  32.  * @param columns 
  33.  * @param row 
  34.  * @param column 
  35.  * @return 
  36.  */  
  37. public static boolean checkValid(Integer[] columns,int row,int column){  
  38.     for(int r=0;r<row;r++){  
  39.         int c=columns[r];  
  40.         /* 检查同一列是否有皇后 */  
  41.         if(c==column)  
  42.             return false;  
  43.           
  44.         /* 检查对角线: 
  45.          * 若两行的距离等于两列的距离,则表示两个皇后在同一对角线上。 
  46.          */  
  47.         int columnDistance=Math.abs(c-column);  
  48.         int rowDistance=row-r;//row>r,不用取绝对值  
  49.         if(columnDistance==rowDistance)  
  50.             return false;  
  51.     }  
  52.       
  53.     return true;  
  54. }  

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
2018/07/03
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
面试 5:手写 Java 的 pow() 实现

我们在处理一道编程面试题的时候,通常除了注意代码规范以外,千万要记得自己心中模拟一个单元测试。主要通过三方面来处理。 功能性测试 边界值测试 负面性测试 不管如何,一定要保证自己代码...

nanchen2251
2018/07/10
0
0
飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙
2016/01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

总结:volatile关键字

实现内存可见性原理: 对volatile变量执行写操作时,会在写操作之后加入一条store指令,将CPU缓存数据强制刷新到主内存中 对volatile变量执行读操作的时候,会在读操作前加入一条load指令,重...

浮躁的码农
26分钟前
0
0
OSChina 周六乱弹 —— 看见这花臂了么?赶紧叫大佬!

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享周华健的单曲《有没有一首歌会让你想起我》 《有没有一首歌会让你想起我》- 周华健 手机党少年们想听歌,请使劲儿戳(这里) ...

小小编辑
今天
119
4
Confluence 6 升级中的一些常见问题

升级的时候遇到了问题了吗? 如果你想尝试重新进行升级的话,你需要首先重新恢复老的备份。不要尝试再次对 Confluence 进行升级或者在升级失败后重新启动老的 Confluence。 在升级过程中的一...

honeymoose
今天
2
0
C++随笔(四)Nuget打包

首先把自己编译好的包全部准备到一个文件夹 像这样 接下来新建一个文本文档,后缀名叫.nuspec 填写内容 <?xml version="1.0"?><package xmlns="http://schemas.microsoft.com/packaging/201......

Pulsar-V
今天
3
0
再谈使用开源软件搭建数据分析平台

三年前,我写了这篇博客使用开源软件快速搭建数据分析平台, 当时收到了许多的反馈,有50个点赞和300+的收藏。到现在我还能收到一些关于dataplay2的问题。在过去的三年,开源社区和新技术的发...

naughty
今天
23
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部