搜尋 Arithmetic Puzzles

問題描述：

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；

變成這樣的形式。

計算時可以

符号	4	3	2	1
+	S	E	N	D
+	M	O	R	E
-	M	O	N	E	Y

首先從第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 = +, letterNum = , numNum = };
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=; str[i]; i++)
        if (isLetter(str[i])&& !visited[str[i] -'A'])
         {
             visited[str[i] - 'A'] = ;
             order.push_back(str[i]- 'A');
         }
}

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

        if (*s == '=')
        {
            opSplit = wordNum +;
        }
        if (*s == '\0')
            break;
     //   printf("%c wordNum %d\n", *s, wordNum);
        s++;
    }
    wordNum++;
}
void setUseLess()
{
    for (int i=; i< wordNum; i++)
    {
       // printf("word %d :", i);
        for (int j=; j<word[i].size(); j++)
        {
        //    printf("%c", word[i][j].c+'A');
            if (i >= opSplit)
                continue;
            if (word[i][j].useful == )
            {
                for (int k=opSplit; k< wordNum; k++)
                {
                    if (word[k].size() > j && word[k][j].useful ==  && word[k][j].c == word[i][j].c)
                    {
                        word[k][j].useful = word[i][j].useful = ;
             //           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=; 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]== ) i++;
    if (i>= letterNum) {
         fillAns(i);
         return ;
    }

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

}
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==)
            fillAns();
        return;
    }
    if (j== wordNum)
    {
    //    printf("999\n");

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


    if (word[j].size() <= i || word[j][i].useful == )
    {
        dfs(i, j+, s);
        return ;
    }
   // printf("111\n");
    int op= ;
    if (j >= opSplit)
        op = -;
   // printf("5555\n");
    if (val[word[j][i].c] == -)
    {
   //     printf("222\n");
       int startNum = ;
       if (notZero[word[j][i].c])
            startNum = ;
    //    printf("444\n");
       for (int k=startNum; k<= ; 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+, s+k*op);
               useNum[k] = false;
               val[word[j][i].c] = -;
           }
       }
    }
    else
    {
   //     printf("3333\n");
   //     printf("    %c is %d\n", word[j][i].c + 'A', val[word[j][i].c]);
        dfs(i, j+, 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=; i<maxn; i++)
            word[i].clear();
        wordNum = ;
        memset(val, -, sizeof(val));
        memset(notZero, , sizeof(notZero));
        memset(useNum, , sizeof(useNum));
        memset(visited, , sizeof(visited));
        order.clear();
        res.clear();
        scanf("%s", str);
   //     printf("%s\n", str);
        findOrder();
        if (order.size() > )
        {
            printf("No Solution\n");
        }
        else{
            parseWord();
            setUseLess();
     //      printf("%d %d\n", wordNum, wordLen);
            dfs(, , );
            if (res == "")
                printf("No Solution\n");
            else
                printf("%s\n", res.c_str());
        }

    }
    return ;
}