数据结构与算法Java版——八皇后问题

雨点打透心脏的1/2处 2022-06-06 12:26 140阅读 0赞

**八皇后问题**是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。如图所示：

![84489047.jpg][]

问题关键在于每一列的皇后不能和其他列的皇后在同一行，同一斜线上（正斜线，反斜线均不可）。

public class Queen {
        
        /**
         * 累计方案
         */
        public static int num = 0;
        public static final int MAXQUEEN = 8;
        /**
         * 8列棋子每一列皇后位置 cols[0] = 0 ,cols[1] = 2;
         */
        public static int [] cols = new int[MAXQUEEN];  
    
        /**
         * 填第n列的皇后
         * @param n
         */
        public void getCount(int n){
            //记录每次递归时当前列的每个方格是否可以放皇后
            boolean [] rows = new boolean[MAXQUEEN];
            //记录所有不能放的位置
            for (int i = 0; i < n; i++) {
                //当前列N的的棋子不能放在前面列i的棋子的所在行上
                rows[cols[i]]=true;
                //当前列N的棋子到前面列i的棋子的距离
                int d = n - i;
                //当前列不能放在前面列i的棋子的正斜线上
                if(cols[i] - d >= 0){
                    rows[cols[i] - d] = true;
                }
                //当前列不能放在前面列i的棋子的反斜线上
                if(cols[i] + d < MAXQUEEN){
                    rows[cols[i] + d] = true;
                }
            }
            for (int i = 0; i < MAXQUEEN; i++) {
                //已经放了皇后的列跳过
                if(rows[i]){
                    continue;
                }
                //没有放便将位置存放在数组中
                cols[n] = i;
                if(n < MAXQUEEN - 1){
                    getCount(n+1);
                }else{
                    //方案加1
                    num++;
                    printQueen();
                }
                //继续循环，重n列的不同位置再开始
            }       
        }
    
        public void printQueen(){
            System.out.println("第"+num+"种方法：");
            for (int i = 0; i < MAXQUEEN; i++) {
                for (int j = 0; j < MAXQUEEN; j++) {
                    if(cols[j]==i){
                        System.out.print("o ");
                    }else{
                        System.out.print("+ ");
                    }
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            Queen queen = new Queen();
            queen.getCount(0);
        }
    }

以上就完成了八皇后问题的解法。

[84489047.jpg]: http://or0um8wrx.bkt.clouddn.com/17-11-8/84489047.jpg