用 C# 破解「愛因斯坦謎題」：從暴力窮舉到短路優化的算法進化

編輯：關於C語言

謎題背景：誰養魚？

傳說這是愛因斯坦出的智力測驗，號稱全球僅 2% 人能解出。題目描述一條街上有 5 棟顏色不同的房子，每棟住不同國籍的人，他們飲品、菸牌、寵物皆不相同。給定 15 條線索（如「英國人住紅房子」、「綠房子在白房子左側」、「挪威人住第一間」等），推導出誰養魚。

初嘗暴力窮舉：組合爆炸的教訓

每類屬性（國籍、顏色、寵物、飲料、菸牌）皆為 5 個元素的排列，共有 5! = 120 種排列。五類屬性獨立排列，總組合數高達 120^5 ≈ 2.49×10^10（約 249 億種）。純暴力窮舉在當時硬體上跑 30 分鐘仍無解，預估需數天才能完成——這是典型的組合爆炸問題。

短路優化：逐層剪枝，瞬間得解

核心思想：在生成排列過程中即時驗證約束，一旦不滿足立即跳過後續組合（類似邏輯運算中的短路求值）。具體步驟：

預先生成所有 120 種排列存入陣列 aid[120,5]。
依約束強弱排序驗證順序：先固定「挪威人住第一間」（assert9）、「中間房喝牛奶」（assert8）等單一位置約束，大幅縮減搜尋空間。
巢狀迴圈逐層填入屬性排列，每填入一層即呼叫對應斷言函式（assert1~15），失敗即 continue 跳過內層迴圈。
最終僅需檢查極少數組合即可找到唯一解。

核心代碼結構解析

資料模型：列舉與矩陣

enum 國籍 { 英國, 瑞典, 丹麥, 挪威, 德國 };
enum 顏色 { 紅, 綠, 藍, 黃, 白 };
enum 寵物 { 鳥, 貓, 馬, 魚, 狗 };
enum 飲料 { 水, 牛奶, 咖啡, 茶, 啤酒 };
enum 香煙 { blends, blue, prince, dunhill, pall };

// 5x5 矩陣：行=房子(0-4)，列=屬性類別(國籍,顏色,寵物,飲料,香煙)
private int[,] array = new int[5, 5];

關鍵斷言函式範例

// 規則 4：綠房子在白房子左側（相鄰）
private bool assert4() {
    return get顏色(顏色.綠) == get顏色(顏色.白) - 1;
}

// 規則 10：抽 Blends 的人住在養貓的人隔壁
private bool assert10() {
    int t1 = get香煙(香煙.blends), t2 = get寵物(寵物.貓);
    return Math.Abs(t1 - t2) == 1;
}

優化後的求解主流程

public void Solve() {
    int sn = 1;
    // 依約束強度排序：國籍 -> 飲料 -> 顏色 -> 寵物 -> 香煙
    for (int i0 = 0; i0 < 120; i0++) { replace((int)T.國籍, i0); if (!assert9()) continue;
        for (int i1 = 0; i1 < 120; i1++) { replace((int)T.飲料, i1); if (!assert8()) continue; if (!assert3()) continue;
            for (int i2 = 0; i2 < 120; i2++) { replace((int)T.顏色, i2); if (!assert4()) continue; if (!(assert1() && assert14() && assert5())) continue;
                for (int i3 = 0; i3 < 120; i3++) { replace((int)T.寵物, i3); if (!assert2()) continue;
                    for (int i4 = 0; i4 < 120; i4++) { replace((int)T.香煙, i4);
                        if (assert6() && assert7() && assert10() && assert11() && assert12() && assert15() && assert13()) {
                            if (assert()) { Console.WriteLine("解：" + sn++); Console.WriteLine(this); }
                        }
                    }
                }
            }
        }
    }
}