HNU Number Guessing：猜數字遊戲邏輯推理

題目大意

電腦生成 4 個不重複數字（0-9）。玩家猜測，電腦返回 "xAyB"：A 為位置值均正確的個數，B 為值正確但位置錯誤的個數。給定若干猜測記錄，推導出唯一答案。輸入以負數結束。

解法：暴力枚舉驗證

所有可能答案：從 0123 到 9876 中挑選 4 個不重複數字的排列，共 P(10,4) = 5040 種。對每個候選答案，檢查是否滿足所有猜測記錄。若唯一滿足，輸出該答案。

判斷邏輯

對猜測 g 和答案 ans：

• A = Σ [g[i] == ans[i]]
• B = Σ [g[i] != ans[i] 且 g[i] 在 ans 中出現]

實現時可用數組標記 ans 中出現的數字。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

int check(int guess, int ans) {
    int g[4], a[4];
    for (int i = 3; i >= 0; i--) {
        g[i] = guess % 10; guess /= 10;
        a[i] = ans % 10; ans /= 10;
    }
    int A = 0, B = 0;
    for (int i = 0; i < 4; i++)
        if (g[i] == a[i]) A++;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (i != j && g[i] == a[j]) B++;
    return A*10 + B; // 編碼為 AB 形式
}

int main() {
    int N;
    while (cin >> N) {
        if (N < 0) break;
        int guesses[20], results[20];
        for (int i = 0; i < N; i++) {
            string g, r; cin >> g >> r;
            guesses[i] = stoi(g);
            int A = r[0]-'0', B = r[2]-'0';
            results[i] = A*10 + B;
        }
        for (int ans = 123; ans <= 9876; ans++) {
            // 檢查 ans 是否 4 位不重複
            int d[4], used[10]={0}, ok=1;
            int tmp = ans;
            for (int i = 3; i >= 0; i--) {
                d[i] = tmp % 10; tmp /= 10;
                if (used[d[i]]) { ok=0; break; }
                used[d[i]] = 1;
            }
            if (!ok) continue;
            bool valid = true;
            for (int i = 0; i < N; i++) {
                if (check(guesses[i], ans) != results[i]) {
                    valid = false; break;
                }
            }
            if (valid) {
                // 輸出 4 位，補前導零
                printf("%04d\n", ans);
                break;
            }
        }
    }
    return 0;
}

優化提示

• 預先生成所有 5040 個合法答案存入數組，查詢時直接遍歷。
• 用位掩碼快速檢查重複數字。

總結

搜索空間極小（5040），暴力枚舉驗證最簡單可靠。關鍵是正確實現 A/B 計算邏輯，並處理前導零輸出格式（%04d）。