当前位置： 面试刷题>> N 皇后 II(经典算法150题)
### 题目描述
**N 皇后 II** 是 N 皇后问题的一个变种，该问题是国际象棋中的一个经典问题。在 N×N 的棋盘上要摆放 N 个皇后，使得它们互不攻击。皇后能攻击同一行、同一列或同一对角线上的其他皇后。给定一个整数 N，返回在 N×N 棋盘上摆放 N 个皇后的不同解决方案的数量。
### 示例
- 输入: 4
- 输出: 2
- 解决方案示例:
```
[
[".Q..", "...Q", "Q...", "..Q."],
["..Q.", "Q...", "...Q", ".Q.."]
]
```
注意：这里的输出仅为了说明问题，而实际题目要求返回的是解决方案的数量，即 2。
### PHP 示例代码
```php
= 0 && $j >= 0; $i--, $j--) {
if ($board[$i][$j] == 'Q') {
return false;
}
}
// 检查右上对角线
for ($i = $row - 1, $j = $col + 1; $i >= 0 && $j < $n; $i--, $j++) {
if ($board[$i][$j] == 'Q') {
return false;
}
}
return true;
}
// 示例调用
echo solveNQueens(4); // 输出 2
?>
```
### Python 示例代码
```python
def solveNQueens(n):
def backtrack(row, cols, pie, na, count):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or row - col in pie or row + col in na:
continue
cols.add(col)
pie.add(row - col)
na.add(row + col)
backtrack(row + 1, cols, pie, na, count)
cols.remove(col)
pie.remove(row - col)
na.remove(row + col)
count = [0]
backtrack(0, set(), set(), set(), count)
return count[0]
# 示例调用
print(solveNQueens(4)) # 输出 2
```
### JavaScript 示例代码
```javascript
function solveNQueens(n) {
let count = 0;
function backtrack(row, cols, pie, na) {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || pie.has(row - col) || na.has(row + col)) {
continue;
}
cols.add(col);
pie.add(row - col);
na.add(row + col);
backtrack(row + 1, cols, pie, na);
cols.delete(col);
pie.delete(row - col);
na.delete(row + col);
}
}
const cols = new Set();
const pie = new Set(); // 主对角线
const na = new Set(); // 副对角线
backtrack(0, cols, pie, na);
return count;
}
// 示例调用
console.log(solveNQueens(4)); // 输出 2
```
以上代码分别用 PHP、Python 和 JavaScript 实现了 N 皇后 II 问题的解决方案，通过回溯算法计算出了在 N×N 棋盘上摆放 N 个皇后的不同解决方案的数量。