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]);//注意不能直接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; };
