10层嵌套循环求解数字拼图效率低下，求算法优化方案

问题背景 #

你原本用10层嵌套循环暴力枚举：

for(int a = 1; a <= 12; a++){
    for(int b = 1; b <= 12; b++){
        for(int c = 1; c <= 12; c++){
            for(int d = 1; d <= 12; d++){
                for(int e = 1; e <=12; e++){
                    for(int f = 1; f <=12; f++){
                        for(int g = 1; g <=12; g++){
                            for(int h = 1; h <=12; h++){
                                for(int i = 1; i <=12; i++){
                                    for(int j = 1; j <=12; j++){
                                        //does something...

目标是找出1-12之间不重复的10个数字a-j，满足：

• a+b+c+d=20
• d+e+f=20
• f+g+h+i=20
• i+j+a=20

但12^10（约6.1万亿）次迭代完全无法高效执行，预先生成组合再匹配的思路是完全可行的，甚至可以通过数学推导进一步简化问题，以下是具体优化方案：

优化思路1：数学推导减少枚举变量 #

先把四个等式相加：

(a+b+c+d)+(d+e+f)+(f+g+h+i)+(i+j+a) = 80
整理得：2a + b + c + 2d + e + 2f + g + h + 2i + j = 80

因为a-j是10个不重复的1-12数字，总和为1+2+...+12减去两个未使用的数x、y，即总和=78 - x - y。代入上式可得：

(78 - x - y) + (a + d + f + i) = 80 → a+d+f+i = 2 + x + y

同时，从原等式可以推导出所有变量都能用a、d、f、i表示：

• b + c = 20 - a - d
• e = 20 - d - f
• g + h = 20 - f - i
• j = 20 - i - a

这样只需要枚举a、d、f、i四个变量（共12×11×10×9=11880次迭代，完全可快速执行），再验证以下条件即可：

• a、d、f、i为1-12的不同数字
• e=20-d-f必须是1-12的数字，且不在{a,d,f,i}中
• j=20-i-a必须是1-12的数字，且不在{a,d,f,i,e}中
• 找到两个不同的数字b、c，满足b+c=20-a-d，且b、c不在已用的{a,d,f,i,e,j}中，b≠c
• 找到两个不同的数字g、h，满足g+h=20-f-i，且g、h不在已用的{a,b,c,d,e,f,i,j}中，g≠h
• 最终所有10个数字不重复，且满足a+d+f+i=2+x+y（x、y为未使用的两个1-12数字）

优化思路2：预生成组合匹配 #

如果坚持预生成组合的思路，可按以下步骤执行：

• 预生成合法4元组：生成所有1-12中不重复的4数组合，满足和为20，分别对应(a,b,c,d)和(f,g,h,i)，存储时以共享变量为键（比如(a,d)作为(a,b,c,d)的键，(f,i)作为(f,g,h,i)的键）。
• 预生成合法3元组：生成所有1-12中不重复的3数组合，满足和为20，对应(d,e,f)，存储时以(d,f)为键。
• 组合匹配：遍历所有(a,b,c,d)，根据d找到对应的(d,e,f)，再根据f找到对应的(f,g,h,i)，最后检查i+j+a=20的条件，同时确保所有数字不重复。

这种方式的迭代次数远低于暴力枚举，因为预生成的组合数量本身就很少（比如和为20的4元组，1-12不重复的数量远少于12^4）。

代码示例（简化版） #

以下是基于思路1的简化代码框架：

#include <iostream>
#include <unordered_set>
using namespace std;

// 寻找两个不同的数，和为target，且不在已用集合中
bool findPair(int target, unordered_set<int>& used, int& num1, int& num2) {
    for (int n = 1; n <= 12; n++) {
        if (used.count(n)) continue;
        int complement = target - n;
        if (complement >=1 && complement <=12 && complement != n && !used.count(complement)) {
            num1 = n;
            num2 = complement;
            return true;
        }
    }
    return false;
}

int main() {
    for (int a = 1; a <=12; a++) {
        for (int d = 1; d <=12; d++) {
            if (d == a) continue;
            for (int f = 1; f <=12; f++) {
                if (f == a || f == d) continue;
                for (int i = 1; i <=12; i++) {
                    if (i == a || i == d || i == f) continue;
                    
                    // 计算e并验证合法性
                    int e = 20 - d - f;
                    if (e <1 || e >12 || used.count(e)) continue;
                    
                    // 计算j并验证合法性
                    int j = 20 - i - a;
                    if (j <1 || j >12 || used.count(j)) continue;
                    
                    unordered_set<int> used = {a,d,f,i,e,j};
                    int bc_sum = 20 - a - d;
                    int b,c;
                    if (!findPair(bc_sum, used, b, c)) continue;
                    used.insert(b);
                    used.insert(c);
                    
                    int gh_sum = 20 - f - i;
                    int g,h;
                    if (!findPair(gh_sum, used, g, h)) continue;
                    used.insert(g);
                    used.insert(h);
                    
                    // 验证a+d+f+i = 2 + x + y（x,y为未使用数字）
                    int sum_adfi = a + d + f + i;
                    int unused_sum = 78;
                    for (int num : used) unused_sum -= num;
                    if (sum_adfi != 2 + unused_sum) continue;
                    
                    // 输出合法解
                    cout << "a="<<a<<", b="<<b<<", c="<<c<<", d="<<d<<", e="<<e<<endl;
                    cout << "f="<<f<<", g="<<g<<", h="<<h<<", i="<<i<<", j="<<j<<endl;
                    cout << "未使用数字：";
                    for (int num=1; num<=12; num++){
                        if (!used.count(num)) cout << num << " ";
                    }
                    cout << endl << "---" << endl;
                }
            }
        }
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Elias Krasny