题目描述

N 皇后 II 是 N 皇后问题的一个变种，该问题是国际象棋中的一个经典问题。在 N×N 的棋盘上要摆放 N 个皇后，使得它们互不攻击。皇后能攻击同一行、同一列或同一对角线上的其他皇后。给定一个整数 N，返回在 N×N 棋盘上摆放 N 个皇后的不同解决方案的数量。

示例

• 输入: 4
• 输出: 2
  • 解决方案示例:

    [
      [".Q..", "...Q", "Q...", "..Q."],
      ["..Q.", "Q...", "...Q", ".Q.."]
    ]
    

    注意：这里的输出仅为了说明问题，而实际题目要求返回的是解决方案的数量，即 2。

PHP 示例代码

<?php

function solveNQueens($n) {
    $result = 0;
    $board = array_fill(0, $n, str_repeat('.', $n));
    backtrack($board, 0, $n, $result);
    return $result;
}

function backtrack(&$board, $row, $n, &$result) {
    if ($row == $n) {
        $result++;
        return;
    }

    for ($col = 0; $col < $n; $col++) {
        if (isValid($board, $row, $col, $n)) {
            $board[$row][$col] = 'Q';
            backtrack($board, $row + 1, $n, $result);
            $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 solveNQueens(4);  // 输出 2
?>

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

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 个皇后的不同解决方案的数量。