51. N-Queens

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Code

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if(n <= 0){
            return res;
        }

        helper(res, new int[n], 0);
        return res;
    }
    /*
    [".Q..",  // Solution 1
     "...Q",
     "Q...",
     "..Q."],
     queens数组在这种情况下为[1,3,0,2]
     queens是为了检查当前行放了Q的位置是否在列上会有冲突
     因此在queens中不能有重复的数字
     行不用管，因为每一行只能放一个

     pos指的是行
    */
    private void helper(List<List<String>> res, int[] queens, int pos){
        // 到了最后一行
        if(pos == queens.length){
            addSolution(res, queens);
            return;
        }

        for(int i = 0; i < queens.length; i++){
            // 在第pos行，把queen放在位置i上，看是不是可行
            queens[pos] = i;
            if(isValid(queens, pos)){
                // 如果可行的话，就进入到下一行
                helper(res, queens, pos + 1);
            }
        }
    }

    private boolean isValid(int[] queens, int pos){
        for(int i = 0; i < pos; i++){
            // 放到当前行的时候，如果出现重叠的列，那就是false
            // 比如[1,1,.....]
            if(queens[i] == queens[pos]){
                return false;
            }
            // 判断斜线是不是相同
            /*
            ["Q...",
             ".Q..",
             "....",
             "...."],
            */
            // 此时pos = 1, i = 0, queens=[0,1,0,0]
            // queens[1] - queens[0] = 1
            // i - pos = 1
            // 返回false
            // 简单说就是： 如果两点的列之差(绝对值)等于行之差(绝对值) 那两点就在同一对角线上
            if(Math.abs(queens[pos] - queens[i]) == Math.abs(i - pos)){
                return false;
            }
        }
        return true;
    }

    // 得到一个有效解, 加入到最终的结果中
    private void addSolution(List<List<String>> res, int[] queens){
        List<String> list = new ArrayList<>();
        for(int i = 0; i < queens.length; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < queens.length; j++){
                if(queens[i] == j){
                    sb.append('Q');
                } else{
                    sb.append('.');
                }
            }
            // 完成一行了，加入到list中
            list.add(sb.toString());
        }
        res.add(list);
    }
}

time: O(N!) factorial space: O(N^2) 2 power of N