您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

經典數字排列謎題：7 對數字間距約束的回溯求解

編輯：關於C++

問題描述

有數字 1~7 各兩個（共 14 個），排成一列，滿足：

兩個 1 之間隔 1 個其他數字
兩個 2 之間隔 2 個其他數字
...
兩個 7 之間隔 7 個其他數字

已知一解：17126425374635（逆序亦為解）。求另一解，且以 74 開頭。

數學建模與約束

設數字 i 的第一個出現位置為 a[i]（1-based），則第二個位置為 a[i] + i + 1。約束條件：

所有位置在 1~14 範圍內
任兩數字的佔用位置不重疊：{a[i], a[i]+i+1} 集合兩兩不相交

回溯搜尋策略

遞迴嘗試 a[1] ~ a[7] 的所有合法位置
剪枝：位置越界、與已定數字衝突即回溯
額外條件：a[7]==1（第一位為 7）、a[4]==2（第二位為 4）

完整 C 程式碼

#include <stdio.h>
#define N 7

int a[8];      // a[i] = 數字 i 第一次出現的位置
int m[15];     // 最終序列

int ok(int h) {
    if (a[h] + h + 1 > 14) return 0;  // 越界
    for (int i = 1; i <= 7; i++) {
        if (a[i] != 0 && i != h) {
            int pos1 = a[h], pos2 = a[h] + h + 1;
            int opos1 = a[i], opos2 = a[i] + i + 1;
            if (pos1 == opos1 || pos1 == opos2 || pos2 == opos1 || pos2 == opos2)
                return 0;  // 位置衝突
        }
    }
    return 1;
}

void compute(int h) {
    if (h == 8 && a[7] == 1 && a[4] == 2) {  // 找到目標解
        for (int i = 1; i <= 7; i++) {
            m[a[i]] = i;
            m[a[i] + i + 1] = i;
        }
        for (int i = 1; i <= 14; i++) printf("%d", m[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= 14; i++) {
        a[h] = i;
        if (ok(h)) compute(h + 1);
        a[h] = 0;
    }
}

int main() {
    compute(1);
    return 0;
}