PHP 實現 N 皇后問題：回溯算法完整解析與代碼實戰

問題描述

N 皇后問題：在 N×N 的棋盤上放置 N 個皇后，使其互不攻擊（同行、同列、同對角線最多一個皇后）。求所有合法擺放方案數。經典回溯算法入門案例。

回溯算法核心思想

• 狀態空間樹：每一行擺放一個皇后，第 k 層節點表示前 k 行的擺放選擇。
• 深度優先搜索 (DFS)：從第 0 行開始，逐行嘗試每一列。
• 剪枝：當前行選定列後，檢查是否與前面行衝突（同列、同對角線），衝突則跳過該分支。
• 回溯：某行無合法列位置，退回上一行換列繼續。

衝突檢測邏輯

假設已放置皇后位置存於數組 $queens，索引為行號，值為列號。檢查第 $row 行第 $col 列是否合法：

function isSafe($queens, $row, $col) {
    foreach ($queens as $r => $c) {
        // 同列
        if ($c == $col) return false;
        // 同主對角線（行差 = 列差）
        if (abs($row - $r) == abs($col - $c)) return false;
        // 同副對角線已包含在上式中（絕對值）
    }
    return true;
}

完整 PHP 實現（遞歸 + 全局狀態）

$n = 8;           // 棋盤大小
$solutions = [];  // 存儲所有解
$queens = [];     // 當前部分解：索引=行，值=列

function solveNQueens($row) {
    global $n, $solutions, $queens;

    if ($row === $n) {
        // 找到一個完整解，複製當前狀態
        $solutions[] = $queens;
        return;
    }

    for ($col = 0; $col < $n; $col++) {
        if (isSafe($queens, $row, $col)) {
            $queens[$row] = $col;      // 做選擇
            solveNQueens($row + 1);    // 遞歸下一行
            unset($queens[$row]);      // 撤銷選擇（回溯）
        }
    }
}

// 執行
$start = microtime(true);
solveNQueens(0);
$time = microtime(true) - $start;

echo "N=$n 共有 " . count($solutions) . " 種解法\n";
echo "耗時: " . round($time * 1000, 2) . " ms\n";

// 可選：打印前幾個解的棋盤圖
foreach (array_slice($solutions, 0, 3) as $idx => $sol) {
    echo "\n解法 #" . ($idx + 1) . ":\n";
    for ($r = 0; $r < $n; $r++) {
        $line = '';
        for ($c = 0; $c < $n; $c++) {
            $line .= ($sol[$r] == $c) ? '♛ ' : '· ';
        }
        echo $line . "\n";
    }
}

性能優化方向

位運算版核心邏輯（參考）

function solveBit($n, $row, $cols, $diag1, $diag2, &$count) {
    if ($row === $n) { $count++; return; }
    // 可用位置 = ~(cols | diag1 | diag2) & ((1<<$n)-1)
    $available = ~($cols | $diag1 | $diag2) & ((1 << $n) - 1);
    while ($available) {
        $pos = $available & -$available;  // 取最低位 1
        $available -= $pos;
        solveBit($n, $row + 1, $cols | $pos, ($diag1 | $pos) << 1, ($diag2 | $pos) >> 1, $count);
    }
}
$count = 0;
solveBit(8, 0, 0, 0, 0, $count);  // 8 皇后：92 解，毫秒級完成

時間測量注意事項

原文使用 microtime() 直接相減，但 microtime() 返回字符串 "秒 微秒"，直接相減會導致字符串轉換錯誤。正確做法：

$start = microtime(true);  // 直接返回浮點秒數
// ... 執行代碼 ...
$elapsed = microtime(true) - $start;  // 精確到微秒

總結

N 皇后是理解回溯、DFS、剪枝、狀態表示的絕佳案例。PHP 雖非高性能語言，但通過位運算優化也能在毫秒級解決 14 皇后（365,596 解）。實際項目中，若需大規模組合優化搜索，建議將核心算法下沉至 C/C++/Rust，PHP 負責業務協調。