178 - 52 n皇后2

题目

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

img

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

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

示例:

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

["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]

解答

https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

image-20191221095220049

全排列为例

img

我们定义的backtrack函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性：剩余选择和已走路径。每当走到树的底层，其「路径」就是一个全排列。

各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样

image-20191221095505611

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。

img

不管怎么优化，时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

n皇后

决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

python的数组似乎是浅拷贝，因此board生成之后就全部都被修改了。。

var solveNQueens = function(n) {
  if (n === 0) {
    return []
  }
  let res = []
  let board = []
  for (let i = 0; i < n; i++) {
    let tmp = []
    for (let j = 0; j < n; j++) {
      tmp.push(".")
    }
    board.push(tmp)
  }

  const valid = function(board, row, col) {
    for (let i = 0; i < n; i++) {
      if (board[i][col] === "Q") {
        return false
      }
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === "Q") {
        return false
      }
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === "Q") {
        return false
      }
    }
    return true
  }
  const backtrack = function(board, row) {
    if (row === n) {
      tmp = []
      for (const item of board) {
        tmp.push(item.join(""))
      }
      res.push(tmp)
      return
    }
    for (let col = 0; col < n; col++) {
      if (!valid(board, row, col)) {
        continue
      }
      board[row][col] = "Q"
      backtrack(board, row + 1)
      board[row][col] = "."
    }
  }

  backtrack(board, 0)
  return res
};

Runtime: 68 ms, faster than 79.26% of JavaScript online submissions for N-Queens.

Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions for N-Queens.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        queens = [-1]*n
        columns = [True]*n+[False]
        back = [True]*n*2
        forward = [True]*n*2
        row = col = 0
        while True:
            if columns[col] and back[col-row+n] and forward[col+row]:
                queens[row] = col
                columns[col] = back[col-row+n] = forward[col+row] = False
                row += 1
                col = 0
                if row == n:
                    ans.append(['.'*q+'Q'+'.'*(n-q-1) for q in queens])
            else:
                if row == n or col == n:
                    if row == 0:
                        return ans
                    row -= 1
                    col = queens[row]
                    columns[col] = back[col-row+n] = forward[col+row] = True
                col += 1

Runtime: 48 ms, faster than 98.01% of Python3 online submissions for N-Queens.

Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for N-Queens.

n皇后2

https://leetcode.com/problems/n-queens-ii/discuss/126533/Python-Backtracking-Solution-(Beats-97)

class Solution:
    def totalNQueens(self, n: int) -> int:
        diag1 = set()
        diag2 = set()
        usedCols = set()

        return self.helper(n, diag1, diag2, usedCols, 0)

    def helper(self, n, diag1, diag2, usedCols, row):
        if row == n:
            return 1

        solutions = 0

        for col in range(n):
            if row + col in diag1 or row - col in diag2 or col in usedCols:
                continue

            diag1.add(row + col)
            diag2.add(row - col)
            usedCols.add(col)

            solutions += self.helper(n, diag1, diag2, usedCols, row + 1)

            diag1.remove(row + col)
            diag2.remove(row - col)
            usedCols.remove(col)

        return solutions

Runtime: 48 ms, faster than 87.61% of Python3 online submissions for N-Queens II.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for N-Queens II.

看不懂的位运算

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.res = 0

        def dfs(row, col, ld, rd):
            if row >= n:
                self.res += 1
                return
            bits = ~(col | ld | rd) & ((1 << n)-1)
            while bits > 0:
                pick = bits & -bits
                dfs(row+1, col | pick, (ld | pick) << 1, (rd | pick) >> 1)
                bits &= bits-1

        dfs(0, 0, 0, 0)
        return self.res

Runtime: 32 ms, faster than 99.09% of Python3 online submissions for N-Queens II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for N-Queens II.