### 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4Output: 2Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
. Q . .            . . Q .. . . Q     or     Q . . .Q . . .            . . . Q. . Q .            . Q . .

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Example 2:

Input: n = 1Output: 1
• Constraints:
• 1 <= n <= 9

### Analyze

0   1   2   30   .   Q   .   .
1   .   .   .   Q
2   Q   .   .   .
3   .   .   Q   .

1. 罗列从右上到左下斜线点发现规律: 横坐标与纵坐标之和为定值
• (0, 0)
• (0, 1)、(1, 0)
• (0, 2)、(1, 1)、(2, 0)
• (0, 3)、(1, 2)、(2, 1)、(3, 0)
• (1, 3)、(2, 2)、(3, 1)
• (2, 3)、(3, 2)
• (3, 3)
1. 罗列从左上到右下斜线点发现规律: 横坐标与纵坐标之差为定值
• (3, 0)
• (2, 0)、(3, 1)
• (1, 0)、(2, 1)、(3, 2)
• (0, 0)、(1, 1)、(2, 2)、(3, 3)
• (0, 1)、(1, 2)、(2, 3)
• (0, 2)、(1, 3)
• (0, 3)
/** * @param {number} n * @return {number} */var totalNQueens = function(n) {  const result = []  const limit = {    used: [],    x: [],    y: [],    sum: [],    diff: []  }  handleNQueens(n, 0, limit, result)  return result.length};
// eg: when n is 4, arr is [["0,1", "1,3", "2,0", "3,2"], ["0,2", "1,0", "2,3", "3,1"]]var generate = (arr) => {  const xArr = []  for (let x = 0; x < arr.length; x++) {    const [queueX, queueY] = arr[x].split(',')    let yStr = ''    for (let y = 0; y < arr.length; y++) {      if (x === Number(queueX) && y === Number(queueY)) {        yStr = yStr + 'Q'      } else {        yStr = yStr + '.'      }    }    xArr.push(yStr)  }  return xArr}
// handle the position with the index row from n Queue.var handleNQueens = (n, index, limit, result) => {  if (limit.x.length === n) {    result.push(generate([...limit.used]))    return  }
// 第 index 行安置在第几列中  for (let y = 0; y < n; y++) {    const sum = index + y    const diff = index - y    if (      limit.used.indexOf(${index},${y}) > -1      || limit.x.indexOf(index) > -1      || limit.y.indexOf(y) > -1      || limit.sum.indexOf(sum) > -1      || limit.diff.indexOf(diff) > -1    ) {      continue    }    limit.used.push(${index},${y})    limit.x.push(index)    limit.y.push(y)    limit.sum.push(sum)    limit.diff.push(diff)
handleNQueens(n, index + 1, limit, result)    limit.used.pop()    limit.x.pop()    limit.y.pop()    limit.sum.pop()    limit.diff.pop()  }}