模拟+dfs
这个题就三行，搜索的话我们从右向左，从上到下。。
如果是在1，2行我们就直接枚举0～n所有数，但是到了第三行，最直接的就是填上这一列上前两行的数的和modN，在此基础上判断该填的数有没有被使用
如果没有被使用，且这个地方没有被赋值，就可以把要填的数填上去，如果被填了切符合要求，就不需要填数了。。注意每次填数都要维护下一列进位的值以及回溯
有一个非常重要的剪枝就是：对于一个竖式a+b=c，如果(a+b)modn != c 且 (a + b + 1)modn != c,那么这个竖式就是错的，可以直接返回
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
int n, num[40], cnt, c[40];
bool vis[40], flag;
char s[4][40];
bool check(int col){
for(int i = col - 1; i >= 1; i --){
if(num[s[1][i] - 'A' + 1] != -1 && num[s[2][i] - 'A' + 1] != -1 && num[s[3][i] - 'A' + 1] != -1){
int a = num[s[1][i] - 'A' + 1], b = num[s[2][i] - 'A' + 1];
int d = num[s[3][i] - 'A' + 1];
if((a + b) % n != d && (a + b + 1) % n != d) return false;
}
}
return true;
}
void dfs(int row, int col){
//cout << row << " " << col << endl;
if(flag) return;
if(cnt == n || (col == 0 && c[col] == 0)){
flag = true;
for(int i = 1; i <= n; i ++) printf("%d ", num[i]);
puts("");
return;
}
if(row != 3){
if(num[s[row][col] - 'A' + 1] == -1){
for(int i = 0; i < n; i ++){
if(vis[i]) continue;
vis[i] = true, num[s[row][col] - 'A' + 1] = i, cnt ++;
if(check(col)) dfs(row + 1, col);
vis[i] = false, num[s[row][col] - 'A' + 1] = -1, cnt --;
}
}
else dfs(row + 1, col);
}
else{
int a = num[s[1][col] - 'A' + 1], b = num[s[2][col] - 'A' + 1];
int d = (a + b + c[col]) % n;
if(num[s[row][col] - 'A' + 1] == -1){
if(vis[d]) return;
vis[d] = true, num[s[row][col] - 'A' + 1] = d, c[col - 1] = (a + b + c[col]) / n, cnt ++;
if(check(col)) dfs(1, col - 1);
vis[d] = false, num[s[row][col] - 'A' + 1] = -1, c[col - 1] = 0, cnt --;
}
else{
if(num[s[row][col] - 'A' + 1] != d) return;
c[col - 1] = (a + b + c[col]) / n;
if(check(col)) dfs(1, col - 1);
c[col - 1] = 0;
}
}
}
int main(){
n = read();
for(int i = 1; i <= 3; i ++) scanf("%s", s[i] + 1);
flag = false, memset(num, -1, sizeof num);
dfs(1, n);
return 0;
}