POJ 3239 N 皇後問題：構造法 O(1) 輸出解

問題描述

在 n×n 棋盤上放置 n 個皇後，使任意兩個皇後不在同行、同列、同對角線。輸出任意一組解（列號表示行位置）。n ∈ [8, 300]，多測試用例。

數學構造規律

N 皇後問題在 n ≥ 4 時總有解。根據 n mod 6 分類構造：

情況一：n mod 6 ≠ 2 且 n mod 6 ≠ 3

• n 偶數：先輸出所有偶數列 2,4,...,n，再輸出所有奇數列 1,3,...,n-1
• n 奇數：先輸出偶數列 2,4,...,n-1，再輸出奇數列 1,3,...,n

情況二：n mod 6 = 2 或 n mod 6 = 3

設 k = n/2（n 偶）或 k = (n-1)/2（n 奇）。根據 k 奇偶分四種子情況，構造四段序列拼接：

// 以 n mod 6 = 2, n 偶, k 偶為例
[k, k+2, ..., n], [2, 4, ..., k-2], [k+3, k+5, ..., n-1], [1, 3, ..., k+1]

完整分支見代碼。

構造代碼（C++）

#include 
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        if (n % 6 != 2 && n % 6 != 3) {
            if (n % 2 == 0) { // 偶數
                for (int i = 2; i <= n; i += 2) cout << i << ' ';
                for (int i = 1; i <= n-1; i += 2) cout << i << ' ';
            } else { // 奇數
                for (int i = 2; i <= n-1; i += 2) cout << i << ' ';
                for (int i = 1; i <= n; i += 2) cout << i << ' ';
            }
        } else {
            if (n % 2 == 0) { // n 偶數
                int k = n / 2;
                if (k % 2 == 0) { // k 偶數
                    for (int i = k; i <= n; i += 2) cout << i << ' ';
                    for (int i = 2; i <= k-2; i += 2) cout << i << ' ';
                    for (int i = k+3; i <= n-1; i += 2) cout << i << ' ';
                    for (int i = 1; i <= k+1; i += 2) cout << i << ' ';
                } else { // k 奇數
                    for (int i = k; i <= n-1; i += 2) cout << i << ' ';
                    for (int i = 1; i <= k-2; i += 2) cout << i << ' ';
                    for (int i = k+3; i <= n; i += 2) cout << i << ' ';
                    for (int i = 2; i <= k+1; i += 2) cout << i << ' ';
                }
            } else { // n 奇數
                int k = (n - 1) / 2;
                if (k % 2 == 0) { // k 偶數
                    for (int i = k; i <= n-1; i += 2) cout << i << ' ';
                    for (int i = 2; i <= k-2; i += 2) cout << i << ' ';
                    for (int i = k+3; i <= n-2; i += 2) cout << i << ' ';
                    for (int i = 1; i <= k+1; i += 2) cout << i << ' ';
                    cout << n;
                } else { // k 奇數
                    for (int i = k; i <= n-2; i += 2) cout << i << ' ';
                    for (int i = 1; i <= k-2; i += 2) cout << i << ' ';
                    for (int i = k+3; i <= n-1; i += 2) cout << i << ' ';
                    for (int i = 2; i <= k+1; i += 2) cout << i << ' ';
                    cout << n;
                }
            }
        }
        cout << endl;
    }
    return 0;
}

算法優勢

• 時間複雜度 O(n)，無需回溯搜索
• 空間複雜度 O(1)
• 適用於大規模 n（本題 n ≤ 300 綽綽有餘）

數學背景

此構造法基於 Pauls (1874) 和 Ahrens (1910) 的數學證明，利用模 6 同餘類將棋盤分解為可安全放置皇後的模式。所有 n ≥ 4 除 n=2,3 外均有解，本題 n ≥ 8 保證有解。

避坑指南

• 輸出格式：每行一組解，數字間單空格，行末無多餘空格
• n=0 結束輸入
• Special Judge 允許任意合法解
• 注意奇數 n 時最後單獨輸出 n 的情況

此題展示了數學構造法在組合優化問題中的驚人威力，將 NP-hard 問題（一般情況）在特定約束下轉化為 O(1) 輸出。