51. N皇后

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

N皇后

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用DFS深度优先搜索，一路走到低，走不通回溯，再继续走

class Solution {
    private static final char QUEEN = 'Q';
    private static final char BLANK = '.';

    private Integer[] rowChoice;    // 记录每一行选择了哪个坐标
    private int targetN; // 记录n，避免参数多次传递，浪费栈空间
    private List<List<String>> result = new ArrayList<>();

    /**
     * 使用DFS深度优先搜索
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        if (n == 0) {
            return result;
        }
        rowChoice = new Integer[n];
        targetN = n;
        searchQueen(new ArrayList<>(n), 0);
        return result;
    }

    /**
     *
     * @param list 重复使用
     * @param curRow 当前行
     */
    private void searchQueen(List<String> list, int curRow) {
        if (curRow == targetN) { // 超过最后一行说明达到终点了
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < targetN; i++) {
            if (canAddQueen(curRow, i)) {
                // 创造一行数据
                char[] chars = new char[targetN];
                Arrays.fill(chars, BLANK);
                chars[i] = QUEEN;
                if (list.size() - 1 >= curRow) {
                    list.set(curRow, String.valueOf(chars));
                } else {
                    list.add(String.valueOf(chars));
                }
                rowChoice[curRow] = i;
                // 深入递归下一行，增加一行数据后，继续搜索下一行
                searchQueen(list, curRow + 1);
                // 恢复到不插入下一行的状态
                rollback(curRow);
            }
        }
    }

    /**
     * 回退，把row行及其之后的行记录都清空
     * @param row
     */
    private void rollback(int row) {
        for (int i = row; i < targetN; i++) {
            rowChoice[row] = null;
        }
    }

    /**
     * 判断这个坐标是否可以加入Queen
     * @param row
     * @param column
     * @return
     */
    private boolean canAddQueen(int row, int column) {
        for (int i = 0; i < row; i++) {
            // 行不需要判断，因为一行只会放一个元素
            // 列不能相同
            if (rowChoice[i] == column) {
                return false;
            }
            // 对角线，使用一元一次方程公式判断
            if (Math.abs(i - row) == Math.abs(rowChoice[i] - column)) {
                return false;
            }
        }
        return true;
    }
}

效果还不过

相同的解法，优化下判断当前坐标是否可以占用

class Solution {
    private static final char QUEEN = 'Q';
    private static final char BLANK = '.';

    private Set<Integer> rowChoice = new HashSet<>(); // 记录占据了哪几列
    private Set<Integer> leftSlant = new HashSet<>(); // 记录 y-x=b,记录b
    private Set<Integer> rightSlant = new HashSet<>();// 记录 y+x=b,记录b
    private int targetN; // 记录n，避免参数多次传递，浪费栈空间
    private List<List<String>> result = new ArrayList<>();

    /**
     * 使用DFS深度优先搜索
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        if (n == 0) {
            return result;
        }
        targetN = n;
        searchQueen(new ArrayList<>(n), 0);
        return result;
    }

    /**
     *
     * @param list 重复使用
     * @param curRow 当前行
     */
    private void searchQueen(List<String> list, int curRow) {
        if (curRow == targetN) { // 超过最后一行说明达到终点了
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < targetN; i++) {
            if (!rowChoice.contains(i) && !leftSlant.contains(curRow - i) && !rightSlant.contains(curRow + i)) {
                // 创造一行数据
                char[] chars = new char[targetN];
                Arrays.fill(chars, BLANK);
                chars[i] = QUEEN;
                if (list.size() - 1 >= curRow) {
                    list.set(curRow, String.valueOf(chars));
                } else {
                    list.add(String.valueOf(chars));
                }
                rowChoice.add(i);
                leftSlant.add(curRow - i);
                rightSlant.add(curRow + i);
                // 深入递归下一行，增加一行数据后，继续搜索下一行
                searchQueen(list, curRow + 1);
                // 恢复到不插入下一行的状态
                rowChoice.remove(i);
                leftSlant.remove(curRow - i);
                rightSlant.remove(curRow + i);
            }
        }
    }

    public static void main(String[] args) {
        List<List<String>> lists = new Solution().solveNQueens(4);
        System.out.println(lists);
    }
}

然而效果并不理想

效果不理想的原因，个人认为是测试用例的数据n不够大，没有发挥set的优势，虽然运行效率第二种方式比第一种方式低，个人还是倾向于使用第二种使用set

再次优化下，不使用set，直接使用数组访问，提高效率

class Solution {
    private static final char QUEEN = 'Q';
    private static final char BLANK = '.';

    private boolean[] rowChoice; // 记录占据了哪几列
    private boolean[] leftSlant; // 记录 y-x=b,记录b
    private boolean[] rightSlant;// 记录 y+x=b,记录b
    private int targetN; // 记录n，避免参数多次传递，浪费栈空间
    private List<List<String>> result = new ArrayList<>();

    /**
     * 使用DFS深度优先搜索
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        if (n == 0) {
            return result;
        }
        targetN = n;
        rowChoice = new boolean[targetN];
        leftSlant = new boolean[targetN * 2];
        rightSlant = new boolean[targetN * 2];
        searchQueen(new ArrayList<>(n), 0);
        return result;
    }

    /**
     *
     * @param list 重复使用
     * @param curRow 当前行
     */
    private void searchQueen(List<String> list, int curRow) {
        if (curRow == targetN) { // 超过最后一行说明达到终点了
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < targetN; i++) {
            if (!rowChoice[i] && !leftSlant[curRow - i + targetN] && !rightSlant[curRow + i]) {
                // 创造一行数据
                char[] chars = new char[targetN];
                Arrays.fill(chars, BLANK);
                chars[i] = QUEEN;
                if (list.size() - 1 >= curRow) {
                    list.set(curRow, String.valueOf(chars));
                } else {
                    list.add(String.valueOf(chars));
                }
                rowChoice[i] = true;
                leftSlant[curRow - i + targetN] = true;
                rightSlant[curRow + i] = true;
                // 深入递归下一行，增加一行数据后，继续搜索下一行
                searchQueen(list, curRow + 1);
                // 恢复到不插入下一行的状态
                rowChoice[i] = false;
                leftSlant[curRow - i + targetN] = false;
                rightSlant[curRow + i] = false;
            }
        }
    }

    public static void main(String[] args) {
        List<List<String>> lists = new Solution().solveNQueens(4);
        System.out.println(lists);
    }
}

效果理想