一、问题描述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

二、解决思路

首先明确每一行只能放置一个棋子，那么每一行的放置位置假设为路径树的节点位置，从0行到i行，每一列代表一个可能的解，重而定义解空间

n皇后.png

限界函数则是判断当前位置，和已经放置节点的位置有没有冲突，如果没有冲突则代表可以放置，否则不能，这个问题是求解所有的解决算法，所以没有剪枝函数

三、代码

public class NQueen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //记录所有的结果
        List<List<Integer>> allResult = new ArrayList<>();
        //记录当前流程节点状态
        int[] currentValue = new int[n];
        calc(allResult,currentValue,0,n);
        System.out.println(allResult.toString());

    }

    /**
     * 放旗子
     *
     * @param allResult
     * @param currentValue
     * @param i
     */
    public static void calc(List<List<Integer>> allResult, int[] currentValue, int i, int n) {
        
        // 搜索结束 i大于数组的长度
        if (i > n - 1) {
            //代表找到一种可能解加入到所有的解之中
            allResult.add(Arrays.stream(currentValue).boxed().collect(Collectors.toList()));
        }

        /**
         * 搜索过程 就是判断当前列是否能够存放
         */
        for (int j = 0; j < n; j++) {
            if (isOK(currentValue, i, j, n)) {
                // 代表当前点可以放
                currentValue[i] = j;
                // 递归进行下一行的存放
                calc(allResult, currentValue, i + 1, n);
            }
        }
        
    }

    /**
     * 判断当前位置是否能够放置棋子
     *
     * @param currentValue
     * @param i            当前棋子索引
     * @param j            列
     * @param n            总大小
     * @return
     */
    private static boolean isOK(int[] currentValue, int i, int j, int n) {
        //找到是否和当前节点同列或者同斜线的 循环每一行
        for (int k = 0; k < i; k++) {
            //找同列
            if (currentValue[k] == j) {
                return false;
            }
            //获得第k行的l列 对角线左侧
            int l = j - (i - k);
            int r = j - l + j;
            //判断是不是在一个横线上
            if (currentValue[k] == l || currentValue[k] == r) {
                return false;
            }
        }

        return true;
    }
}

四、优化空间