八皇后问题

概述

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

官方给出的答案:

public class Queen {
    private int[] column; //同栏是否有皇后,1表示有
    private int[] rup; //右上至左下是否有皇后
    private int[] lup; //左上至右下是否有皇后
    private int[] queen; //解答
    private int num; //解答编号

    public Queen() {
        column = new int[8+1];
        rup = new int[(2*8)+1];
        lup = new int[(2*8)+1];
        for (int i = 1; i <= 8; i++)
        column[i] = 0;
        for (int i = 1; i <= (2*8); i++)
            rup[i] = lup[i] = 0;  //初始定义全部无皇后
            queen = new int[8+1];
    }

    public void backtrack(int i) {
        if (i > 8) {
        showAnswer();
        } else {
            for (int j = 1; j <= 8; j++) {
                if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
                    //若无皇后
                    queen[i] = j; //设定为占用
                    column[j] = rup[i+j] = lup[i-j+8] = 1;
                    backtrack(i+1);  //循环调用
                    column[j] = rup[i+j] = lup[i-j+8] = 0;
                }
            }
        }
    }



    protected void showAnswer() {
        num++;
        System.out.println("      第"+num+"种");
        for (int y = 1; y <= 8; y++) {
            for (int x = 1; x <= 8; x++) {
                if(queen[y]==x) {
                    System.out.print("♛ ");
                } else {
                    System.out.print("✚ ");
                }
            }
        System.out.println();
        }
    }

    public static void main(String[] args) {
        Queen queen = new Queen();
        long startTime = System.currentTimeMillis();    //获取开始时间
        queen.backtrack(1);
        long endTime = System.currentTimeMillis();    //获取结束时间
        System.out.println("共用时"+(endTime-startTime)+"ms");
    }
}

运行结果:

      第1种                            第2种                       第3种
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
  第4种                                第5种                       第6种
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
.................................................
      第87种                            第88种                   第89种
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
      第90种                            第91种                   第92种
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 

总共用时46ms

我自己的:

package lwj.ppz.Main.栈;

public class 八皇后 {
    public static void main(String[] args) {
        eightQueens e = new eightQueens();
        long startTime = System.currentTimeMillis();    //获取开始时间
        e.solution(0);
        long endTime = System.currentTimeMillis();    //获取结束时间
        System.out.println("共用时"+(endTime-startTime)+"ms");
    }
}

class eightQueens {
    private int[] res;
    private int index;
    private int p;

    public eightQueens() {
        this.res = new int[8];
        this.index = 1;
        this.p = 0;
    }

    public void solution(int count) {
        if (count == 8) {
            print();
            return;
        }
        for (int i = 0; i < 8; i++) {
            res[count] = i;
            if (Judge(count)) {
            solution(count + 1);
            }
        }
    }

    private boolean Judge(int n) {
        for (int i = 0; i < n; i++) {
            if (res[i] == res[n] || Math.abs(n - i) == Math.abs(res[n] - res[i])) {
                return false;
            }
        }
        return true;
    }

    private void Init(int [][]map){
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                map[i][j]=0;
            }
        }
    }

    private void print() {
        System.out.println("      第"+index+"种");
        for (int i = 0; i < 8; i++) {
            for(int j=0;j<8;j++){
                if(res[i]==j){
                    System.out.print("♛ ");
                }else{
                    System.out.print("✚ ");
                }
            }
            System.out.println();
        }
        index++;
    }
}

运行结果

      第1种                            第2种                       第3种
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
  第4种                                第5种                       第6种
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
.................................................
      第87种                        第88种                       第89种
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
      第90种                        第91种                       第92种
✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛  ✚ ✚ ✚ ✚ ✚ ✚ ✚ ♛ 
✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ♛ ✚ ✚ ✚ ✚ ✚ 
♛ ✚ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚ 
✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚  ✚ ♛ ✚ ✚ ✚ ✚ ✚ ✚ 
✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚  ✚ ✚ ✚ ✚ ✚ ✚ ♛ ✚ 
✚ ✚ ✚ ✚ ✚ ♛ ✚ ✚  ✚ ✚ ✚ ♛ ✚ ✚ ✚ ✚  ✚ ✚ ✚ ✚ ♛ ✚ ✚ ✚ 

总共用时45ms

总结

其实不管是我的还是官方的都是用了递归加回溯来解决的,主要注意的是怎么判断两个皇后不在同一行,同一列,同一条斜线上。这点需要注意。

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/20190810094820
最后更新于:2020-02-26 16:20:59

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×