题解 P4205 【[NOI2005]智慧珠游戏 】
我的第一道黑题，写篇题解纪念一下。
…………这个题目其实并不是太难…………（蒟蒻我都能AC的黑题）
算法应该很好想到，就是暴力的搜索（好像时间复杂度不是太高，我的程序321ms过）不过要注意的一点是存图时要把整个三角形沿斜边的高翻折交换一波（我不会告诉你这其实是我们老师说的）
剩下的就是暴力的深度搜索啦，码量贼大，但没什么技巧，认真点把所有情况都打完就行，千万别打错，三百多行的程序真心不好改
打完长舒一口气，我有些地方错了，但居然能有九十分，不知是数据太水还是怎么地，大家最好别复制代码，自己写一下也是极大的提升，磨炼耐心与毅力。
下面是完整代码
#include<bits/stdc++.h>
#define FOR(i,a,b) for (register int i=a;i<=b;i++)
using namespace std;
const int n=10;
int tu[15][15];
bool used[15];
void print() {
for (int i=1,k=1; i<=n; i++) {
FOR(j,1,k)
swap(tu[i][j],tu[11-j][11-i]);
if (i<=4) k++;
else k--;
}
FOR(i,1,n) {
FOR(j,1,i)
printf("%c",tu[i][j]+'A'-1);
printf("\n");
}
exit(0);
}
void dfs(int x,int y) {
while(tu[x][y]) {
y++;
if (x<y) x++,y=1;
if (x>n) {
print();
return;
}
}
if ((!used[12])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x][y+3])&&(!tu[x+1][y])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])&&(!tu[x+1][y+3])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+1][y+3]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+1][y+3]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+3][y])&&(!tu[x+3][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=tu[x+3][y+1]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=tu[x+3][y+1]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+3][y-1])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y-1]=tu[x+3][y]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y-1]=tu[x+3][y]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x+1][y-3])&&(!tu[x+1][y-2])&&(!tu[x+1][y-1])&&(!tu[x+1][y])) {
tu[x][y]=tu[x+1][y-3]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-3]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x][y+3])&&(!tu[x+1][y+3])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+3]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+3]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x][y+1])&&(!tu[x+1][y+1])&&(!tu[x+2][y+1])&&(!tu[x+3][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+3][y+1]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+3][y+1]=0,used[12]=0;
}
if ((!used[12])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+3][y])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=12,used[12]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=0,used[12]=0;
}
if ((!used[11])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y+1])&&(!tu[x+2][y+2])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+2][y+2]=11,used[11]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+2][y+2]=0,used[11]=0;
}
if ((!used[11])&&(!tu[x+1][y])&&(!tu[x+1][y-1])&&(!tu[x+2][y-1])&&(!tu[x+2][y-2])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y-1]=tu[x+2][y-1]=tu[x+2][y-2]=11,used[11]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y-1]=tu[x+2][y-1]=tu[x+2][y-2]=0,used[11]=0;
}
if ((!used[11])&&(!tu[x][y-1])&&(!tu[x+1][y-1])&&(!tu[x+1][y-2])&&(!tu[x+2][y-2])) {
tu[x][y]=tu[x][y-1]=tu[x+1][y-1]=tu[x+1][y-2]=tu[x+2][y-2]=11,used[11]=1;
dfs(x,y);
tu[x][y]=tu[x][y-1]=tu[x+1][y-1]=tu[x+1][y-2]=tu[x+2][y-2]=0,used[11]=0;
}
if ((!used[11])&&(!tu[x][y+1])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])&&(!tu[x+2][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+2][y+2]=11,used[11]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+2][y+2]=0,used[11]=0;
}
if (!(used[10])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=10,used[10]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=0,used[10]=0;
}
if ((!used[9])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y+2])&&(!tu[x+1][y+3])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=tu[x+1][y+3]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=tu[x+1][y+3]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x][y+1])&&(!tu[x+1][y-2])&&(!tu[x+1][y-1])&&(!tu[x+1][y])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+2][y-1])&&(!tu[x+3][y-1])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y-1]=tu[x+3][y-1]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y-1]=tu[x+3][y-1]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y+1])&&(!tu[x+3][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+3][y+1]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=tu[x+3][y+1]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x][y+1])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])&&(!tu[x+1][y+3])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+1][y+3]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+1][y+2]=tu[x+1][y+3]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y-1])&&(!tu[x+1][y])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y-1]=tu[x+1][y]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y-1]=tu[x+1][y]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x+1][y])&&(!tu[x+2][y-1])&&(!tu[x+2][y])&&(!tu[x+3][y-1])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=tu[x+3][y-1]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=tu[x+3][y-1]=0,used[9]=0;
}
if ((!used[9])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+2][y+1])&&(!tu[x+3][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+3][y+1]=9,used[9]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+3][y+1]=0,used[9]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+1]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+1]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=tu[x+2][y+1]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=tu[x+2][y+1]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+2][y-1])&&(!tu[x+2][y])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+1]=tu[x+1][y+2]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+1]=tu[x+1][y+2]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y+1]=0,used[8]=0;
}
if ((!used[8])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=8,used[8]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=0,used[8]=0;
}
if ((!used[7])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+2]=7,used[7]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+2]=0,used[7]=0;
}
if ((!used[7])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=7,used[7]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=0,used[7]=0;
}
if ((!used[7])&&(!tu[x][y+2])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=7,used[7]=1;
dfs(x,y);
tu[x][y]=tu[x][y+2]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=0,used[7]=0;
}
if ((!used[7])&&(!tu[x][y+1])&&(!tu[x+1][y+1])&&(!tu[x+2][y])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y]=tu[x+2][y+1]=7,used[7]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y]=tu[x+2][y+1]=0,used[7]=0;
}
if ((!used[6])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x][y+3])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+1]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+1]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x][y+3])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+2]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=tu[x+1][y+2]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y-2])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=tu[x+1][y+1]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+2][y])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=tu[x+3][y]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+2][y]=tu[x+3][y]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y-1])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+2][y+1])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+3][y]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+3][y]=0,used[6]=0;
}
if ((!used[6])&&(!tu[x+1][y])&&(!tu[x+2][y-1])&&(!tu[x+2][y])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=tu[x+3][y]=6,used[6]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=tu[x+3][y]=0,used[6]=0;
}
if ((!used[5])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y])&&(!tu[x+2][y])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+2][y]=5,used[5]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=tu[x+2][y]=0,used[5]=0;
}
if ((!used[5])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y+2])&&(!tu[x+2][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=tu[x+2][y+2]=5,used[5]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=tu[x+2][y+2]=0,used[5]=0;
}
if ((!used[5])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+2][y+1])&&(!tu[x+2][y+2])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+2][y+2]=5,used[5]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=tu[x+2][y+2]=0,used[5]=0;
}
if ((!used[5])&&(!tu[x+1][y])&&(!tu[x+2][y-2])&&(!tu[x+2][y-1])&&(!tu[x+2][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y-2]=tu[x+2][y-1]=tu[x+2][y]=5,used[5]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y-2]=tu[x+2][y-1]=tu[x+2][y]=0,used[5]=0;
}
if ((!used[4])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=4,used[4]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+1][y+1]=0,used[4]=0;
}
if ((!used[3])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x+1][y])&&(!tu[x+1][y+1])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=tu[x+1][y+2]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+2][y+1]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x+1][y])&&(!tu[x+2][y-1])&&(!tu[x+2][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y-1]=tu[x+2][y]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x+1][y-2])&&(!tu[x+1][y-1])&&(!tu[x+1][y])) {
tu[x][y]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-2]=tu[x+1][y-1]=tu[x+1][y]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x+1][y+2])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x+1][y+2]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x][y+1])&&(!tu[x+1][y+1])&&(!tu[x+2][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y+1]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=tu[x+2][y+1]=0,used[3]=0;
}
if ((!used[3])&&(!tu[x][y+1])&&(!tu[x+1][y])&&(!tu[x+2][y])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=3,used[3]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y]=tu[x+2][y]=0,used[3]=0;
}
if ((!used[2])&&(!tu[x][y+1])&&(!tu[x][y+2])&&(!tu[x][y+3])) {
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=2,used[2]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x][y+2]=tu[x][y+3]=0,used[2]=0;
}
if ((!used[2])&&(!tu[x+1][y])&&(!tu[x+2][y])&&(!tu[x+3][y])) {
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=2,used[2]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+2][y]=tu[x+3][y]=0,used[2]=0;
}
if ((!used[1])&&(!tu[x+1][y])&&(!tu[x][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x][y+1]=1,used[1]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x][y+1]=0,used[1]=0;
}
if ((!used[1])&&(!tu[x][y+1])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=1,used[1]=1;
dfs(x,y);
tu[x][y]=tu[x][y+1]=tu[x+1][y+1]=0,used[1]=0;
}
if ((!used[1])&&(!tu[x+1][y])&&(!tu[x+1][y+1])) {
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=1,used[1]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y]=tu[x+1][y+1]=0,used[1]=0;
}
if ((!used[1])&&(!tu[x+1][y-1])&&(!tu[x+1][y])) {
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=1,used[1]=1;
dfs(x,y);
tu[x][y]=tu[x+1][y-1]=tu[x+1][y]=0,used[1]=0;
}
}
int main() {
char ch;
memset(tu,127,sizeof(tu));
FOR(i,1,n)FOR(j,1,i) {
ch=getchar();
while ((ch!='.')&&((ch<'A')||(ch>'L'))) ch=getchar();
if (ch=='.') tu[i][j]=0;
else tu[i][j]=ch-'A'+1,used[tu[i][j]]=1;
}
for (int i=1,k=1; i<=n; i++) {
for (int j=1; j<=k; j++)
swap(tu[i][j],tu[11-j][11-i]);
if (i<=4)k++;
else k--;
}
dfs(1,1);
printf("No solution");
return 0;
}