51. N 皇后

皇后的摆放规则

• 行(横)方向不能有两个
• 列(竖)方向不能有两个
• 对角线不能有两个

代码

import java.util.Arrays;

public class eightQueen {

    static int nQueen = 8;  //n皇后
    static int count = 0;   //记录有多少种摆法

    public static void main(String[] args) {
        System.out.println("hello world");
        int[] result = new int[nQueen]; //存放结果
        place(0,result);
        System.out.println("总共有 ： " + count + "种摆法");
    }

    /* 放置8皇后， 存入当前放置的对应的行，  */
    public static void place(int row, int[] result) {
        if (row >= nQueen) {
            //当row是第8个行， 能放第8行， 排完了。 完成
            System.out.println(Arrays.toString(result));
            System.out.println("------------------------------");
            count++;
            return;
        }

        // 遍历当前row的所有col元素是否满足
        for (int col = 0; col<nQueen; col++) {
            //如果可以，就再判断下一轮， 这个时候，row + 1， 然后又从col = 0 开始遍历
            if (isOK(row, col, result)) {
                result[row] = col;
                place(row + 1, result);//递归到下一行
            }
        }
    }

    // 规则 :
    // 1.当前格子的对应的行上，都没有，因为每次放都是新的一行， 所以这个情况不用判断。
    // 2.当前格子的对应的列上，都没有。
    // 3.当前格子的对应的对角线上， 都没有。
    public static boolean isOK(int row , int col, int[] result) {

        //值得注意的是： 
        // result存放的结果是 result[0]对应的是第1行的col值
        // result存放的结果是 result[1]对应的是第2行的col值
        // ....
        // 所以，这里对比存放的结果的时候， 查看的是for (int i = 0; i< row; i++)的条件。 
        // 对于result后面的值就不需要关心了，因为row+1行的值不关心，只关心前面已经存过的值
        
        if (row == 0 && col == 0 ) return true;
        for (int i = 0; i< row; i++) {
            //列方向不能有相同的两个
            if (result[i] == col ) return false;
            //对角线方向不能有相同的两个
            if (Math.abs(result[i] - col) == Math.abs(row - i) ) return false;
        }
        return true;
    }
}

递归 + 回溯 分析

// 遍历当前row的所有col元素是否满足
for (int col = 0; col<nQueen; col++) {
    //如果可以，就再判断下一轮， 这个时候，row + 1， 然后又从col = 0 开始遍历
    if (isOK(row, col, result)) {
        result[row] = col;
        place(row + 1, result);//递归到下一行
    }
}

• 因为是从第0行开始的， place(0,result); 会针对第0行的所有的col做情况筛选， 也就是遍历每一列。第0行总会有满足的条件， 所以就会递归到下一行。

• 如果接下来的某一行的col都不满足， 也就是当前这一行的情况不满足， 就会回到往上一级回溯， 也就是回到row-1行， 直到第0行。

• 只要第0行有满足的条件， 就会再次递归到下一行

执行结果 ：

4皇后结果

[1, 3, 0, 2]
------------------------------
[2, 0, 3, 1]
------------------------------
总共有 ： 2种摆法

4皇后结果

PS ：
[1, 3, 0, 2] 值是代码中的数组的索引的值， 从0开始计算。
4皇后4列对应的是0，1，2，3.

8皇后结果

[0, 4, 7, 5, 2, 6, 1, 3]
------------------------------
[0, 5, 7, 2, 6, 3, 1, 4]
------------------------------
[0, 6, 3, 5, 7, 1, 4, 2]
------------------------------
[0, 6, 4, 7, 1, 3, 5, 2]
------------------------------
....（.中间太多了，可以自己打印试试）
------------------------------
[7, 2, 0, 5, 1, 4, 6, 3]
------------------------------
[7, 3, 0, 2, 5, 1, 6, 4]
------------------------------
总共有 ： 92种摆法

也可以对比执行其他皇后情况 ： 5皇后， 6皇后.....

更多优化 ：

public static boolean isOK(int row , int col, int[] result) {
    if (row == 0 && col == 0 ) return true;
        for (int i = 0; i< row; i++) {
        //列方向不能有相同的两个
        if (result[i] == col ) return false;
        //对角线方向不能有相同的两个
        if (Math.abs(result[i] - col) == Math.abs(row - i) ) return false;
    }
    return true;
}

这里每次都要做一次for循环的比较， 可以优化到O(1)级别。

回头看规则 ：

• 行(横)方向不能有两个
• 列(竖)方向不能有两个
• 对角线不能有两个

定义三个数组，

• 一个保存行(横)方向的结果集，数组大小为n
• 一个保存 列(竖)方向的结果集，数组大小为n
• 一个保存对角线方向的结果集，数组大小为2n-1

关于对角线数组

对角线

对角线

对角线公式参考 ：八皇后||算法

每次递归+回溯的时候， 满足条件递归就赋值， 不满足条件回溯的时候就重置原来的值。

下一次做isOK比价的时候就直接取对应的值来做比较。可以优化到O(1)级别。