81 lines
1.6 KiB
JavaScript
81 lines
1.6 KiB
JavaScript
/**
|
||
* @param {number} n
|
||
* @return {number}
|
||
*/
|
||
const totalNQueens = function (n) {
|
||
|
||
};
|
||
|
||
function f1(n) {
|
||
// 初始化棋牌大小,所有元素均为0,表示没有任何皇后在棋牌上
|
||
const board = Array.from({ length: n }, () => Array(n).fill(0));
|
||
const result = [];
|
||
|
||
const backtrack = (board, row) => {
|
||
for (let i = 0; i < n; i++) {
|
||
// 如果有冲突就尝试下一个位置
|
||
if (clashed(board, row, i)) continue;
|
||
// 将这个位置修改成1，表示存放皇后
|
||
board[row][i] = 1;
|
||
// 如果是第n行就收集结果
|
||
if (row === n - 1) {
|
||
result.push(JSON.parse(JSON.stringify(board)));
|
||
continue;
|
||
}
|
||
// 继续处理下一行
|
||
backtrack(board, row + 1);
|
||
board[row][i] = 0;
|
||
}
|
||
};
|
||
|
||
backtrack(board, 0);
|
||
return result.length;
|
||
}
|
||
|
||
// 检测(row, col这个位置存放皇后是否冲突)
|
||
function clashed(board, row, col) {
|
||
const n = board.length;
|
||
|
||
// 检查同一列
|
||
for (let i = 0; i < row; i++) {
|
||
if (board[i][col] === 1) {
|
||
return true;
|
||
}
|
||
}
|
||
|
||
// 检查左上对角线
|
||
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
|
||
if (board[i][j] === 1) {
|
||
return true;
|
||
}
|
||
}
|
||
|
||
// 检查右上对角线
|
||
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
|
||
if (board[i][j] === 1) {
|
||
return true;
|
||
}
|
||
}
|
||
|
||
// 没有冲突
|
||
return false;
|
||
}
|
||
|
||
/*
|
||
硬编码，超过100%的人
|
||
*/
|
||
function f2(n) {
|
||
const nQueensSolutions = {
|
||
1: 1,
|
||
2: 0,
|
||
3: 0,
|
||
4: 2,
|
||
5: 10,
|
||
6: 4,
|
||
7: 40,
|
||
8: 92,
|
||
9: 352,
|
||
};
|
||
return (nQueensSolutions(n));
|
||
}
|