Verbal Arithmetic

Verbal Arithmetic
バックトラックで解いてみました。 適当な枝刈りをすれば手元で１０秒くらいorz。

優れた解法はlaycurseさんのブログを参照。

#include<iostream>
#include<string>
using namespace std;
#define MAX 12

int N, L[26], R[26], LT[26][10], RT[26][10];
string S[MAX];
int num[26];
bool used[10];
int cnt, MDL[26], MDR[26];

void setValue( string str, int a[] ){
    for ( int i = str.size()-1, p = 1; i >= 0; i--, p *= 10 ){
        a[str[i] - 'A'] += p;
    }
}

bool zeroCheck(){
    for ( int i = 0; i < N; i++ ){
        if ( S[i].size() > 1 && num[S[i][0]-'A'] == 0 ) return false;
    }
    return true;
}

void rec( int cur, int left, int right ){
    if ( cur == 26 ){
        if ( left == right && zeroCheck() ) cnt++;
        return;
    }

    if ( left + MDL[cur] < right ) return;
    if ( right + MDR[cur] < left ) return;
    
    if ( L[cur] + R[cur] == 0 ){ rec( cur+1, left, right ); return; }

    for ( int d = 9; d >= 0; d-- ){
        if ( used[d] ) continue;
        used[d] = true;
        num[cur] = d;
        rec( cur+1, left + L[cur]*d, right + R[cur]*d );
        used[d] = false;
    }
}

void makeMD(){
    int md = 0;
    MDL[25] = 9*(L[25]);
    MDR[25] = 9*(R[25]);
    for ( int i = 24; i >= 0; i-- ){
        MDL[i] = MDL[i+1] + (L[i])*9;
        MDR[i] = MDR[i+1] + (R[i])*9;
    }
}

main(){
    while ( cin >> N && N ){
        for ( int i = 0; i < 26; i++ ) { L[i] = R[i] = 0;}
        for ( int i = 0; i < N; i++ ) {
            cin >> S[i];
            if ( i == N-1 ) setValue( S[i], R );
            else setValue( S[i], L );
        }

        makeMD();

        for ( int i = 0; i <= 9; i++ ) used[i] = false;
        cnt = 0;
        rec(0, 0, 0);
        cout << cnt << endl;
    }
}