题目描述:
难度:Hard
相关话题:回溯算法
n 皇后问题研究的是如何将 n 个皇后放置在 n ×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n ,返回所有不同的n 皇后问题的解决方案。
每一种解法包含一个明确的n 皇后问题的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
思路:
经典的回溯问题,主要思想就是不断尝试每一行每一个位置能否放置Q
。
定义3个hash
,用来保存已经放置的Q
能攻击到的范围,分别是col
,dia1
,dia2
(竖线和2对角线)
并且定义一个board
来记录每个Q
放置的位置,因为最终输出需要输出整个棋盘位置。
由于每一行最多只可能存在一个Q
,那么如果第i
行放置了,那么就继续第i+1
行,检查是否有位置能放置。
检查的过程有一个高效的方法,col
很简单,关键在两条斜线,可以思考这两条斜线的延长线最终到达第一行的位置。
左下到右上斜线[i,j]
延长线最终能到达第一行的位置就是[0,j+i]
,因此只需要保存j+i
;
左上到右下的斜线[i,j]
延长线最终能到达第一行的位置就是[0,j-i]
,因此只需要保存j-i
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
let dia1=Array(2*n).fill(false),
dia2=Array(2*n).fill(false),
col=Array(n).fill(false)
let board=Array(n).fill().map(()=>Array(n).fill('.'))
let res=[]
backtrack(board,0,0)
return res
function backtrack(board,setCount,rowId){
if(setCount===n){
let ans=[]
for(let i=0;i<n;i++){
ans.push(board[i].join(''))
}
res.push(ans)
}
for(let j=0;j<n;j++){
let lt2rd=j-rowId+n,rt2ld=j+rowId
// 检查竖线,两斜线是否冲突
if(col[j] || dia1[lt2rd] || dia2[rt2ld])continue
col[j]=true
dia1[lt2rd]=true
dia2[rt2ld]=true
board[rowId][j]="Q"
backtrack(board,setCount+1,rowId+1)
board[rowId][j]="."
dia2[rt2ld]=false
dia1[lt2rd]=false
col[j]=false
}
}
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com