原题地址：N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
回溯算法
这是回溯算法的一个典型应用。在国际象棋中皇后的攻击范围是所在的直线和对角线，所以本题实际上是要求将 n 个皇后放置在 n×n 的棋盘上，并且使所有的皇后相互之间都不能在同一条直线和对角线上。
所以我们求解的过程就是依次放皇后，每次都任选一个有效的位置放置，当发现某一步的皇后没有位置可放时就说明这个方案是失败的，此时就回退选择其它方案，直到 n 个皇后都放到了棋盘上，就证明找到了有效的方案。
具体的实现方式如下：
/**
* @param {number} n
* @return {string[][]}
*/
const solveNQueens1 = function(n) {
// 记录皇后的位置，下标为行，值为列
let queen = new Array(n).fill(-1);
let result = [];
/**
* 判断新的皇后放在某一行是不是有效的
* @param row 行数
* @returns {boolean} 是否合法
*/
const isOk = (row) => {
// 依次判断已经放置的皇后是否在同一列或同一对角线上
for (let i = 0; i < row; i ++) {
if (queen[i] === queen[row] || // 同一列有两个皇后
row - queen[row] === i - queen[i] || row + queen[row] === i + queen[i]) { // 对角线
return false;
}
}
return true;
};
/**
* 放置某一行的皇后
* @param row 行号
*/
const placeQueen = (row) => {
// n个皇后已经放置完毕，方案可行，将该方案加入结果集
if (row === n) {
result.push([...queen]);
} else {
// 依次尝试放皇后放在每一列，判断该方案是否OK，如果OK就继续放置下一行
// 否则证明该方案不可行，剪枝
for (let column = 0; column < n; column ++) {
queen[row] = column;
if (isOk(row)) {
placeQueen(row + 1);
}
}
}
};
// 从第一行开始放置皇后
placeQueen(0);
// 需要将结果转换成题目要求的方式
return result.map(item => {
let array = new Array(n);
for (let i = 0; i < n; i ++) {
let str = '';
for (let j = 0; j < n; j ++) {
str += item[i] === j ? 'Q' : '.'
}
array[i] = str;
}
return array;
});
};
测试：
let start = new Date();
const test = solveNQueens1;
/**
[
[ '.Q..', '...Q', 'Q...', '..Q.' ],
[ '..Q.', 'Q...', '...Q', '.Q..' ]
]
*/
console.log(test(4));
/**
[
[ 'Q....', '..Q..', '....Q', '.Q...', '...Q.' ],
[ 'Q....', '...Q.', '.Q...', '....Q', '..Q..' ],
[ '.Q...', '...Q.', 'Q....', '..Q..', '....Q' ],
[ '.Q...', '....Q', '..Q..', 'Q....', '...Q.' ],
[ '..Q..', 'Q....', '...Q.', '.Q...', '....Q' ],
[ '..Q..', '....Q', '.Q...', '...Q.', 'Q....' ],
[ '...Q.', 'Q....', '..Q..', '....Q', '.Q...' ],
[ '...Q.', '.Q...', '....Q', '..Q..', 'Q....' ],
[ '....Q', '.Q...', '...Q.', 'Q....', '..Q..' ],
[ '....Q', '..Q..', 'Q....', '...Q.', '.Q...' ]
]
*/
console.log(test(5));
console.log(new Date().getTime() - start.getTime()); // 11
时间复杂度： 放置第一个皇后有n种方式，放置第二个皇后不超过n-1种方式，……，放置第m个皇后不超过n-m+1种方式，所以总的时间复杂度为$O(n!)$
空间复杂度： 递归的栈不超过n，空间复杂度为$O(n)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 6,2019