C ++ программа для решения криптарифметических задач

// CPP программа для решения криптографических головоломок
#include <bits/stdc++.h>

using namespace std;

  
// вектор хранит 1, соответствующий индексу
// номер, который уже присвоен
// на любой символ, в противном случае хранит 0

vector<int> use(10);

  
// структура для хранения char и соответствующего ему целого числа

struct node

{

    char c;

    int v;

};

  
// проверка функции на правильное решение

int check(node* nodeArr, const int count, string s1,

                               string s2, string s3)

{

    int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;

    // вычисляем число, соответствующее первой строке

    for (i = s1.length() - 1; i >= 0; i--)

    {

        char ch = s1[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

        val1 += m * nodeArr[j].v;

        m *= 10;

    }

    m = 1;

    // вычисляем число, соответствующее второй строке

    for (i = s2.length() - 1; i >= 0; i--)

    {

        char ch = s2[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

        val2 += m * nodeArr[j].v;

        m *= 10;

    }

    m = 1;

    // вычисляем число, соответствующее третьей строке

    for (i = s3.length() - 1; i >= 0; i--)

    {

        char ch = s3[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

        val3 += m * nodeArr[j].v;

        m *= 10;

    }

    // сумма первых двух чисел равна третьей возвращаемое значение true

    if (val3 == (val1 + val2))

        return 1;

    // еще вернуть false

    return 0;

}

  
// Рекурсивная функция для проверки решения для всех перестановок

bool permutation(const int count, node* nodeArr, int n,

                 string s1, string s2, string s3)

{

    // Базовый вариант

    if (n == count - 1)

    {

        // проверяем все неиспользуемые номера

        for (int i = 0; i < 10; i++)

        {

            // если не используется

            if (use[i] == 0)

            {

                // присваиваем char по индексу n целому числу i

                nodeArr[n].v = i;

                // если решение найдено

                if (check(nodeArr, count, s1, s2, s3) == 1)

                {

                    cout << "\nSolution found: ";

                    for (int j = 0; j < count; j++)

                        cout << " " << nodeArr[j].c << " = "

                             << nodeArr[j].v;

                    return true;

                }

            }

        }

        return false;

    }

    for (int i = 0; i < 10; i++)

    {

        // если i-е целое число еще не используется

        if (use[i] == 0)

        {

            // присваиваем char по индексу n целому числу i

            nodeArr[n].v = i;

            // пометить его как недоступный для других символов

            use[i] = 1;

            // вызов рекурсивной функции

            if (permutation(count, nodeArr, n + 1, s1, s2, s3))

                return true;

            // возвращаемся назад для всех других возможных решений

            use[i] = 0;

        }

    }

    return false;

}

bool solveCryptographic(string s1, string s2,

                                   string s3)

{

    // рассчитывать на номер уникального символа

    int count = 0;

    // Длина всех трех строк

    int l1 = s1.length();

    int l2 = s2.length();

    int l3 = s3.length();

    // вектор для хранения частоты каждого символа

    vector<int> freq(26);

    for (int i = 0; i < l1; i++)

        ++freq[s1[i] - 'A'];

    for (int i = 0; i < l2; i++)

        ++freq[s2[i] - 'A'];

    for (int i = 0; i < l3; i++)

        ++freq[s3[i] - 'A'];

    // посчитаем количество уникальных символов

    for (int i = 0; i < 26; i++)

        if (freq[i] > 0)

            count++;

    // решение не возможно для счета больше 10

    if (count > 10)

    {

        cout << "Invalid strings";

        return 0;

    }

    // массив узлов

    node nodeArr[count];

    // сохраняем все уникальные символы в nodeArr

    for (int i = 0, j = 0; i < 26; i++)

    {

        if (freq[i] > 0)

        {

            nodeArr[j].c = char(i + 'A');

            j++;

        }

    }

    return permutation(count, nodeArr, 0, s1, s2, s3);

}

  
// Функция драйвера

int main()

{

    string s1 = "SEND";

    string s2 = "MORE";

    string s3 = "MONEY";

    if (solveCryptographic(s1, s2, s3) == false)

        cout << "No solution";

    return 0;

}