LeetCode 51.N皇后
一、题目
1、问题描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
2、示例
输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],
["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ]
3、提示
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
二、分析
该题为回溯算法的一道经典题目，解题思路如下。
1、构建空棋盘
for(let i
= 0; i
< n
; i
++){
t
.push(0);
}
for(let i
= 0; i
< n
; i
++){
temp
.push([...t
]);
}
2、判断当前位置能否摆放
主要是在斜线上的判断，需要沿四个方向扩展出去。
//判断能否摆放
var judge = function(i,j,n){
//横
for(let k = 0;k < n; k++){
if(temp[i][k] == 1) return 0;
}
//竖
for(let k = 0;k < n; k++){
if(temp[k][j] == 1) return 0;
}
//斜
for(let k = 1; k + j < n && i - k >= 0; k++){
if(temp[i - k][j + k] == 1) return 0;
}
for(let k = 1; k + i < n && j - k >= 0; k++){
if(temp[i + k][j - k] == 1) return 0;
}
for(let k = 1; k + i < n && j + k < n; k++){
if(temp[i + k][j + k] == 1) return 0;
}
for(let k = 1; i - k >= 0 && j - k >= 0; k++){
if(temp[i - k][j - k] == 1) return 0;
}
return 1;
}
3、深搜回溯
//深搜遍历
var dfs = function(e,n){
//遍历当前行的每一列
for(let i = 0;i < n; i++){
//判断能否摆放
if(temp[e][i] == 0 && judge(e,i,n)){
//标记当前位置已摆放
temp[e][i] = 1;
//已经摆置n个皇后
if(e == n-1){
var ans = [];
for(let i1 = 0; i1 < n; i1++){
var a = "";
for(let i2 = 0; i2 < n; i2++){
//格式化输出
if(temp[i1][i2] == 0) a += ".";
else a += "Q";
}
ans.push(a);
}
//将当前结果放进列表
res.push(ans);
}else{
//没够n个，继续往下遍历
dfs(e+1,n);
}
}
//回溯，取消标记
temp[e][i] = 0;
}
}
三、代码
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
var t = [],
temp = [],
res = [];
for(let i = 0; i < n; i++){
t.push(0);
}
for(let i = 0; i < n; i++){
temp.push([...t]);
}
//判断能否摆放
var judge = function(i,j,n){
//横
for(let k = 0;k < n; k++){
if(temp[i][k] == 1) return 0;
}
//竖
for(let k = 0;k < n; k++){
if(temp[k][j] == 1) return 0;
}
//斜
for(let k = 1; k + j < n && i - k >= 0; k++){
if(temp[i - k][j + k] == 1) return 0;
}
for(let k = 1; k + i < n && j - k >= 0; k++){
if(temp[i + k][j - k] == 1) return 0;
}
for(let k = 1; k + i < n && j + k < n; k++){
if(temp[i + k][j + k] == 1) return 0;
}
for(let k = 1; i - k >= 0 && j - k >= 0; k++){
if(temp[i - k][j - k] == 1) return 0;
}
return 1;
}
//深搜遍历
var dfs = function(e,n){
for(let i = 0;i < n; i++){
if(temp[e][i] == 0 && judge(e,i,n)){
temp[e][i] = 1;
if(e == n-1){
var ans = [];
for(let i1 = 0; i1 < n; i1++){
var a = "";
for(let i2 = 0; i2 < n; i2++){
if(temp[i1][i2] == 0) a += ".";
else a += "Q";
}
ans.push(a);
}
res.push(ans);
}else{
dfs(e+1,n);
}
}
temp[e][i] = 0;
}
}
dfs(0,n);
return res;
};
四、个人博客
个人博客地址
