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