N 皇后問題 (UVa 1605 變體)：輸出前三解與總解數

前言

經典回溯問題：在 $N \times N$ 棋盤放置 $N$ 個皇后，使其不互相攻擊 (同行、同列、同對角線)。需按字典序輸出前三組解 (以欄位序列表示) 及總解數。$N \le 13$。

解題思路

• 逐行放置皇后，每行僅一個。
• 用三個布林陣列標記佔用：`col[j]` (同列)、`diag1[row+col]` (主對角線)、`diag2[row-col+N]` (副對角線)。
• 遞迴嘗試每列，安全則標記並進入下一行，回溯時取消標記。
• 計數器 `total` 記錄總解，`printed` 控制前三解輸出。

完整程式碼

#include 

int n, total = 0;
int col[14], diag1[27], diag2[27];  /* 索引上限 2N-1 */
int sol[14];                         /* 當前解: sol[row] = col */

void dfs(int row) {
    if (row > n) {
        total++;
        if (total <= 3) {
            for (int i = 1; i <= n; i++) {
                printf("%d%c", sol[i], i == n ? '\n' : ' ');
            }
        }
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (!col[c] && !diag1[row+c] && !diag2[row-c+n]) {
            sol[row] = c;
            col[c] = diag1[row+c] = diag2[row-c+n] = 1;
            dfs(row + 1);
            col[c] = diag1[row+c] = diag2[row-c+n] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", total);
    return 0;
}

範例 (N=6)

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

關鍵點

• 對角線索引轉換：`row+col` (範圍 2~2N)、`row-col+N` (範圍 1~2N-1)。
• 陣列大小開 `2*N+1` 即可 (N≤13 → 27)。
• 按列 1→N 遞迴天然產生字典序解。
• 時間複雜度 $O(N!)$ 剪枝後極快，N=13 瞬間跑完。