算法02：N 皇后问题

描述

整数 N 个皇后放在 N * N 的棋盘上，要求每个皇后不能相互攻击，即同一行、同一列、同一斜线上不能同时存在两个皇后，有多少种不同的方法？

分析

棋盘是个二维数组，但是每一行只有一个元素，那么可以用一维数组 board 表示棋盘, board[i] = j 表示第 i 个(行)皇后放在第 j 列上，此时再看条件

• 不能处于同一行：由于一维数组下标表示皇后所在行，则不用考虑两个皇后处在同一行，因为数组下标不可能重复；
• 不能处于同一列：对于第 i 个皇后来说，前面 i-1 个皇后均不能和第 i 个皇后所处的列相同，即 board[i] != board[0...(i - 1)];
• 不能处于同一斜线：对于第 i 个皇后，假设 board[i] = a, 则对于前面 i-1 个皇后中的任意一个 board[j] = b, 必须满足 |i - j| != |a - b|

代码

采用递归方式，先校验第 1 个皇后是否能摆放在第 1 列，如果可以则放置皇后并递归第 2 个皇后，否则检验第 1 个皇后是否能放置在第 2 列，如果可以则放置皇后并递归调用第 2 个皇后，否则继续检验第 3...n 列，直到最后一个皇后放置后递归结束。

代码如下

    /**
     * 返回 N 个皇后共有多少种放置方式
     * @param N
     * @return
     */
    public static int sum(int N) {
        if(N == 0) {
            return 0;
        }
        // 一维数组 board[i] = j 表示第 i 个皇后放置在第 j 列
        int[] board = new int[N];
        // 从第一个皇后开始递归
        return process(board, 0, N);
    }

    /**
     * 从第 row 个皇后开始摆放，返回 n 个皇后共有多少种放置方法
     * @param board
     * @param row
     * @param n
     * @return
     */
    private static int process(int[] board, int row, int n) {
        // 当最后一行放置皇后，则返回1表示完成一种摆放方式
        // 因为是从0开始摆放，此时实际是滴n-1行摆放成功即可认为完成了，下一次调用时正好加到了n
        if(row == n) {
            return 1;
        }
        int result = 0;
        for(int col=0; col<n; col++) {
            // 对于第 row 个皇后，需要检验是否与前面 row - 1 个皇后是否有冲突
            if(isValid(board, row, col)) {
                // 如果没冲突，则讲皇后摆放在该位置上
                board[row] = col;
                // 进行摆放第 row + 1 个皇后
                result += process(board, row+1, n);
            }
        }
        return result;
    }

    /**
     * 检验第 row 个皇后是否可以摆放在第 col 列上
     * @param board
     * @param row
     * @param col
     * @return
     */
    private static boolean isValid(int[] board, int row, int col) {
        for(int i=0; i<row; i++) {
            if(board[i] == col || Math.abs(row - i) == Math.abs(board[i] - col)) {
                return false;
            }
        }
        return true;
    }