N-Queens(Hard)

Leetcode Source

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

解题思路：集合法

我们用三个集合来保存之前皇后的信息，就可以O(1)时间判断出皇后是否冲突。三个集合分别是行集合，用于存放有哪些行被占了，主对角线集合，用于存放哪个右上到左下的对角线被占了，副对角线集合，用于存放哪个左上到右下的对角线被占了。如何唯一的判断某个点所在的主对角线和副对角线呢？我们发现，两个点的行号加列号的和相同，则两个点在同一条主对角线上。两个点的行号减列号的差相同，则两个点再同一条副对角线上。

注意

主对角线row + col，副对角线row - col

复杂度

时间 O(N^2) 空间 O(N)

List<List<String>> res = new LinkedList<List<String>>();;
Set<Integer> rowSet = new HashSet<Integer>();
Set<Integer> diag1Set = new HashSet<Integer>();
Set<Integer> diag2Set = new HashSet<Integer>();

    public List<List<String>> solveNQueens(int n) {
        helper(new LinkedList<Integer>(), n, 0);
        return res;
    }

    public void helper(LinkedList<Integer> tmp, int n, int col){
        if(col == n){
            List<String> one = new LinkedList<String>();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append('.');
                }
                sb.append('Q');
                for(int j = num + 1; j < n; j++){
                    sb.append('.');
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 对于列col，看皇后应该放在第几行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三条线上已经有占据的皇后了，则跳过该种摆法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法递归求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);

                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Test instance = new Test();


        //wordList = ["hot","dot","dog","lot","log"]
        List<List<String>> res = instance.solveNQueens(8);

        for (List<String> li : res) {
            System.out.println("Result: ");
            for (String str : li) {
                System.out.println(str);
            }
            System.out.println("Done : ");
        }
    }