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 all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

. 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 = 1
Output: [["Q"]]

• Constraints:
  • 1 <= n <= 9

Analyze

0   1   2   3
0   .   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)

2. 罗列从左上到右下斜线点发现规律: 横坐标与纵坐标之差为定值。

• (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 {string[][]}
 */
var solveNQueens = function(n) {
  const result = []
  const limit = {
    used: [],
    x: [],
    y: [],
    sum: [],
    diff: []
  }
  handleNQueens(n, 0, limit, result)
  return result
};

// 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()
  }
}