题目描述补充

n皇后问题 II：给定一个整数n，返回n皇后问题中不同的解决方案的数量。n皇后问题的目的是在n×n的棋盘上放置n个皇后，使得它们互不攻击。两个皇后互相攻击当且仅当：

• 它们处于同一行；
• 它们处于同一列；
• 它们处于同一条对角线上。

示例

输入: n = 4 输出: 2 解释: 存在两种不同的解法：

. Q . .
. . . Q
Q . . .
. . Q .

和

. . Q .
Q . . .
. . . Q
. Q . .

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; // 同列有皇后
        if ($board[$row - $i - 1][$col - $i - 1] == 'Q') return false; // 左上方对角线有皇后
        if ($board[$row - $i - 1][$col + $i + 1] == 'Q') return false; // 右上方对角线有皇后
    }
    return true;
}

// 示例用法
echo totalNQueens(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
            if board[i][col - row + i] == 'Q' and col - row + i >= 0:
                return False
            if board[i][col + row - i] == 'Q' and col + row - i < n:
                return False
        return True

    board = [['.' for _ in range(n)] for _ in range(n)]
    count = [0]
    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

码小课网站中有更多关于算法和数据结构的相关内容分享，欢迎大家学习交流。