八皇后问题-递归

八皇后问题-递归

伍陆柒 95 2022-04-03

八皇后问题(回溯算法)

八皇后问题求解,任意两个皇后不能处在同一行,同一列,同一斜线

  1. 第一个皇后放在第一行第一列

  2. 第二个皇后放在第二行的第一列,判断是否满足条件,不满足就移动下一列

  3. 满足条件后就放置下一个皇后,也是重复2的步骤,直到找到一个正确解或者列表末尾

  4. 当得到正确解后,栈退回至上一个栈,开始回溯,回溯上一步移动至下下一列,

    比如在[1][2]找到正确解,接下来从[1][3]开始寻找

  5. 直到所有栈退出,得到所有结果

主要是判断列重复,和同一斜线冲突,比较巧妙,同一斜线可以利用斜率相等求解(绝对值)

代码实现

import java.util.Arrays;

/**
 * @author 伍陆柒GUI
 * <p>
 * 八皇后问题求解,任意两个皇后不能处在同一行同一列,同一斜线
 * 1. 第一个皇后放在第一行第一列
 * 2. 第二个皇后放在第二行的第一列,判断是否满足条件,不满足就移动下一列
 * 3. 满足条件后就放置下一个皇后,也是重复2的步骤,直到找到一个正确解或者列表末尾
 * 4. 当得到正确解后,栈退回至上一个栈,开始回溯,回溯上一步移动至下下一列,
 * 比如在[1][2]找到正确解,接下来从[1][3]开始寻找
 * 5. 直到所有栈退出,得到所有结果
 */
public class EightQueen {
    int max = 8; //皇后数量为8
    static int count = 0; //统计结果总数
    int[] array = new int[max];
    /* 构建摆放列表
     * 比如array[]={0,4,7,5,2,6,1,3}
     * 这就时一种满足要求的摆放方式
     * 第一个摆在第一列,第二个摆在第五列,如此类推*/

    public static void main(String[] args) {
        EightQueen queen = new EightQueen();
        queen.check(0); //从第一行开始摆放
        System.out.println("总共解法:" + count);
    }


    //放置第n个皇后,检测是否和前面n-1个皇后冲突
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                /*
                 * 因为array第i个元素记录的是第 i 个皇后摆放的列数,比较值是否有相等就相当于比较是否同一列冲突
                 * 然后斜线相等,就是利用斜率判断
                 * 0 0 1   比如左边代表棋盘,很明显实际存储是array[0] = 2, array[1] = 1;
                 * 0 1 0   然后比较斜率(array[0]-array[1]) / (0 - 1) = 1
                 * 0 0 0   就相当于 array[0]-array[1] = 0 - 1
                 *         也就是 array[n] - array[i] = n - i (取绝对最值)
                 * */
                return false; //表示已经冲突,返回,需要移动到下一列判断
            }
        }
        return true; //没有冲突
    }

    //放置第N个皇后
    private void check(int n) {
        if (n >= max) { //8个皇后已经放好了
            System.out.println(Arrays.toString(array));
            count++;
            return;
        }
        //依次放入每一列,判断是否冲突
        for (int i = 0; i < max; i++) {
            array[n] = i; //首先将第N个皇后,放到这一行第一列
            if (judge(n)) { //判断是否与前几个皇后冲突
                check(n + 1); //不冲突就放下一个皇后
            }
            //如果冲突了,就把位置往后移动一个,执行array[n] = (i+1);
            /*
             * 因为是递归,当第最后一行找到一个满足结果,然后执行check(n+1)
             * 执行到check(8),程序会退出当前check,回到上一个check的for循环中
             * 依次吧上一个皇后位置往后面的列数移动,判断
             * 层层递归,最终递归回到第一次调用check(0),找遍位置,然后退出递推,得到所有结果
             */
        }
    }

}

# Java # 数据结构