ZOJ 1457 / HDU 1016 Prime Ring Problem：DFS + 剪枝全排列構造

問題重述

將 1..n (n<20, n 為偶數) 填入環狀 n 個圓圈，相鄰兩數之和為質數，且 1 固定在第一位。按字典序輸出所有合法環（順時針+逆時針視為不同）。

核心觀察

• n 為奇數時無解（奇偶數交替相加為奇數，質數除 2 外皆奇，環長奇數無法交替）。
• 質數範圍：2..2n，最大 38，預計算質數表 O(1) 判斷。
• DFS 逐位填入，剪枝條件：新數未用 且 與前一數和為質數。
• 填滿 n 位後，額外檢查最後一數與 1 的和是否為質數。

DFS 遞歸框架

void dfs(int pos) {           // pos: 當前要填的位置 (1-based)
    if (pos == n) {           // 已填滿 n-1 個位置（0 固定為 1）
        if (isPrime[ring[n-1] + 1]) output();
        return;
    }
    for (int v = 2; v <= n; ++v) {
        if (!used[v] && isPrime[ring[pos-1] + v]) {
            used[v] = true;
            ring[pos] = v;
            dfs(pos + 1);
            used[v] = false;  // 回溯復原
        }
    }
}

關鍵優化細節

1. 質數表預計算：bool isPrime[40] = {0}; 手動標記 {2,3,5,7,11,13,17,19,23,29,31,37}。
2. 字典序天然保證：外層循環 v=2..n 遞增，DFS 先深後淺，輸出順序即字典序。
3. 剪枝前置：if (!used[v] && isPrime[...]) 合併判斷，減少分支。
4. 回溯復原：used[v]=false 必須在遞歸返回後執行，否則污染同層其他分支。

完整 C++ 代碼（ZOJ/HDU 通用）

#include 
using namespace std;

int n, caseNo = 0;
int ring[20];
bool used[20];
bool isPrime[40] = {0};

void initPrime() {
    vector primes = {2,3,5,7,11,13,17,19,23,29,31,37};
    for(int p: primes) isPrime[p] = true;
}

void dfs(int pos) {
    if (pos == n) {
        if (isPrime[ring[n-1] + 1]) {
            for(int i=0;i> n) {
        cout << "Case " << ++caseNo << ":\n";
        if (n % 2 == 1) { cout << '\n'; continue; }
        fill(used, used+n+1, false);
        ring[0] = 1; used[1] = true;
        dfs(1);
        cout << '\n';
    }
    return 0;
}

複雜度分析

• 搜索空間：(n-1)!，但質數約束極強，實際訪問節點極少。
• n=16 時解約 81024 個，運行 < 0.1s。

常見錯誤

• 忘記判斷 n%2==1 直接輸出空行。
• 末尾未檢查 ring[n-1]+1 是質數。
• 回溯未復原 used[] 導致漏解/重解。
• 輸出格式：每行數字間單空格，行尾無空格，Case 之間空行。

延伸：HDU 1016 差異

HDU 1016 允許 n 為奇數（輸出空行），且測試數據較弱，同代碼雙 AC。