51. N-Queens

题目分析

N 皇后问题 + 回溯法

代码

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if(n <= 0) return res;
        List<Integer> cols = new ArrayList<>();
        helper(res, cols, n);
        return res;
    }
    public static boolean isConflict(List<Integer> cols, int col) {
        int row = cols.size();
        for(int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
            if(cols.get(rowIndex) == col) {
                return true;
            }
            if(Math.abs(cols.get(rowIndex) - col) == row - rowIndex) {
                return true;
            }
        }
        return false;
    }
    public static void helper(List<List<String>> res, List<Integer> cols, int n) {
        if(cols.size() == n) {
            res.add(drawChessBoard(cols));
            return;
        } else {
            for(int col = 0; col < n; col++) {
                if(isConflict(cols, col)) {
                    continue;
                }
                cols.add(col);
                helper(res, cols, n);
                cols.remove(cols.size() - 1);
            }
        }
    }
    public static List<String> drawChessBoard(List<Integer> cols) {
        List<String> chessboard = new ArrayList<>();
        for(int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < cols.size(); j++) {
                sb.append(j == cols.get(i) ? 'Q' : '.');
            }
            chessboard.add(sb.toString());
        }
        return chessboard;
    }
}