这道题是一道经久不衰的搜索题目，但是开始做的时候我没什么思路==。初始值-1 输出格式
(naive)想法
从右往左依次尝试填充数字，把算式当做一个3行(n)列的网格。（什么？你问为什么是从右往左？大概是人类习惯吧(qwq)），然后需要头脑清晰的分类讨论，对搜到第三行字符串时要特别注意。
具体的分类讨论：当前位置是否已经填了（(*2)）,判断当前行是不是第三行（(*2)）。
(80)分代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int num[30];
bool vis[30];
char st[4][30];
void dfs(int y,int x,int hi)
{//列 行 进位数
if(y==0)
{
if(hi!=0) return ;
for(int i=1;i<=n-1;i++) printf("%d ",num[i]);
printf("%d",num[n]);
exit(0);
}
if(num[st[x][y]-'A'+1]!=-1)
{
if(x!=3) dfs(y,x+1,hi);
//当前位已经被填 向下搜索
else
{//在第三行时能保证当前列的第一行&第二行已经临时确定
int w=num[st[1][y]-'A'+1]+num[st[2][y]-'A'+1]+hi;
if(w%n!=num[st[3][y]-'A'+1]) return ;
dfs(y-1,1,w/n);
//向左边推进
}
}
else
{
for(int i=0;i<=n-1;i++)
if(!vis[i])
{
if(x==3)
{//搜到这里的时候保证第一行第二行都已经搜过
int w=num[st[1][y]-'A'+1]+num[st[2][y]-'A'+1]+hi;
if(w%n!=i) continue;
vis[i]=1;num[st[3][y]-'A'+1]=i;
dfs(y-1,1,w/n);
vis[i]=0;num[st[3][y]-'A'+1]=-1;
}
else
{
vis[i]=1;num[st[x][y]-'A'+1]=i;
dfs(y,x+1,hi);
vis[i]=0;num[st[x][y]-'A'+1]=-1;
}
}
}
}
int main()
{
scanf("%d",&n);
scanf("%s",st[1]+1);
scanf("%s",st[2]+1);
scanf("%s",st[3]+1);
memset(num,-1,sizeof(num));
dfs(n,1,0);
return 0;
}
强力剪枝
但是(T)了两个点，我们怎么办呢？可以加入两个强力剪枝。
①：在尝试放新的数字时，我们可能习惯从(0)~(n-1)放，但是如果从(n-1)到(0)放的话会快很多。为什么？小的数字更容易进到深层，如果不合法就会浪费很多时间；而大的数字容易引起回溯，但是不会引起结果的改变，所以这个剪枝可行。
②：我们真的要在状态都确定结束的时候才判断它是否合法吗？就不能边搜边判嘛？确定新数的时候我们肯定是保证它在当前状态下（眼前）是合法的，但是即使每次都合法，组在一起仍有可能不合法，因此，我们边搜边判。具体地说，就是每次搜的时候，看自己左边的列如果三行都确定的话，就检查下他们是否合法，这个剪枝还是很强的。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int num[30];
bool vis[30];
char st[4][30];
void dfs(int y,int x,int hi)
{
if(y==0)
{
if(hi!=0) return ;
for(int i=1;i<=n-1;i++) printf("%d ",num[i]);
printf("%d",num[n]);
exit(0);
}
for(int i=y-1;i>=1;i--)
{
int a=num[st[1][i]-'A'+1];
int b=num[st[2][i]-'A'+1];
int c=num[st[3][i]-'A'+1];
if(a==-1||b==-1||c==-1) continue ;
if((a+b)%n!=c&&(a+b+1)%n!=c) return ;
}
if(num[st[x][y]-'A'+1]!=-1)
{
if(x!=3) dfs(y,x+1,hi);
else
{
int w=num[st[1][y]-'A'+1]+num[st[2][y]-'A'+1]+hi;
if(w%n!=num[st[3][y]-'A'+1]) return ;
dfs(y-1,1,w/n);
}
}
else
{
for(int i=n-1;i>=0;i--)
if(!vis[i])
{
if(x==3)
{
int w=num[st[1][y]-'A'+1]+num[st[2][y]-'A'+1]+hi;
if(w%n!=i) continue;
vis[i]=1;num[st[3][y]-'A'+1]=i;
dfs(y-1,1,w/n);
vis[i]=0;num[st[3][y]-'A'+1]=-1;
}
else
{
vis[i]=1;num[st[x][y]-'A'+1]=i;
dfs(y,x+1,hi);
vis[i]=0;num[st[x][y]-'A'+1]=-1;
}
}
}
}
int main()
{
scanf("%d",&n);
scanf("%s",st[1]+1);
scanf("%s",st[2]+1);
scanf("%s",st[3]+1);
memset(num,-1,sizeof(num));
dfs(n,1,0);
return 0;
}
另一些细节
因为赋数字是从(0)到(n-1)的，所以初始值都要设成(-1)。回溯的时候也别习惯回成(0)。
注意下输出格式。