NEFU 640 Number Guessing：四位數猜謎遊戲暴力解

問題描述

給定 n 條提示，每條格式為 XXXX aA bB：

• XXXX：猜測的四位數（數字不重複）。
• a：數字與位置皆正確的個數（A）。
• b：數字正確但位置錯誤的個數（B）。

保證存在唯一解。輸入以負數 n 結束（非 -1，注意題目陷阱）。

解法：全排列暴力枚舉

四位數不重複數字共有 10×9×8×9 = 5040 種可能（首位不可為 0），極小。直接枚舉所有合法四位數，逐一驗證是否滿足所有提示即可。

驗證邏輯

bool check(int guess, const vector<tuple<string,int,int>>& hints) {
    string g = to_string(guess);
    for (auto [s, a, b] : hints) {
        int ca = 0, cb = 0;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                if (g[i] == s[j]) {
                    if (i == j) ++ca;
                    else ++cb;
                }
            }
        }
        if (ca != a || cb != b) return false;
    }
    return true;
}

完整程式碼（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n >= 0) {  // 注意：n 為負數結束，非 -1
        vector<tuple<string,int,int>> hints(n);
        for (int i = 0; i < n; ++i) {
            string s; int a, b; char ch;
            cin >> s >> a >> ch >> b; // 讀入 "4A2B" 格式
            hints[i] = {s, a, b};
        }
        for (int a = 1; a <= 9; ++a)      // 千位不可為 0
        for (int b = 0; b <= 9; ++b) if (b != a)
        for (int c = 0; c <= 9; ++c) if (c != a && c != b)
        for (int d = 0; d <= 9; ++d) if (d != a && d != b && d != c) {
            int guess = a*1000 + b*100 + c*10 + d;
            if (check(guess, hints)) {
                cout << setw(4) << setfill('0') << guess << '\n';
                goto NEXT_CASE;
            }
        }
        NEXT_CASE: ;
    }
    return 0;
}

複雜度分析

• 枚舉數量：5040（固定常數）。
• 每數驗證 n 條提示（n 通常 ≤ 100）。
• 總時間 O(5040 × n) ≪ 1 秒，極其輕鬆。

避坑指南

• 輸入結束條件：題目說「程序結束是 n 為負數，而不是 -1」，許多選手在此 WA。
• 讀入格式：scanf("%s %dA%dB", ...) 可直接解析 4A2B。
• 輸出格式：不足四位補前導零（如 0123）。