n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
51.N 皇后 - 图1

  1. 输入：n = 4
  2. 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  3. 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

  1. 输入：n = 1
  2. 输出：[["Q"]]

提示：

  • 1 <= n <= 9

解法一：回溯

  1. function solveNQueens(n: number): string[][] {
  2.   //
  3.   let res :Array<Array<number>> = []
  4.   let cols : Set<number> = new Set()
  5.   let pies : Set<number> = new Set()
  6.   let nas :Set<number> = new Set()
  9.   function  recursion(row: number, list:Array<number>) {
  10.     if (row === n) {
  11.       res.push([...list])
  12.       return
  13.     }
  15.     for(let col = 0 ; col < n; col ++) {
  16.       // 列、撇、捺 中是否存在
  17.       if (cols.has(col) || pies.has(row + col) || nas.has(row-col)) {
  18.         continue
  19.       }
  20.       cols.add(col)
  21.       pies.add(row+col)
  22.       nas.add(row - col)
  23.       list.push(col)
  24.       recursion(row + 1, list)
  26.       cols.delete(col)
  27.       pies.delete(row + col)
  28.       nas.delete(row - col)
  29.       list.pop()
  30.     }
  31.   }
  32.   recursion(0, [])
  33.   // console.log(res)
  35.   function  genStr(nums: Array<Array<number>>, n : number): Array<Array<string>> {
  36.     return nums.map(list => list.map(i => '.'.repeat(i) + "Q" + ".".repeat( n - i - 1)))
  37.   }
  38.   return genStr(res, n)
  40. };