Leetcode-51. N皇后

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

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

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

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

示例:

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

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

解法：看到这种题目，应该能想到使用dfs进行回溯，最浅层就是第一层，最深层就是第N层，每一层进行的操作就是查看有没有位置放置皇后，如果有，对下一层执行递归，没有就返回（这里可以执行剪枝避免无用路径）；直到最后一层，如果有位置，添加到结果，没有往上回溯。时间复杂度O（N！），放置一个皇后方法不超过N种，放置两个皇后不超过N*（N-2）种，放置三个皇后不超过N*(N-2)(N-4)种，以此类推。空间复杂度O（N）

• Java

class Solution {
   
    public List<List<String>> solveNQueens(int n) {
   
        Set<Integer> left = new HashSet<>();
        Set<Integer> right = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        this.dfs(0, n, cols, left, right, tmp, res);
        return this.formatting(res, n);
    }

    public void dfs(int level, int n, Set<Integer> cols, Set<Integer> left, Set<Integer> right, List<Integer> tmp, List<List<Integer>> res){
   
        if (tmp.size()==n) {
   
            // res.add(tmp); DO NOT ADD TMP DIRECTLY! tmp will change in backtracing! add a copy of tmp!
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i=0;i<n;i++) {
   
            if (!cols.contains(i) && !left.contains(level+i) && !right.contains(level-i)) {
   
                cols.add(i);
                left.add(level+i);
                right.add(level-i);
                tmp.add(i);
                this.dfs(level+1, n, cols, left, right, tmp, res);
                cols.remove(i);
                left.remove(level+i);
                right.remove(level-i);
                tmp.remove(Integer.valueOf(i)); // remove(i) will not remove the i value in tmp ,but will remove the ith value! MARK THAT!
            }
        }
        return ;
    }
    public List<List<String>> formatting(List<List<Integer>> lst, int n){
   
        List<List<String>> res = new ArrayList<>();
        for (List<Integer> tmp:lst) {
   
            List<String> l = new ArrayList<>();
            for (Integer col:tmp) {
   
                String str = "";
                for (int i=0;i<n;i++) {
   
                    if (i==col){
   
                        str += "Q";
                    }else{
   
                        str += ".";
                    }
                }
                l.add(str);
            }
            res.add(l);
        }
        return res;
    }
}

• Python

class Solution:
    def solveNQueens(self, n: int):
        self.n, self.cols, self.left, self.right, self.tmp, self.res = n, set(), set(), set(), [], []
        self.dfs(0)
        return self.formatting()
    def dfs(self, level):
        if len(self.tmp) == self.n: 
            self.res.append(self.tmp.copy())
            return
        for i in range(self.n):
            if i not in self.cols and (level+i) not in self.left and (level-i) not in self.right:
                self.cols.add(i)
                self.left.add(level+i)
                self.right.add(level-i)
                self.tmp.append(i)
                self.dfs(level+1)
                self.cols.remove(i)
                self.left.remove(level+i)
                self.right.remove(level-i)
                self.tmp.pop()
        return
    def formatting(self):
        l1 = []
        for lst in self.res:
            l = []
            for num in lst:
                str = ""
                for i in range(self.n):
                    if i==num:
                        str += "Q"
                    else:
                        str += "."
                l.append(str)
            l1.append(l)
        return l1

Leetcode-52. N皇后 II

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

解法：同上题一样的方法。这道题和上一题都是用array来存储，不使用hashset的话，会减少很多时间，只给出java代码，因为解法实在是一毛一样

• Java

public class Solution {
   
    int count = 0;
    public int totalNQueens(int n) {
   
        boolean[] cols = new boolean[n];     // columns |
        boolean[] d1 = new boolean[2 * n];   // diagonals \
        boolean[] d2 = new boolean[2 * n];   // diagonals /
        backtracking(0, cols, d1, d2, n);
        return count;
    }
    
    public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
   
        if(row == n) count++;

        for(int col = 0; col < n; col++) {
   
            int id1 = col - row + n;
            int id2 = col + row;
            if(cols[col] || d1[id1] || d2[id2]) continue;
            
            cols[col] = true; d1[id1] = true; d2[id2] = true;
            backtracking(row + 1, cols, d1, d2, n);
            cols[col] = false; d1[id1] = false; d2[id2] = false;
        }
    }
}