BOJ 4574

#include <iostream>
#include <vector>
#include <cstring>
#define MAXN 10
using namespace std;

bool row[MAXN][MAXN];
bool col[MAXN][MAXN];
bool cross[MAXN][MAXN];
vector<pair<int,int> > v;
bool visited[MAXN][MAXN];
int state[MAXN][MAXN];
int N;
int total_cnt;
struct node{
    int x1;
    int y1;
    int x2;
    int y2;
};
node dirs[4] = { {0,0,0,1},{0,1,0,0},{0,0,1,0},{1,0,0,0} };
vector<bool> used;
bool flag;
void check_state(int x, int y, int num,bool mode){
    row[x][num] = mode;
    col[y][num] = mode;
    cross[3*(x/3)+y/3][num] = mode;
}
bool check(int x, int y, int num){
    if (row[x][num] || col[y][num] || cross[3*(x/3)+y/3][num]) return false;
    return true;
}
bool is_range(int x, int y){
    return !(x<0||y<0||x>=MAXN-1 || y >= MAXN-1 || state[x][y]!=0);
}
void backtrack(int x, int y, int cnt){
    if (flag) return;
    if (total_cnt == cnt){
        for (int i = 0; i < MAXN-1; i++){
            for (int j =0 ;j < MAXN-1; j++){
                cout << state[i][j];
            }
            cout <<"\n";
        }
        flag = true;
        return;
    }
    if (y == MAXN -1) {
        backtrack(x+1,0,cnt);
        return;
    }
    if (state[x][y]!=0) {
        backtrack(x,y+1,cnt);
        return;
    }
    for (int i = 0 ;i < 4; i++){
        int x1 = x + dirs[i].x1;
        int y1 = y + dirs[i].y1;
        int x2 = x + dirs[i].x2;
        int y2 = y + dirs[i].y2;
        if (!is_range(x1,y1)|| !is_range(x2,y2)) continue;
        for (int j = 0; j < v.size(); j++){
            if (used[j]) continue;
            int num1 = v[j].first;
            int num2 = v[j].second;
            if (!check(x1,y1,num1) || !check(x2,y2,num2)) continue;
            used[j] = true;
            check_state(x1,y1,num1,true);
            check_state(x2,y2,num2,true);
            state[x1][y1] = num1;
            state[x2][y2] = num2;
            // 가로로 채울경우 y+2
            if (i < 2) backtrack(x,y+2,cnt+1);
            // 세로로 채울 경우 y+1
            else backtrack(x,y+1,cnt+1);
            check_state(x1,y1,num1,false);
            check_state(x2,y2,num2,false);
            used[j] = false;
            state[x1][y1] = 0;
            state[x2][y2] = 0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t= 1;
    while (1){
        cin >> N;
        if (N ==0) break;
        flag = false;
        v.clear();
        memset(row,false,sizeof(row));
        memset(col,false,sizeof(col));
        memset(cross,false,sizeof(cross));
        memset(visited,false,sizeof(visited));
        memset(state,0,sizeof(state));
        for (int i = 0; i < N; i++){
            int num1,num2;
            string s1,s2;
            cin >> num1 >> s1 >> num2 >> s2;
            visited[num1][num2] = true;
            visited[num2][num1] = true;
            state[s1[0]-'A'][s1[1]-'0'-1] = num1;
            state[s2[0]-'A'][s2[1]-'0'-1] = num2;
            check_state(s1[0]-'A',s1[1]-'0'-1,num1,true);
            check_state(s2[0]-'A',s2[1]-'0'-1,num2,true);
        }
        for (int i = 1; i <= 9; i++){
            string s;
            cin >> s;
            state[s[0]-'A'][s[1]-'0'-1] = i;
            check_state(s[0]-'A',s[1]-'0'-1,i,true);
        }
        for (int i = 1; i < 9; i++){
            for (int j = i+1; j <= 9; j++){
                if (visited[i][j]) continue;
                v.push_back({i,j});
            }
        }
        total_cnt = v.size();
        used.resize(v.size(),false);

        cout << "Puzzle " << t << "\n";
        backtrack(0,0,0);
        t++;
    }
    return 0;
}