问题链接

51. N 皇后

问题描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例

解题思路

1. 用回溯进行穷举，直接暴力解题

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // init ans
        List<List<String>> ans = new ArrayList<>();
        List<String> initial = new ArrayList<>();

        recursion(ans, initial, n, 0);
        return ans;
    }

    public void recursion(List<List<String>> ans, List<String> res, int n, int row) {
        if (row == n) {
            ans.add(res);
            return;
        }

        for (int i = 0; i < n; i++) {
            // 验证 列 以及 斜线
            if (cheakColumn(res, n, row, i) && checkSlash(res, n, row, i)) {
                StringBuilder str = new StringBuilder();
                for (int k = 0; k < n; k++) {
                    if (k == i) {
                        str.append("Q");
                    } else {
                        str.append(".");
                    }
                }
                res.add(str.toString());
                recursion(ans, new ArrayList<>(res), n, row + 1);
                res.remove(res.size() - 1);
            }
        }
    }

    public boolean cheakColumn(List<String> res, int n, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (res.get(i).indexOf("Q") == col) {
                return false;
            }
        }
        return true;
    }

    public boolean checkSlash(List<String> res, int n, int row, int col) {
        // 验证“/”
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (res.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        // 验证“\”
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (res.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

2. 基于思路一，对列以及斜线的验证进行优化
用三个集合记录列以及两条斜线的使用情况，如果后续的皇后满足以下条件，那么可以被攻击到：
A. 列相同
B. 斜线1（ x + y）相同
C. 斜线2 （x - y）相同

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> shash1s = new HashSet<>();
        Set<Integer> shash2s = new HashSet<>();

        recursion(ans, res, n, 0, columns, shash1s, shash2s);
        return ans;
    }

    public void recursion(List<List<String>> ans, int[] res, int n, int row,
                          Set<Integer> columns, Set<Integer> shash1s, Set<Integer> shash2s) {
        if (row == n) {
            ans.add(convert(res));
            return;
        }

        for (int i = 0; i < n; i++) {
            // 验证 列 以及 斜线
            if (!columns.contains(i) && !shash1s.contains(row + i) && !shash2s.contains(row - i)) {
                StringBuilder str = new StringBuilder();
                for (int k = 0; k < n; k++) {
                    if (k == i) {
                        str.append("Q");
                    } else {
                        str.append(".");
                    }
                }
                res[row] = i;
                columns.add(i);
                shash1s.add(row + i);
                shash2s.add(row - i);

                recursion(ans, res, n, row + 1, columns, shash1s, shash2s);

                res[row] = -1;
                columns.remove(i);
                shash1s.remove(row + i);
                shash2s.remove(row - i);
            }
        }
    }
    
    public List<String> convert(int[] arr) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i <= arr.length - 1; i++) {
            int curColumn = arr[i];
            StringBuilder str = new StringBuilder();
            for (int j = 0; j <= arr.length - 1; j++) {
                if (j == curColumn) {
                    str.append("Q");
                } else {
                    str.append(".");
                }
            }
            res.add(str.toString());
        }
        return res;
    }
}