📑 题目：51. N 皇后

🚀 本题 LeetCode 传送门

题目大意

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

解题思路

  • 求解 n 皇后问题
  • 利用 col 数组记录列信息，col 有 n 列。用 dia1，dia2 记录从左下到右上的对角线，从左上到右下的对角线的信息，dia1 和 dia2 分别都有 2*n-1 个。
  • dia1 对角线的规律是 i + j 是定值，例如[0,0]，为 0；[1,0]、[0,1] 为 1；[2,0]、[1,1]、[0,2] 为 2；
  • dia2 对角线的规律是 i - j 是定值，例如[0,7]，为 -7；[0,6]、[1,7] 为 -6；[0,5]、[1,6]、[2,7] 为 -5；为了使他们从 0 开始，i - j + n - 1 偏移到 0 开始，所以 dia2 的规律是 i - j + n - 1 为定值。
  • 还有一个位运算的方法，每行只能选一个位置放皇后，那么对每行遍历可能放皇后的位置。如何高效判断哪些点不能放皇后呢？这里的做法毕竟巧妙，把所有之前选过的点按照顺序存下来，然后根据之前选的点到当前行的距离，就可以快速判断是不是会有冲突。举个例子: 假如在 4 皇后问题中，如果第一二行已经选择了位置 [1, 3]，那么在第三行选择时，首先不能再选 1, 3 列了，而对于第三行， 1 距离长度为2，所以它会影响到 -1, 3 两个列。同理，3 在第二行，距离第三行为 1，所以 3 会影响到列 2, 4。由上面的结果，我们知道 -1, 4 超出边界了不用去管，别的不能选的点是 1, 2, 3，所以第三行就只能选 0。在代码实现中，可以在每次遍历前根据之前选择的情况生成一个 occupied 用来记录当前这一行，已经被选了的和由于之前皇后攻击范围所以不能选的位置，然后只选择合法的位置进入到下一层递归。另外就是预处理了一个皇后放不同位置的字符串，这样这些字符串在返回结果的时候是可以在内存中复用的，省一点内存。

代码

  1. package leetcode
  3. // 解法一 DFS
  4. func solveNQueens(n int) [][]string {
  5.  col, dia1, dia2, row, res := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, [][]string{}
  6.  putQueen(n, 0, &col, &dia1, &dia2, &row, &res)
  7.  return res
  8. }
  10. // 尝试在一个n皇后问题中, 摆放第index行的皇后位置
  11. func putQueen(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *[][]string) {
  12.  if index == n {
  13.   *res = append(*res, generateBoard(n, row))
  14.   return
  15.  }
  16.  for i := 0; i < n; i++ {
  17.   // 尝试将第index行的皇后摆放在第i列
  18.   if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] {
  19.    *row = append(*row, i)
  20.    (*col)[i] = true
  21.    (*dia1)[index+i] = true
  22.    (*dia2)[index-i+n-1] = true
  23.    putQueen(n, index+1, col, dia1, dia2, row, res)
  24.    (*col)[i] = false
  25.    (*dia1)[index+i] = false
  26.    (*dia2)[index-i+n-1] = false
  27.    *row = (*row)[:len(*row)-1]
  28.   }
  29.  }
  30.  return
  31. }
  33. func generateBoard(n int, row *[]int) []string {
  34.  board := []string{}
  35.  res := ""
  36.  for i := 0; i < n; i++ {
  37.   res += "."
  38.  }
  39.  for i := 0; i < n; i++ {
  40.   board = append(board, res)
  41.  }
  42.  for i := 0; i < n; i++ {
  43.   tmp := []byte(board[i])
  44.   tmp[(*row)[i]] = 'Q'
  45.   board[i] = string(tmp)
  46.  }
  47.  return board
  48. }
  50. // 解法二 二进制操作法 Signed-off-by: Hanlin Shi shihanlin9@gmail.com
  51. func solveNQueens2(n int) (res [][]string) {
  52.  placements := make([]string, n)
  53.  for i := range placements {
  54.   buf := make([]byte, n)
  55.   for j := range placements {
  56.    if i == j {
  57.     buf[j] = 'Q'
  58.    } else {
  59.     buf[j] = '.'
  60.    }
  61.   }
  62.   placements[i] = string(buf)
  63.  }
  64.  var construct func(prev []int)
  65.  construct = func(prev []int) {
  66.   if len(prev) == n {
  67.    plan := make([]string, n)
  68.    for i := 0; i < n; i++ {
  69.     plan[i] = placements[prev[i]]
  70.    }
  71.    res = append(res, plan)
  72.    return
  73.   }
  74.   occupied := 0
  75.   for i := range prev {
  76.    dist := len(prev) - i
  77.    bit := 1 << prev[i]
  78.    occupied |= bit | bit<<dist | bit>>dist
  79.   }
  80.   prev = append(prev, -1)
  81.   for i := 0; i < n; i++ {
  82.    if (occupied>>i)&1 != 0 {
  83.     continue
  84.    }
  85.    prev[len(prev)-1] = i
  86.    construct(prev)
  87.   }
  88.  }
  89.  construct(make([]int, 0, n))
  90.  return
  91. }