题目介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际象棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。高斯认为有76种方案。1854年柏林象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 Input 无输入数据 Output 输出所有解

题目思路

根据规则我们可以得出每行必有一个皇后，则找指定皇后时只需在当行遍历。 首先根据规则找到一个皇后，然后根据规则把棋盘上不能有皇后点全部标记，再在剩下的棋盘上找下一个没被标记的皇后，如果找不到则回溯。 回溯：这个操作需要在每一步结束时加个“快照”，以便于回溯

具体代码

package com.dreamchaser;

import java.util.Stack;

/**
 * 八皇后问题
 * 每行都肯定有一个皇后
 */
public class test4 {
    //维护一个当前正在处理的矩阵
    static int[][] finalCheckerBoard=new int[8][8];
    static Stack<Step> stack=new Stack<Step>();
    /**
     * 控制循环的开关
     */
    static boolean flag=true;

    public static void main(String[] args) {
        /**
         * 第n组解
         */
        int n=0;
        //初始值
        Spot spot=findOne(finalCheckerBoard,stack.size()+1);
        while (flag){
            Step step=new Step();

            if (spot!=null){
                //若找到则将这个点处理后的棋盘与原来棋盘合并，然后入栈
                int[][] c;
                c=handle(spot);
                finalCheckerBoard=merge(c,finalCheckerBoard);

                //赋值给step，相当于给当前步骤存档，以便回溯
                step.setSpot(spot);
                step.setCheckerboard(finalCheckerBoard);
                step.setNumber(stack.size()+1);
                //步骤入栈
                stack.push(step);

                spot=findOne(finalCheckerBoard,stack.size()+1);


                if (stack.size()==8){
                    Stack<Step> steps= (Stack<Step>) stack.clone();
                    n++;
                    System.out.println("第"+n+"组解：");
                    while (steps.size()>0){
                        System.out.println(steps.pop().spot);
                    }
                    recall();
                }
            }else{
                //若没找到，则回溯
                spot=recall();
            }
        }

    }

    /**
     * 回溯，返回上一步的下一个点，如果没有下一个点则放回null
     * @return 上一步的下一个点
     */
    private static Spot recall(){
            Step step=stack.pop();
            Spot spot=step.getSpot();
            if (spot.getY()<7){
                //处理finalCheckerBoard
                if (stack.isEmpty()){
                    //如果堆栈是空的话，则赋值一个初始值

                    finalCheckerBoard=new int[8][8];
                    for (int j=0;j<= spot.getY();j++){
                        finalCheckerBoard[spot.getX()][j]=1;
                    }
                }else {
                    //如果不为空，则直接从上一步中取值
                    finalCheckerBoard=stack.peek().getCheckerboard();
                    //因为之前没做过标记，这里回溯时前进一个防止重复
                    finalCheckerBoard[spot.getX()][spot.getY()]=1;
                }
                return findOne(finalCheckerBoard, step.getNumber());
            }
            if (stack.isEmpty()&&spot.getX()==0&&spot.getY()==7){
                flag=false;
            }
            //如果等于7，说明此皇后遍历完了，下一次得从上一个开始遍历
            return null;

    }



    /**
     * 在处理好的棋盘中找第number个皇后可以摆放的位置
     * @param handledcheckerboard 处理好的棋盘
     * @param number 第number个皇后
     * @return 摆放的位置
     */
    private static Spot findOne(int[][] handledcheckerboard,int number) {
        Spot spot=new Spot();
        int i=number-1;
        for (int j=0;j<8&&i<8;j++){
            if (handledcheckerboard[i][j]==0){
                spot.x=i;
                spot.y=j;
                return spot;
            }
        }

        return null;
    }


    /**
     * 处理棋盘
     * @param spot 皇后坐标
     * @return 处理好的棋盘
     */
    private static int[][] handle(Spot spot) {
        int x= spot.x;
        int y= spot.y;
        int[][] checkerboard=new int[8][8];
        for (int j=0;j<8;j++){
            checkerboard[x][j]=1;
        }
        for (int i = 0; i < 8; i++) {
            checkerboard[i][y]=1;
        }

        //处理对角线

        for (int i=0,j=y-x;i<8;i++,j++){
            if (j>=0&&j<8){
                checkerboard[i][j]=1;
            }
        }
        for (int i=0,j=x+y;i<8;i++,j--){
            if (j>=0&&j<8){
                checkerboard[i][j]=1;
            }
        }

        return checkerboard;
    }

    /**
     * 合并处理好的棋盘
     * @param checkerboards 处理好的棋盘
     * @return 合并好的棋盘
     */
    private static int[][] merge(int[][]...checkerboards) {
        int[][] checkerboard=new int[8][8];
        for (int[][] c:checkerboards){
            for (int i=0;i<8;i++){
                for (int j=0;j<8;j++){
                    if (c[i][j]==1){
                        checkerboard[i][j]=1;
                    }
                }
            }
        }
        return checkerboard;
    }

    /**
     * 记录点的坐标
     */
    private static class Spot{
        int x;
        int y;

        public Spot() {
        }

        public Spot(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        @Override
        public String toString() {
            return "Spot{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    /**
     * 记录每一步，便于存储和回溯
     */
    private static class Step{
        Spot spot;
        int[][] checkerboard;
        //记录序号
        int number;

        public Step() {
        }

        public Step(Spot spot, int[][] checkerboard, int number) {
            this.spot = spot;
            this.checkerboard = checkerboard;
            this.number = number;
        }

        public Spot getSpot() {
            return spot;
        }

        public void setSpot(Spot spot) {
            this.spot = spot;
        }

        public int[][] getCheckerboard() {
            return checkerboard;
        }

        public void setCheckerboard(int[][] checkerboard) {
            this.checkerboard = checkerboard;
        }

        public int getNumber() {
            return number;
        }

        public void setNumber(int number) {
            this.number = number;
        }
    }
}

运行截图

记录点滴，乐于分享，转载请注明出处。

愿我们能以梦为马，不负人生韶华！ 与君共勉！