方法的递归经典问题--八皇后问题

方法的递归经典问题–八皇后问题

八皇后问题，非常有意思的问题
数学家高斯给了76种方法，今天我们利用计算机能给出92种！
我们自己如果没有什么图论基础去玩八皇后这个小游戏，我们只能一个个的试，计算机也是如此。
游戏思路是利用方法递归，把8×8的方格内的所有情况（实际上不是所有情况，而是每一行放置一个皇后的所有情况，我们先利用游戏规则简化了代码）全部列出，经判断筛选出正确的。

代码实现

package 八皇后问题;
import java.util.Arrays;
public class bahuanghou {
    public static void main(String[] args) {
        //该问题用二维数组是小题大做
        //一个一维数组即可，每个元素代表一个皇后，每个皇后在不同行上面
        int[] arr = new int[8];//如{1, 5, 8, 6, 3, 7, 2, 4}
        bahuanghou ba = new bahuanghou();
        ba.add(1, arr);//调用方法
    }
    //定义一个方法，用于添加新位置
    public void add(int n, int[] arr) {
        //行数为n,对于n行的1-8全部试完，就进入n+1行
        // 试着将1-8位置都试一下
        while (n <= 8) {
            int[] brr = {0};//定义brr的目的是看数组的第8个数有没有被改变
            for (int i = 1; i <= 8; i++) {
                //尝试，1-8
                if (check(i, n, arr, brr)) {
                    //如果该位置可以
                    // 进行下一行添加
                    add(n + 1, arr);
                } else {
                    //如果该点不行，试试它右边的点
                    continue;
                }
            }
            //每一次调用add不能都打印数组，只有当数组的8个数全部填充完毕
            if (n == 8) {
                if (brr[0] == 1) {
                    System.out.println(Arrays.toString(arr));
                }
            }
            return;
        }
    }
    //定义一个方法，用于判断新位置是否成立
    public boolean check(int i, int n, int[] arr, int[] brr) {
        for (int m = 0; m < n - 1; m++) {
            if (i == arr[m]) {
                return false;
            }
            if (Math.abs((i - arr[m])) == Math.abs((m + 1 - n))) {
                return false;
            }
        }
        arr[n - 1] = i;
        if (n == 8) {
            brr[0] = 1;
        }
        return true;
    }
}

代码实现的核心是下面这个检查方法（检查位置是否能放置皇后），第一个if语句用来判断是否与之前的皇后位于同一列
如果位于同一列，那么他们对应的数组元素大小应该相等！，第二个if语句用来判断是否与之前的皇后位于同一斜线上，利用了
|y1-y2|=|x1-x2|的原理

其中红色框内的brr数组用来检查第八个数的，如果不检查第八个数字，那么在我写的方法中，无论是成功的8皇后数组，还是只成功了7个的（第八个用上一次的位置）都会被打印，所以借助brr数组，来控制这一缺陷。
下面定义一个方法，用来循环放置皇后

最后调用方法，打印

结果由96种，这里只有第一页

本文地址：https://blog.csdn.net/wokkkok/article/details/111935933