按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

思路

  1. 递归持续放置合法项进而得出可行解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var solveNQueens = function (n) {
  const result = []
  const handler = (curIndex, prevItems) => {
    if (curIndex === n) {
      result.push(prevItems)
      return
    }
    for (let j = 0; j < n; ++j) {
      let available = true
      for (let i = 0; i < prevItems.length; ++i) {
        const prevItem = prevItems[i]
        const gap = curIndex - i
        if (prevItem[j] === 'Q' || prevItem[j - gap] === 'Q' || prevItem[j + gap] === 'Q') {
          available = false
          break
        }
      }
      if (available) {
        const chars = new Array(n).fill('.')
        chars[j] = 'Q'
        handler(curIndex + 1, [...prevItems, chars.join('')])
      }
    }
  }
  handler(0, [])
  return result
}