HDU 1016 Prime Ring Problem：DFS 回溯構造素數環

問題描述

將 1..n (n<20) 排成環，相鄰兩數之和為素數，且第一個數固定為 1。按字典序輸出所有方案。

解法：DFS + 剪枝

預先篩選 40 以內素數（最大和 19+20=39）。遞歸填充位置 pos，嘗試未用過的數 i，檢查 i + ring[pos-1] 是否為素數；最後檢查 ring[n-1] + ring[0]。按遞增順序嘗試自動保證字典序。

代碼實現

int n, ring[20], used[20];
bool isPrime[50];

void dfs(int pos) {
    if (pos == n) {
        if (isPrime[ring[n-1] + ring[0]]) {
            for (int i=0;i1) printf("\n");
        printf("Case %d:\n", caseNo++);
        memset(used,0,sizeof(used));
        ring[0]=1; used[1]=1;
        dfs(1);
    }
    return 0;
}

關鍵點

• 素數表預計算，O(1) 判斷。
• 第一個數固定為 1，避免旋轉重複。
• 遞增枚舉保證輸出字典序。
• 多測試用例間空行處理。

複雜度

n≤16 時方案數極少，DFS 瞬間結束。n=16 最大約 810 個方案。

總結

HDU 1016 是經典回溯入門題。核心在於「固定首元素破對稱」+「素數表加速判斷」+「遞增枚舉產生有序解」。模板極其通用，可解決所有排列組合約束問題。