题目描述补充

n皇后问题是一个经典的回溯算法问题。在n×n的棋盘上要摆放n个皇后，使得它们互不攻击。即任何两个皇后都不能处于同一行、同一列或同一斜线上。现在，我们需要编写一个函数来解决n皇后问题，并返回所有可能的解决方案的数量。

示例代码

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 示例

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 示例

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皇后问题及其他算法相关内容的分享和学习资源，欢迎访问码小课网站深入探索和学习。