Magic/CryptarithmeticPuzzle.cpp at main · smmesbah/Magic · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_valid(vector<int> &assignment)
{
    return (assignment[0] != 0);
}

bool constraint_satisfied(vector<int> &assignment)
{
    int T = assignment[0];
    int W = assignment[1];
    int O = assignment[2];
    int F = assignment[3];
    int U = assignment[4];
    int R = assignment[5];

    int two1 = T * 100 + W * 10 + O;
    int two2 = T * 100 + W * 10 + O;
    int four = F * 1000 + O * 100 + U * 10 + R;

    return (two1 + two2 == four);
}

bool backtrack(vector<int> &assignment, vector<bool> &used, int index)
{
    if (index == 6)
    {
        if (constraint_satisfied(assignment))
        {
            return true;
        }
        return false;
    }

    for (int i = 0; i <= 9; i++)
    {
        if (!used[i])
        {
            assignment[index] = i;
            used[i] = true;

            if (is_valid(assignment))
            {
                if (backtrack(assignment, used, index + 1))
                {
                    return true;
                }
            }

            assignment[index] = -1;
            used[i] = false;
        }
    }

    return false;
}

int main()
{
    vector<int> assignment(6, -1);
    vector<bool> used(10, false);

    if (backtrack(assignment, used, 0))
    {
        cout << "Solution found:" << endl;
        cout << "   T  W  O" << endl;
        cout << " + T  W  O" << endl;
        cout << "---------------" << endl;
        cout << "F  O  U  R" << endl;

        cout << "Values:" << endl;
        cout << "T = " << assignment[0] << endl;
        cout << "W = " << assignment[1] << endl;
        cout << "O = " << assignment[2] << endl;
        cout << "F = " << assignment[3] << endl;
        cout << "U = " << assignment[4] << endl;
        cout << "R = " << assignment[5] << endl;
    }
    else
    {
        cout << "No valid solution found." << endl;
    }

    return 0;
}