原文:51. N皇后(x, n)(力扣 面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-051/

题目:

难度: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能攻击到的范围,分别是coldia1dia2(竖线和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
    }
  }
};