Chương trình C++ giải bài toán Cryptarithmetic Puzzles

Cryptarithmetic Puzzle: Gán chữ số 0-9 cho các chữ cái sao cho phép cộng đúng. Ví dụ: BASE + BALL = GAMES.

Ràng buộc: Tối đa 10 chữ cái khác nhau (vì chỉ có 10 chữ số 0-9).

Ví dụ

  B A S E
+ B A L L
---------
G A M E S

Giải pháp:
A=4, B=2, E=1, G=0, L=5, M=9, S=6
  2 4 6 1
+ 2 4 5 5
---------
  0 4 9 1 6  (GAMES = 04916, nhưng G=0 dẫn đầu? Thường G≠0)

Lưu ý: Thường chữ cái đầu không được bằng 0. Code gốc cho phép G=0.

Thuật toán Backtracking

1. Thu thập tất cả chữ cái duy nhất từ 3 từ.
2. Nếu > 10 → vô nghiệm.
3. Thử gán chữ số 0-9 cho từng chữ cái (backtracking).
4. Kiểm tra: giá trị word1 + word2 == word3?

Code ví dụ (đã sửa lỗi compile)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Node {
    char letter;
    int value = -1;
};

vector<int> used(10, 0); // Chữ số 0-9 đã dùng

bool isValid(const vector<Node>& nodes, const string& s1, const string& s2, const string& s3) {
    auto getValue = [&](const string& s) {
        long long val = 0;
        for(char c : s) {
            for(const auto& node : nodes)
                if (node.letter == c) { val = val * 10 + node.value; break; }
        }
        return val;
    };
    
    long long v1 = getValue(s1);
    long long v2 = getValue(s2);
    long long v3 = getValue(s3);
    
    // Kiểm tra chữ cái đầu không phải 0 (tùy chọn)
    // if (nodes[0].value == 0 || ...) return false;
    
    return v1 + v2 == v3;
}

bool solve(int idx, vector<Node>& nodes, const string& s1, const string& s2, const string& s3) {
    if (idx == nodes.size()) {
        if (isValid(nodes, s1, s2, s3)) {
            cout << "Solution: ";
            for(auto& node : nodes) cout << node.letter << "=" << node.value << " ";
            cout << endl;
            return true;
        }
        return false;
    }
    
    for(int d = 0; d <= 9; d++) {
        if (!used[d]) {
            used[d] = 1;
            nodes[idx].value = d;
            if (solve(idx + 1, nodes, s1, s2, s3)) return true;
            used[d] = 0;
        }
    }
    return false;
}

bool solvePuzzle(string s1, string s2, string s3) {
    vector<int> freq(26, 0);
    for(char c : s1) freq[c-'A']++;
    for(char c : s2) freq[c-'A']++;
    for(char c : s3) freq[c-'A']++;
    
    vector<Node> nodes;
    for(int i = 0; i < 26; i++)
        if (freq[i] > 0) nodes.push_back({char('A'+i), -1});
    
    if (nodes.size() > 10) {
        cout << "Invalid: >10 unique letters\n";
        return false;
    }
    
    return solve(0, nodes, s1, s2, s3);
}

int main() {
    string s1 = "BASE", s2 = "BALL", s3 = "GAMES";
    if (!solvePuzzle(s1, s2, s3))
        cout << "No solution\n";
    return 0;
}

Kết quả

Solution: A=4 B=2 E=1 G=0 L=5 M=9 S=6

Độ phức tạp

• O(10!) = 3.6M trường hợp worst-case (10 chữ cái).
• Cắt tỉa (pruning) sớm: kiểm tra cột đơn vị trước, v.v.
• Thực tế chạy rất nhanh cho puzzle thông thường.

Cải tiến chuyên nghiệp

• Column-wise solving (giải theo cột từ phải sang trái).
• Constraint propagation.
• Dùng OR-Tools CP-SAT cho bài toán lớn.