递归 -八皇后问题

8皇后问题

  • 问题描述
  • 思路
  • 代码分析
  • 难点

问题描述

在国际棋盘上,放置8个皇后,要求,皇后之间不能互相攻击,即不能同一行,不能同一列,不能在对角线

思路

  • 第一个皇后放在第一行第一列

  • 第二个皇后放在第二行第一列,判断是否满足条件,不满足就放在第二列,第三列……直到找到合适的

  • 继续第三个皇后,同样是先第三行第一列,第二列,第三列…….因为是递归,最终会回溯找到一个合适的位置

  • 当8歌皇后都放在正确的位置时,在栈上木安回退到上一个栈,就会开始回溯,找到第一个皇后在第一列的所有正确结果

  • 然后把第一个皇后放在第二个位置,重复上述步骤

tips :

皇后的位置用一维数组表示,索引表示行数,数值表示列数

代码

package henu.recursion;

public class Queen {
    //定义一个递归调用次数
    public static int num = 0;
    //定义找到的方案的个数
    public static int resNum = 0;
    //定义判断是否冲突的次数
    public static int judgeNum = 0;
    //定义max,皇后数量
    int max = 8;
    //结果数组
    int[] arr = new int[max];
    public static void main(String[] args) {
        Queen queen = new Queen();
        queen.check(0);
        System.out.println(num);
        System.out.println(resNum);
        System.out.println(judgeNum);
    }

    //输出结果
    private void print() {
        resNum++;
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    //放置皇后
    private void check(int n) {
        num++;
        //递归终止条件
        if(n == max) {
            print();
            return;
        }
        //依次放入皇后,判断是否冲突
        for(int i=0;i<max;i++) {
            //先把当前皇后 n,放到该行的第一列
            arr[n] = i;
            //判断是否冲突
            if(judge(n)) {
                //不冲突,放置下一个皇后
                check(n+1);
            }
            //冲突,会回溯,把第n个皇后放到下一列(for循环)
        }
    }

    /**
     *
     * @param n 第n个皇后
     * @return
     */
    public boolean judge(int n) {
        judgeNum++;
        for(int i=0;i<n;i++) {
            //位于同一列 , 行差等于列差,判断是否为对角线
            if(arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n]-arr[i])) {
                return false;
            }
        }
        return true;
    }

}

Output:
0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
    ......
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
2057
92
15720

难点

如何理解,在找到一个正确答案时,会执行思路的第四步?

  • 在把最后一个皇后第一次放在合适的位置时,坐上面的栈return了,会执行下一个置顶栈

  • 也就是第7个皇后的位置,然后,挪动第7个皇后,判断是否合适…..

  • 第7个没合适的就继续回溯,去改变第6个皇后,以此类推……..

  • 最终会找到第一个皇后在第一列时的所有正确方案

  • 然后第一个皇后又会放在第二列,重复上述整个过程

  • 整个程序执行完毕就是第一个皇后遍历的所有的7列找到所有的合适位置才会最终退出这个程序

  • 可以看出,最后程序一共递归了2057次,找到了92种方案,判断了15720次

可以看出递归的资源浪费量巨大