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
0 1 2 3
0 . Q . .
1 . . . Q
2 Q . . .
3 . . Q .
关于斜对角线上的限制可以得出以下两条规律。
- 罗列从
右上到左下
斜线点发现规律:横坐标与纵坐标之和为定值
。
(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)
- 罗列从
左上到右下
斜线点发现规律:横坐标与纵坐标之差为定值
。
(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()
}
}