《算法设计与分析》八皇后问题

1、题目描述:在8x8的国际象棋上面摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列或者同一条斜线上，请问有多少种摆法？

当时高斯先生计算说有76种，但是最后有92种。

2、代码解析（递归） 

步骤：分解为两个子问题，首先在第一行放置一个棋子，第二在其他安全的不被攻击的地方放第二个棋子，以此类推。

结束条件：放完第八个棋子就结束了。

package com.yuanfeng.test;/**
 * Created by yuanfeng on 2019/7/17 10:12
 */

/**
 *@ClassName EightQueen
 *@Description T0D0
 *@Author yuanfeng
 *@Date 2019/7/17 10:12
 *@Version 1.0
 **/
public class EightQueen {

    //定义一个变量计算种数
    private static int count = 0;

    /*
    *
     * @Author yuanfeng
     * @Description //TODO
     * @Date 10:32 2019/7/17
     * @Param [row, j, chess]chess传进来的棋盘
     * @return int
     **/
    public static int security(int row,int j,int[][]chess){

        int i = 0,flag1 = 0,flag2= 0,flag3=0,flag4=0,flag5=0,k;
        //判断列方向的危险
        for(i = 0;i<8;i++){
            if(chess[i][j] != 0){
                flag1 = 1;
                break;
            }
        }
        //判断左上方,因为代码不好直接判断啊一条斜线
        for (i = row,k = j;i>=0 && k>=0;i--,k--){
            if(chess[i][k] != 0){
                flag2 = 1;
                break;
            }
        }
        //判右下方,因为代码不好直接判断啊一条斜线
        for (i = row,k = j;i<8 && k<8;i++,k++){
            if(chess[i][k] != 0){
                flag3 = 1;
                break;
            }
        }


        //判断右上方,因为代码不好直接判断啊一条斜线
        for (i = row,k = j;i>=0 && k<8;i--,k++){
            if(chess[i][k] != 0){
                flag4 = 1;
                break;
            }
        }
        //判断左下方,因为代码不好直接判断啊一条斜线
        for (i = row,k = j;i<8 && k>=0;i++,k--){
            if(chess[i][k] != 0){
                flag5 = 1;
                break;
            }
        }

        if(flag1 == 1 || flag2 == 1 || flag3 == 1 || flag4 == 1 || flag5 == 1){
            return 0;
        }else {
            return 1;
        }


    }
    /*
    *
     * @Author yuanfeng
     * @Description //TODO
     * @Date 10:22 2019/7/17
     * @Param [row, col, chess]chess代表指向每一行的指针
     * @return void
     **/
    //参数为row,col,指向棋盘的引用


    public static void eightQueen(int row,int col,int[][] chess){

        //建立一个临时棋盘来存放最后要打印的92个棋盘
        int[][] chess2 = new int[8][8];
        int i,j;
        //主棋盘赋值给临时的棋盘
        for( i = 0;i < chess2.length;i++){

            for (j = 0;j < chess2[0].length;j++) {

                chess2[i][j] = chess[i][j];
                }
        }

        //递归结束条件,row==8已经到了第九行了，代表前面已经结束了
        if(row == 8){
            count=count+1;
            System.out.println("第"+count+"种");
            for(i = 0;i<8;i++){
                for( j = 0;j<8;j++){
                    System.out.print(chess2[i][j]);
                }
                System.out.println();//换行
            }
            System.out.println();
        }else {

            //不符合条件的时候，判断这个位置是否有攻击危险
            //如果没有危险。继续往下
            //每一行一格一格往下判断

            for(j = 0;j<col;j++){
                //判断是否危险
                if(security(row,j,chess) == 1){

                    for(i = 0;i<8;i++){
                        chess2[row][i] = 0;//整行所有列的值赋值为0
                    }
                    chess2[row][j] = 1;//不危险的j的位置赋值为1
                    //接着下一行递归测试
                    eightQueen(row+1,col,chess2);
                }
            }
        }
    }
    public static void main(String[] args) {

        //定义一个二维数组来表示8x8的棋盘
        int chess[][] = new int[8][8];

        //棋牌所有初始化为0
        for(int i = 0;i < chess.length;i++){
            for (int j = 0;j < chess[0].length;j++){
                chess[i][j] = 0;
            }
        }

        eightQueen(0,8,chess);
        System.out.println("总共有"+count+"种解决方法");
    }

}

 

总结：

说说大体的思路，本身这个题目中我们首先将一个二维数组棋盘赋值为0，目的是最后1是代表的皇后。

递归进入eightQueen()的时候，最开始row是不满足row == 8这个条件的，所以这个时候进行else判断,定义一个security方法判断row行j列的元素是否安全，整行赋值0，安全的位置赋值1,row+1进行下一行的递归。

其中security这个方法是判断该皇后位置的左上方，右下方，左下方，右上方的位置是否存在冲突。