题解 | #N皇后问题#

public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        // write code here
        if (1 == n) {
            return 1;
        }
        // 具体代码实现
        // 定义一个整型数组，下标 i 表示的是第 i 行，que[i] 表示的是第 j 列
        int[] que = new int[n];
        // 调用自定义方法
        int result = FindN(0, que, n);
        // 返回结果
        return result;
    }
    
    /*
     * 具体的实现过程
     * i   表示的是当前搜索的行数
     * que 表示的是[0 ... i-1]范围上的皇后的位置
     * n   表示的是整个棋盘的大小
     */
    public static int FindN(int i, int[] que, int n) {
        // 当 i == n 时，表示已经得到了一个摆法
        if (i == n) {
            return 1;
        }
        // 定义一个整型变量，用于存放多少种摆法
        int rs = 0;
        // 遍历当前行的所有可能的结果
        for (int j = 0; j < n; j++) {
            if (isValid(que, i, j)) { // 判断 (i, j) 位置上的摆放是否合法
                que[i] = j;
                rs += FindN(i + 1, que, n); // 加上下一行的摆放次数
            }
        }
        return rs;
    }
    
    /*
     * 验证 (i, j) 位置上的摆放是否合法(任何两个皇后不同行，不同列也不在同一条斜线上)
    */
    public static boolean isValid (int[] que, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (que[k] == j || Math.abs(que[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }
}