CryptarithmeticCSP.cpp

#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

vector<string> letters = {"S", "E", "N", "D", "M", "O", "R", "Y"};
vector<int> assignment(letters.size());
vector<bool> used(10, false);

bool isValid() {
    int S = assignment[0], E = assignment[1], N = assignment[2], D = assignment[3];
    int M = assignment[4], O = assignment[5], R = assignment[6], Y = assignment[7];

    if (S == 0 || M == 0) return false;

    int send = S * 1000 + E * 100 + N * 10 + D;
    int more = M * 1000 + O * 100 + R * 10 + E;
    int money = M * 10000 + O * 1000 + N * 100 + E * 10 + Y;

    return send + more == money;
}

bool backtrack(int index) {
    if (index == static_cast<int>(letters.size())) {
        return isValid();
    }

    for (int digit = 0; digit <= 9; ++digit) {
        if (!used[digit]) {
            used[digit] = true;
            assignment[index] = digit;
            if (backtrack(index + 1)) return true;
            used[digit] = false;
        }
    }
    return false;
}

int main() {
    if (backtrack(0)) {
        cout << "Solution for SEND + MORE = MONEY:\n";
        for (size_t i = 0; i < letters.size(); ++i) {
            cout << letters[i] << " = " << assignment[i] << '\n';
        }
    } else {
        cout << "No solution found.\n";
    }
    return 0;
}