実は、「 各行 / 各列 に A, B, C がちょうど 1 個ずつ含まれる 」を満たすグリッドは \(N=5\) の場合でも \(66240\) 個しか存在しません。
なので、様々な方針の枝刈り全探索でこの問題に正解することができます。この解説ではその一例を示します。

以下、 \(N=5\) であったとして説明します。
まず、行の制約のみに着目します。このとき、以下の \(2\) つの条件を守ることになります。

• 全ての行は ABC.. の並べ替えである
• 上から \(i\) 行目の最も左にある . 以外の文字は \(R_i\) である

各行についてこれを満たすものは \(20\) 通りしかありません。 ( \((5 \times 4 \times 3 )/ 3 = 20\) )
これを \(5\) 行分試すことを考えます (合計 \(20^5\) 通り)
上の行から順に決定していくことを考えます。このとき、以下の条件に違反してはなりません。

• 各列は A, B, C を高々 \(1\) つずつ含む。
• 左から \(j\) 列目の最も上にある . 以外の文字は \(C_j\) である

これに違反したことが発覚した時点で、そこで探索を打ち切って構いません。
そうして \(N\) 行全てが決まった場合、最後に以下をチェックします。

• 各行は A, B, C を丁度 \(1\) つ含む。

この条件も満たしていれば、そのグリッドは問題文中の条件を全て満たしています。

この解法中で演算を行う回数は高々 \(20^5 \times 5^2 = 8 \times 10^7 \times \) ( 小さな定数倍 ) 回程度と見積もれますが、実際は非常に高速に動作します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

vector<vector<string>> row(3);
bool fnd=false;
int n;
string r,c;
vector<string> grid;

void dfs(int i,int fl){
  if(fnd){return;}
  if(i==n){
    if(fl==0){
      cout << "Yes\n";
      for(auto &nx : grid){cout << nx << "\n";}
      fnd=true;
    }
    return;
  }
  for(auto &nx : row[r[i]-'A']){
    grid.push_back(nx);

    int ufl=fl;
    bool und=true;
    for(int j=0;j<n;j++){
      if(nx[j]=='.'){continue;}
      int kind=(nx[j]-'A');
      if((fl&(1<<(4*j+kind)))==0){und=false;break;}
      ufl^=(1<<(4*j+kind));
      if((fl&(1<<(4*j+3)))!=0){
        if(nx[j]!=c[j]){und=false;break;}
        ufl^=(1<<(4*j+3));
      }
    }

    if(und){dfs(i+1,ufl);}
    grid.pop_back();
  }
}

int main(){
  cin >> n >> r >> c;
  string abc="ABC";
  while(abc.size()<n){abc.push_back('.');}
  sort(abc.begin(),abc.end());
  do{
    char tg='.';
    for(auto &nx : abc){
      if(nx!='.'){tg=nx;break;}
    }
    row[tg-'A'].push_back(abc);
  }while(next_permutation(abc.begin(),abc.end()));

  dfs(0,(1<<(4*n))-1);
  if(!fnd){cout << "No\n";}
  return 0;
}