20201017
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
N 皇后 II
给定一个整数 n,返回 n 皇后不同的解决方案的数量。
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
类似的题目之前做过N 皇后,两题的逻辑一致,只是返回值要求不同,本题只要求返回结果数量
抛砖引玉
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
let _result = 0,
tmp = []
dfs(tmp)
function dfs(tmp) {
if (tmp.length === n) {
_result++
return
}
for (let i = 0; i < n; i++) {
if (isValid(tmp, i)) {
// 遇到满足“不能相互攻击”的点就先占着后继续安放下一个Q
tmp.push(i)
dfs(tmp)
// 回溯已经安放的Q
tmp.pop()
}
}
}
// 判断新的位置是否满足“不能相互攻击”
function isValid(tmp, Ny) {
// 传入校验的坐标:[Nx,Ny]
let Nx = tmp.length
for (let x = 0; x < Nx; x++) {
let y = tmp[x]
// 不同列,因为所有做行一定不同行,不在斜对角上[注:斜对角判断]
if (y === Ny || Nx - y === x - Ny || Nx + y === x + Ny) {
return false
}
}
return true
}
return _result
}
博客: 前端小书童
公众号:前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言