当前位置： 面试刷题>> n皇后问题Ⅰ (经典算法题500道)
### 题目描述补充
n皇后问题是一个经典的回溯算法问题。在n×n的棋盘上要摆放n个皇后，使得它们互不攻击。即任何两个皇后都不能处于同一行、同一列或同一斜线上。现在，我们需要编写一个函数来解决n皇后问题，并返回所有可能的解决方案的数量。
### 示例代码
#### PHP 示例
```php
function totalNQueens($n) {
$count = 0;
$board = array_fill(0, $n, array_fill(0, $n, '.'));
backtrack($board, 0, $n, $count);
return $count;
}
function backtrack(&$board, $row, $n, &$count) {
if ($row == $n) {
$count++;
return;
}
for ($col = 0; $col < $n; $col++) {
if (isValid($board, $row, $col, $n)) {
$board[$row][$col] = 'Q';
backtrack($board, $row + 1, $n, $count);
$board[$row][$col] = '.';
}
}
}
function isValid(&$board, $row, $col, $n) {
// 检查列
for ($i = 0; $i < $row; $i++) {
if ($board[$i][$col] == 'Q') {
return false;
}
}
// 检查左上方对角线
for ($i = $row - 1, $j = $col - 1; $i >= 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 totalNQueens(4); // 输出 2，表示 4 皇后问题有 2 种解决方案
```
#### Python 示例
```python
def totalNQueens(n):
def backtrack(board, row, count):
if row == n:
count[0] += 1
return
for col in range(n):
if is_valid(board, row, col):
board[row][col] = 'Q'
backtrack(board, row + 1, count)
board[row][col] = '.'
def is_valid(board, row, col):
for i in range(row):
if board[i][col] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 'Q':
return False
return True
count = [0]
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(board, 0, count)
return count[0]
# 示例用法
print(totalNQueens(4)) # 输出 2
```
#### JavaScript 示例
```javascript
function totalNQueens(n) {
let count = 0;
const board = Array.from({length: n}, () => Array(n).fill('.'));
function backtrack(row) {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
function isValid(row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
if (board[i][col - row + i] === 'Q' && col - row + i >= 0) return false;
if (board[i][col + row - i] === 'Q' && col + row - i < n) return false;
}
return true;
}
backtrack(0);
return count;
}
// 示例用法
console.log(totalNQueens(4)); // 输出 2
```
### 码小课提示
码小课网站中提供了更多关于回溯算法、n皇后问题及其他算法相关内容的分享和学习资源，欢迎访问码小课网站深入探索和学习。