问题描述：

Arithmetic puzzle is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter. – wikipedia

For example, SEND+MORE=MONEY is a famous one of such puzzles. The solution is 9567+1085=10652. Note that different letters should represent different digits and the leading digit of a multi-digit number shoud not be zero.

Given an arithmetic puzzle, please find the solution.

问题分析：

首先由于数字只有0~9 10个数字，所以字母个数最多为10个。
当单词长度不超过1时，其首字母不能为0。
我们最笨的方法是枚举每个字母的数值，然后判断是否会让等式成立。
枚举的个数最多有10！= 3,628,800个， 显然时间复杂度太大。
优化方法：
首先我们把右边的字母移到左边：
SEND+MORE-MONEY=0；
变成这样的形式。
计算时可以

首先从第0位开始，从第一行到第三行，对应的字母分别是D E Y ， 我们先枚举D E Y 的值，然后， 对算出
s= D + E - Y , w = s /10 如果s%10 不为 0 则当前组合是不会成立的， 枚举下一个D E Y， 如果 s %10 为0， 我们计算第1位， 同样枚举 N R E 的值， E已经枚举过了，就不用再赋值了， 依次类推，如果所有数字都枚举完成，就得到了一个结果。

优化二
对于有些位置的字母，其值不会对结果产生影响， 我们就可以先不枚举这些字母，最后再对其赋值。
如A+B+C+D+E+F+G+HJJJJJJJJJJJJJJ=A+B+C+D+E+F+G+IJJJJJJJJJJJJJJ
中对结果又影响的只是字母H 和I 其他字母可以取任意数字。
所以在枚举到这些位置时，可以跳过。

代码太长，调了很久才调通。

#include <vector>
#include <cstring>
#include <cstdio>
#include <string>
enum{maxn = 100+5, letterNum = 27, numNum = 10};
using namespace std;
struct wd{
    int c;
    int useful;
};
vector<wd> word[maxn];
int wordNum;
int wordLen;
int opSplit;
char str[maxn];
bool notZero[letterNum];
int val[letterNum];
bool useNum[numNum];
int visited[letterNum];
int orderNum;
vector<int> order;
string res;

bool isLetter(char c)
{
    return c>= 'A' && c<= 'Z';
}
void findOrder()
{
    for (int i=0; str[i]; i++)
        if (isLetter(str[i])&& !visited[str[i] -'A'])
         {
             visited[str[i] - 'A'] = 1;
             order.push_back(str[i]- 'A');
         }
}

void parseWord()
{
    char * s = str;
    wordLen = -1;
    for (wordNum = 0; ; wordNum++)
    {
        int i=0;
        for (; isLetter(s[i]); i++);
        if (i> 1)
        {
            notZero[*s - 'A'] = true;
        }
        wordLen = max(wordLen, i);
        for (int j=i-1; j>=0; j--){
            word[wordNum].push_back(wd{s[j]-'A', 1});
        }
        s += i;

        if (*s == '=')
        {
            opSplit = wordNum +1;
        }
        if (*s == '\0')
            break;
     //   printf("%c wordNum %d\n", *s, wordNum);
        s++;
    }
    wordNum++;
}
void setUseLess()
{
    for (int i=0; i< wordNum; i++)
    {
       // printf("word %d :", i);
        for (int j=0; j<word[i].size(); j++)
        {
        //    printf("%c", word[i][j].c+'A');
            if (i >= opSplit)
                continue;
            if (word[i][j].useful == 1)
            {
                for (int k=opSplit; k< wordNum; k++)
                {
                    if (word[k].size() > j && word[k][j].useful == 1 && word[k][j].c == word[i][j].c)
                    {
                        word[k][j].useful = word[i][j].useful = 0;
             //           printf("--word %d %d %d %c useless\n", i, k, j, word[i][j].c + 'A');
                        break;
                    }
                }
            }
        }
     //   printf("\n");
    }
}
void fillAns(int i)
{
   //printf("fill ans %d %c\n", i, order[i] + 'A');
    if (i >= letterNum)
    {
        string s;
        for (int j=0; str[j]; j++)
        {
            if (isLetter(str[j]))
                s.push_back(val[str[j]-'A'] + '0');
            else
                s.push_back(str[j]);
        }
    //    printf("s is %s\n", s.c_str());
        if (res == "" || res > s)
            res = s;
        return;
    }
    while(i< letterNum && visited[i]== 0) i++;
    if (i>= letterNum) {
         fillAns(i);
         return ;
    }

        if (val[i] == -1)
        {
            int startNum = 0;
            if (notZero[i])
                startNum = 1;
            for (int j=startNum; j<= 9; j++)
            {
                if (useNum[j] == false)
                {
                    useNum[j] = true;
                    val[i] = j;
                    fillAns(i+1);
                    useNum[j] = false;
                    val[i]= -1;
                    return;
                }
            }
        }else
            fillAns(i+1);

}
void dfs(int i, int j, int s)
{
   // printf("i %d j %d s %d\n", i, j, s);
    if (i == wordLen)
    {
   //     printf("888\n");
        if (s==0)
            fillAns(0);
        return;
    }
    if (j== wordNum)
    {
    //    printf("999\n");

        if (s%10 == 0)
            dfs(i+1, 0, s/10);
        return;
    }


    if (word[j].size() <= i || word[j][i].useful == 0)
    {
        dfs(i, j+1, s);
        return ;
    }
   // printf("111\n");
    int op= 1;
    if (j >= opSplit)
        op = -1;
   // printf("5555\n");
    if (val[word[j][i].c] == -1)
    {
   //     printf("222\n");
       int startNum = 0;
       if (notZero[word[j][i].c])
            startNum = 1;
    //    printf("444\n");
       for (int k=startNum; k<= 9; k++)
       {
           if (!useNum[k])
           {
               useNum[k] = true;
               val[word[j][i].c] = k;
    //           printf("set %c as %d\n", word[j][i].c + 'A', k);
               dfs(i, j+1, s+k*op);
               useNum[k] = false;
               val[word[j][i].c] = -1;
           }
       }
    }
    else
    {
   //     printf("3333\n");
   //     printf("    %c is %d\n", word[j][i].c + 'A', val[word[j][i].c]);
        dfs(i, j+1, s+val[word[j][i].c] * op);
    }

}
#define OJ
int main()
{
    #ifndef OJ
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif // OJ

    int n;
    scanf("%d", &n);
    while(n--){
        for(int i=0; i<maxn; i++)
            word[i].clear();
        wordNum = 0;
        memset(val, -1, sizeof(val));
        memset(notZero, 0, sizeof(notZero));
        memset(useNum, 0, sizeof(useNum));
        memset(visited, 0, sizeof(visited));
        order.clear();
        res.clear();
        scanf("%s", str);
   //     printf("%s\n", str);
        findOrder();
        if (order.size() > 10)
        {
            printf("No Solution\n");
        }
        else{
            parseWord();
            setUseLess();
     //      printf("%d %d\n", wordNum, wordLen);
            dfs(0, 0, 0);
            if (res == "")
                printf("No Solution\n");
            else
                printf("%s\n", res.c_str());
        }

    }
    return 0;
}