递归解决八皇后问题

递归解决八皇后问题

√八皇后问题说明

• 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

• 该问题是国际西洋祺棋手马克斯贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击

• 即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

√八皇后思路分析

1)第一个皇后先放第一行第一列 arr[8] = {0,0}

2)第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完，找到一个合适

3)继续第三个皇后，还是第一列、第二列.直到第8个皇后也能放 在一个不冲突的位置，算是找到了一个正确解

4)当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即 将第一个皇后，放到第一列的所有正确解，全部得到.

5)然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4的 步骤

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通 过算法，用一个一维数组即可解决问题

例如 : arr[8]={0,4,7,5,2,6,1,3} ,我们可以使用这样的一维数组来解决问题, 例如该数组 就是将皇后摆放到 ,第一行的第一列 ,第二行的第五列 ………

代码示例(通过视频参考,对着敲出来的)

public class Eight_questions {
    public static void main(String[] args) {
​
        checkerboard c1 = new checkerboard();
        c1.check(8,0);
​
    }
}
​
class checkerboard {
    int [] arr= new int[8];
    int count = 0;
    public void check(int n, int index) {
        if (n == index){
            for (int i = 0;i < n ;i++){
                System.out.print(arr[i]+" ");
            }
            count+=1;
​
            System.out.println();
            System.out.println("第"+count+"种摆放");
​
        }else {
            for (int i = 0;i < n ;i++){
                //此时的n代表列
                arr[index] = i;
                //第index行第i列
                if (judge(index)){
                    check(n,index + 1);
                }
            }
        }
​
​
    }
​
    public boolean judge(int index){
        for (int i=0;i<index;i++){
            if (arr[i]==arr[index]||Math.abs(index - i)==Math.abs(arr[index]-arr[i])){
                return false;
            }
        }
        return true;
        //如果不起冲突就返回true
    }
​
}

实际分析一下代码

class checkerboard

创建一个类 ,用于实现八皇后的棋盘填充

 int [] arr= new int[8];
 //在类中创建一个全局变量数组,因为下面有两个方法需要使用到
 public void check(int n, int index) {
 //创建方法check,传参的参数 n为皇后棋子的个数,index表示从第几行开始
        if (n == index){
        //如果棋子个数和和行数一致表示皇后已经全部下完
            for (int i = 0;i < n ;i++){
            //循环行数对数组进行遍历,然后将数组的内容打印出来
                System.out.print(arr[i]+" ");
            }
            count+=1;
            System.out.println();
            System.out.println("第"+count+"种摆放");
        }

//如果数组没有完成填充(也就是八皇后的棋子没有下完)
else {
       for (int i = 0;i < n ;i++)
       //循环
       {
           //此时的n代表列
           arr[index] = i;
           //循环填充数组的内容
           //第index行第i列
           if (judge(index)){
           //接收judge方法来判断这个位置是否符合规范,若符合规范就执行下面的递归
           check(n,index + 1);
           //递归调用方法,每次添加都会增加一次行数
           }
       }
    }

public boolean judge(int index){
//这个方法主要用于判断皇后放置是否合法,接收参数index表示每行进行判断
        for (int i=0;i<index;i++){
        //循环
            if (arr[i]==arr[index]||Math.abs(index - i)==Math.abs(arr[index]-arr[i])){
            //判断数组的上下两行放置的列是否一致(如若一致表示皇后在同一列触犯了规则)
            //判断数组的上下两行,通过两个位置横纵坐标互减如果数值一致就说明在一条斜线之上
            //同时由于不可能同行因此不判断同行的情况
                return false;
                //如果不符合判断就返回false
            }
        }
        return true;
        //如果符合规范就返回true
    }