AcWing 843. n-皇后问题
原题链接
中等
作者:
Snjjsvsand
,
2022-12-02 10:12:37
,
所有人可见
,
阅读 213
DFS 排列型枚举 O(n!)
很好的题解,图解了对角线计算方法
立扣链接
JavaScript 代码
var solveNQueens = function(n) {
let g = new Array(n).fill('').map(e => new Array(n).fill('.'))
let col = new Array(n).fill(false) , dg = new Array(n).fill(false) , udg = new Array(n).fill(false)
let res = []
function dfs(x) {
if(x >= n) return res.push(g.map(row => row.join('')))
for(let y = 0; y < n; y++) {
if(!col[y] && !dg[y - x + n] && !udg[y + x]) {
g[x][y] = 'Q'
col[y] = true , dg[y - x + n] = true , udg[y + x] = true
dfs(x + 1)
g[x][y] = '.'
col[y] = false , dg[y - x + n] = false , udg[y + x] = false
}
}
}
dfs(0)
return res
};