【回溯】八皇后的方案数——经典巨无霸

  • 时间:
  • 来源:互联网
  • 文章标签:

问题描述:

皇后问题是指在8*8的棋盘上放置8个皇后,使这8个皇后无法吃掉对方(也就是说两两不在一行,不在一列,也不在对角线上),求放置皇后的方案数

输入:

输出:

一个整数,表示方案数


解法:回溯试探

思路

(1)用一个数组arr表示放置的方式,例如arr[i] = j表示在第i行第j列放置一个皇后,i和j均从0开始,即0表示第一行(列)
(2)一行一行的放置皇后,挨个位置进行试探,如果该位置可用,继续进行下一行的试探,如果该位置不可用,那么回退,将这个皇后放置到下一列
(3)直到行数等于8,方案数+1,否则继续进行下一行的试探

代码

/**
 * 八皇后问题
 * (有多少种摆法)
 */
public class Main {
    /**  放置的方案数 */
    static int count = 0;
    public static void main(String[] args) {
        // arr[i] = j : 表示第i行j列放置了一个皇后
        int[] arr = new int[8];
        queen(arr,0, 8);
        System.out.println(count);
    }

    /**
     * 回溯解法
     */
    private static void queen(int[] arr, int i, int n) {
        if(i == n){
            // 方法数加一
            ++ count;
            return;
        }else {
            for (int j = 0; j < n; j++) {
                // 往第i行第j列放置一个皇后
                arr[i] = j;
                // 判断前面放的i行是否符合条件,如果符合,则放置下一行,如果不符合,继续试探j + 1列
                if(judge(arr, i)){
                    queen(arr, i + 1, n);
                }
            }
        }
    }

    /**
     * 判断已经放置的皇后位置是否可行
     */
    private static boolean judge(int[] arr, int i) {
        for (int ii = 0; ii < i; ii++) {
            // 同列 || 主斜线 || 副斜线
            if(arr[i] == arr[ii] || i - ii == arr[i] - arr[ii] || i - ii == arr[ii] - arr[i]){
                return false;
            }
        }
        return true;
    }
}

运行结果

本文链接http://www.taodudu.cc/news/show-1944494.html