一天一大 lee(N 皇后)难度:困难-Day20200903
程序员文章站
2022-05-08 14:27:35
...
题目:
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
输入:4
输出:[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示:
- 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
抛砖引玉
翻一下题目的意思:
出入 N,要在长宽为 N 的矩阵中放入 N 个 Q,且每个 Q 不能处在同行同列也不能处在对角线上
思路
第一下看示例的输出其实有点不符合直觉,第一反应应该是从第一位开始放 Q:
Q | . | . | . |
---|---|---|---|
. | . | Q | . |
. | . | . | . |
. | . | . | . |
[0,2] -> [ [0,0],[1,2] ]
这个时候就知道为什么输出不是从开始就放 Q,因为如果在某些位置放置了 Q,后续可能不能放下 n 个 Q
那么此时就有两种方式开启行的枚举:
- 回溯到开始从新枚举
- 就当前位回溯开始新的枚举
如果采用第 1 种方式回溯,可能在当前起始填充位下存在正确的解法,直接切换了起始位就会造成解法丢失,则采用的第 2 种方法回溯
回溯第二个 Q,给其重新放置位置
Q | . | . | . |
---|---|---|---|
. | . | . | Q |
. | Q | . | . |
. | . | . | . |
[0,3,1] -> [ [0,0],[1,3],[2,1] ]
还是放置不下 4 个 Q,说明枚举了第二个 Q 的位置还是不能满足条件,次数枚举了 Q 起始位置为[0,0]的组合,确定起始位置为[0,0]不存在正解
继续向后枚举起始位置
. | Q | . | . |
---|---|---|---|
. | . | . | Q |
Q | . | . | . |
. | . | Q | . |
[1,3,0,2] -> [ [0,1],[1,3],[2,0],[3,2] ]
得到一种解法,记录下拉继续枚举…
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {
let _result = Array.from({length:n,()=>Array(n).fill('.')}),
tmp = [];
dfs(tmp)
function dfs(tmp) {
if (tmp.length === n) {
for (let i = 0; i < n; i++) {
const s = Array(n).fill('.').splice(tmp[i], 1, 'Q').join('')
_result.push(s)
}
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 || x - y === x - Ny || x + y === x + Ny) {
return false
}
}
return true
}
return _result
}
注:斜对角判断
a | * | b |
---|---|---|
* | A | * |
c | * | d |
元素 A ->[1,1]的斜对角有:
- a->[0,0]
- b->[2,0]
- c->[0,2]
- d->[2,2]
坐标[x,y]的斜对角坐标[i,j]都满足 x-y=== i-j 或者 x+y===i+j
博客: 小书童博客
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言
公号: 坑人的小书童
推荐阅读
-
一天一大 lee(解数独)难度:困难-Day20200915
-
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
-
一天一大 lee(冗余连接 II)难度:困难-Day20200917
-
【一天一大 lee】最大间距 (难度:困难) - Day20201126
-
一天一大 lee(N 皇后)难度:困难-Day20200903
-
【一天一大 lee】N皇后 II (难度:困难) - Day20201017
-
【一天一大 lee】插入区间 (难度:困难) - Day20201104
-
一天一大 lee(24点游戏)难度:困难-Day20200822
-
一天一大 lee(回文对)难度:困难-Day20200806
-
一天一大 lee(最短回文串)难度:困难-Day20200829