推荐一波题解：http://blog.csdn.net/yuyanggo/article/details/48154031
这道题很容易想出要用DFS，但是单纯的DFS枚举时间复杂度会达到O（n!)，这个复杂度是难以接受的，因此我们要想办法剪去一些不必要的情况：
1.用used[i]表示i这个数字是否已使用，若枚举过程中算出不同字母表示了同一个数字，表明枚举不合法，直接退出。
2.a[i]和b[i]都已确定，那么c[i]只有可能是(a[i]+b[i])%n或(a[i]+b[i]+1)%n（如果进位已知则可以直接算出）,如果这两个数字都已经被用过且不是c[i]所表示的话，枚举不合法，退出；否则若进位已知，把c[i]表示为这个数字并打上标记。
3.a[i]和c[i]已知但不知道b[i]，容易知道b[i]只可能为(c[i]-a[i]+n)%n或(c[i]-a[i]+n)%n+1，注意这里c[i]-a[i]可能是负数所以要先加n再取余，如果这两个数字都已经使用过且不是b[i]所表示，枚举不合法，退出。
4.b[i]和c[i]已知但a[i]不知，道理同上。
5.当a[0]+b[0]>=n时，因为三个数都为n位，所以不满足，退出。
剪枝部分的思路基本就是这样，然后要记得的就是赋值时要记得打标记，失败退出时要清空标记，这里用了一个q[0]和p的比较来清空不合法的枚举中赋给c[i]的数字的标记，自己理解一下。
剩下的具体实现部分看代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> const int maxn=36; using namespace std; char a[maxn],b[maxn],c[maxn],n; int ans[200],q[maxn]; bool used[maxn]; bool ok(int x,int jin) { if(ans[a[0]]+ans[b[0]]>=n)return 0; int i,j,k; for(i=x;i>=0;i--) { if(ans[a[i]]!=-1&&ans[b[i]]!=-1) { j=ans[a[i]]+ans[b[i]]+jin;jin=j/n; if(ans[c[i]]!=-1&&ans[c[i]]!=(j%n))return 0; if(ans[c[i]]==-1) { if(used[j%n])return 0; ans[c[i]]=j%n;used[j%n]=1;q[++q[0]]=c[i]; } } else break; } if(ans[a[0]]+ans[b[0]]>=n)return 0; for(;i>=0;i--) { if(ans[a[i]]!=-1&&ans[b[i]]!=-1) { j=ans[a[i]]+ans[b[i]]; if(ans[c[i]]!=-1&&ans[c[i]]!=(j%n)&&ans[c[i]]!=((j+1)%n))return 0; if(ans[c[i]]==-1&&used[j%n]&&used[(j+1)%n])return 0;continue; } if(ans[a[i]]!=-1&&ans[c[i]]!=-1) { j=ans[c[i]]-ans[a[i]]+n; if(used[j%n]&&used[(j-1)%n])return 0; } if(ans[b[i]]!=-1&&ans[c[i]]!=-1) { j=ans[c[i]]-ans[b[i]]+n; if(used[j%n]&&used[(j-1)%n])return 0; } } return 1; } bool dfs(int x,int jin,bool flag) { if(x<0)return 1; int p=q[0],i; if(flag) { if(ans[a[x]]!=-1)return dfs(x,jin,0); for(ans[a[x]]=n-1;ans[a[x]]>=0;ans[a[x]]--) { if(!used[ans[a[x]]]) { used[ans[a[x]]]=1; if(ok(x,jin)&&dfs(x,jin,0))return 1; while(q[0]>p) { used[ans[q[q[0]]]]=0;ans[q[q[0]]]=-1; q[0]--; } used[ans[a[x]]]=0; } } return 0; } if(ans[b[x]]!=-1)return dfs(x-1,(ans[a[x]]+ans[b[x]]+jin)/n,1); for(ans[b[x]]=n-1;ans[b[x]]>=0;ans[b[x]]--) { if(!used[ans[b[x]]]) { used[ans[b[x]]]=1; if(ok(x,jin)&&dfs(x-1,(ans[a[x]]+ans[b[x]]+jin)/n,1))return 1; while(q[0]>p) { int k=q[q[0]];used[ans[k]]=0;ans[k]=-1;q[0]--; } used[ans[b[x]]]=0; } } return 0; } int main() { scanf("%d",&n); scanf("%s",a); scanf("%s",b); scanf("%s",c); for(int i=0;i<n;i++)ans['A'+i]=-1; memset(used,0,sizeof(used)); dfs(n-1,0,1); printf("%d",ans['A']); for(int i=1;i<n;i++)printf(" %d",ans['A'+i]); return 0; }