算法35: N皇后问题（力扣52, 51以及 面试题 08.12. 八皇后 ）

力扣52题：. - 力扣（LeetCode）

题目：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n?皇后问题?研究的是如何将?n?个皇后放置在?n×n?的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数?n?，返回所有不同的?n?皇后问题?的解决方案。

每一种解法包含一个不同的?n 皇后问题?的棋子放置方案，该方案中?'Q'?和?'.'?分别代表了皇后和空位。

假设4行4列的矩阵。

1. 假设第一行放入第一列放入Q. 那么第二行只能放入下标为2和3的位置。

	0	1	2	3
0	Q
1
2
3

2. 如果第二行放在下标为2的位置，那么第3行就没有地方放了。

	0	1	2	3
0	Q
1			Q
2
3

3. 如果第二行放在下标为3的位置，那么第三行就可以放在下标为1的位置.

	0	1	2	3
0	Q
1				Q
2		Q
3

4. 我发发现最后一行就没有地方放了。因为无论怎么放，要没列上方有Q，要么左上方或者右上方有值。也就是这种方案根本不成立。因此，我们在讨论每一种方案的时候，需要有一个逻辑判断：

之前所有行的当前列不能被占用过。其次，当前行当前列不能在之前行的左下或者右下方，否则会构成斜线。

第一行放在第二列和第三列，力扣已经给了详细的解释了，此处就不做过多的解释了。

package code03.动态规划_07.lesson5;

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣 52 题： https://leetcode.cn/problems/n-queens-ii/description/
 */
public class Queen_03_opt {

    public int totalNQueens(int n)
    {
        //边界值
        if (n < 1) {
            return 0;
        }

       //存放之前行的列下标，此下标代表放置了Q皇后
       int[] record = new int[n];
        //从第一行到最后一行，逐步摆放
        return process(record, 0, n);
    }


    public int process(int[] record, int row, int n)
    {
        //base case:
        // row从0到n-1行，如果row能走到n行，那么
        //说明 n-1行，即最后一行已经摆好了
        if(row == n) {
            return 1;
        }

        int ans = 0;
        //遍历列
        for (int i = 0; i < n; i++) {
            //当前行row的i列
            if (isValid(record, row, i)) {
               //row为行，i为列。遍历record
               //就可以知道每一行的那一列放了Q皇后
               record[row] = i;
                //处理下一行
                ans += process(record, row+1, n);
            }
        }

        return ans;
    }

    public boolean isValid(int[] record , int row, int col)
    {
         // 每一行摆放位置都是依赖之前行摆放的位置
         // 只判断之前摆放的行。
         for (int i = 0; i < row ; i++) {
             /**
              * 想要放在row行i列，需要判断row之前所有的行，i列是否放置了Q皇后
              * record[i] == col 就是之前行的当前列。
              *
              * 左下方或者右下方，就是坐标行加1，列加1或者减1.
              * 因此，行差和列差的绝对值，肯定是相等的
              */
             if (record[i] == col || Math.abs(record[i] - col) == Math.abs(row - i)) {
                 return false;
             }
         }

         return true;
    }

    public static void main(String[] args) {
        int n = 4;
        Queen_03_opt queen1 = new Queen_03_opt();
        System.out.println(queen1.totalNQueens(n));
    }
}

力扣51题：. - 力扣（LeetCode）

面试题8.12 ：?. - 力扣（LeetCode）

上一题说的是统计所有能够摆满N皇后的方案总数。 而这两题就是说，需要知道之前统计的方案的详细情况。具体摆在哪里，并打印出信息。这两题其实可以当做一道题来做

分析：

上一题的record就是记录每一行的摆放Q皇后的信息的。那么本题就是在原有的基础之上，把record信息收集一下就好了。而record是一维数组，记录每一行防止Q的列的下标。

既然是N行，那我们就把每一行在record能找到的下标设置位Q, 其他一律默认设置位 . 就好了。

package code03.动态规划_07.lesson5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 力扣 51 题： https://leetcode.cn/problems/n-queens/description/
 * 力扣
 */
public class Queen_04 {

    public  List<List<String>>  solveNQueens(int n)
    {
        //边界值
        if (n < 1) {
            return null;
        }

       int[] record = new int[n];
        //从第一行当最后一行，逐步摆放
        List<List<String>> allList = new ArrayList<>();
        process(record, 0, n, allList);

        return allList;
    }


    public int process(int[] record, int row, int n,  List<List<String>> allList)
    {
        //base case:
        // row从0到n-1行，如果row能走到n行，那么
        //说明 n-1行，即最后一行已经摆好了
        if(row == n) {
            return 1;
        }

        int ans = 0;
        //遍历列
        for (int i = 0; i < n; i++) {
            if (isValid(record, row, i)) {
               record[row] = i;
                //处理下一行
                int res =process(record, row+1, n, allList);
                if (res == 1 && (row + 1) == n) {
                    prt(record, n, allList);
                }
                ans += res;
            }
        }

        return ans;
    }

    public void prt (int[] record, int n, List<List<String>> allList)
    {
        List<String> cur_solution = new ArrayList<>();
        for (int i = 0; i < record.length; i++) {
            String str = "";
            int res = record[i];
            for (int j = 0; j < n; j++) {
                str = str + (res == j ? "Q" : ".");
            }
            cur_solution.add(str);
        }
        allList.add(cur_solution);
    }
    public boolean isValid(int[] record , int row, int col)
    {
         // 每一行摆放位置都是依赖之前行摆放的位置
         // 只判断之前摆放的行。
         for (int i = 0; i < row ; i++) {
             if (record[i] == col || Math.abs(record[i]- col) == Math.abs(row - i)) {
                 return false;
             }
         }
         return true;
    }

    public static void main(String[] args) {
        int n = 4;
        Queen_04 queen1 = new Queen_04();
        System.out.println(queen1.solveNQueens(n));
    }
}