#include <bits/stdc++.h>
using namespace std;
const int N=15, M=150;
struct node{
    int id, e[5];
} a[M]; // 0上 1右 2下 3左
int n, m, S, w[N][N], b[N][N]; bool v[M];
bool cmp(node n1, node n2){
    return n1.id < n2.id;
}
int calc(int x, int y){
    return (x-1)*m + y;
}
bool jd1(int x, int y, int i, int j){
    int t1=w[x-1][y], t2=w[x][y-1];
    if(a[i].e[j] != a[b[x-1][y]].e[(w[x-1][y]+2)%4] && x>1) return 0; 
    if(a[i].e[(j+3)%4] != a[b[x][y-1]].e[(w[x][y-1]+1)%4] && y>1) return 0; 
    return 1;
}
bool jd2(int x, int y, int i, int j){
    if(x != 1 && a[i].e[j%4] == 0) return 0; 
    if(x == 1 && a[i].e[j%4] != 0) return 0; 
    if(y == 1 && a[i].e[(j+3)%4] != 0) return 0; 
    if(y != 1 && a[i].e[(j+3)%4] == 0) return 0; 
    if(x != n && a[i].e[(j+2)%4] == 0) return 0; 
    if(x == n && a[i].e[(j+2)%4] != 0) return 0; 	
    if(y == m && a[i].e[(j+1)%4] != 0) return 0; 
    if(y != m && a[i].e[(j+1)%4] == 0) return 0; 
    return 1;}
bool dfs(int x, int y){
    if(y > m){
        return dfs(x+1, 1);
    }
    if(x > n){
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){
                printf("%d ", a[b[i][j]].id);
                for(int k=0; k<4; k++){
                    int d = a[b[i][j]].e[(k + w[i][j])%4];
                    if(d == 0) printf("0 ");
                    else printf("%c ", d + 'a' - 1);
                }
                printf("\n");
            }
        return 1;
    }
    for(int i=1; i<=S; i++) if(!v[i]){
        for(int j=0; j<4; j++){
            if(jd1(x, y, i, j) && jd2(x, y, i, j)){
                w[x][y] = j; b[x][y] = i; v[i] = 1;
                if(dfs(x, y+1)) return 1;
                w[x][y] = 0; b[x][y] = 0; v[i] = 0;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d", &n, &m); S = n*m;
    for(int i=1; i<=S; i++){
        char s[5]; scanf("%d", &a[i].id);
        for(int j=0; j<4; j++){
            scanf("%s", s);
            if(s[0] == '0') a[i].e[j] = 0;
            else a[i].e[j] = s[0] - 'a' + 1;
        }
    }
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));
    memset(b, 0, sizeof(b));
    sort(a+1, a+S+1, cmp);;
    bool flag = dfs(1, 1);
    return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=15, M=150;
struct node{
	int id, e[5];
} a[M]; // 0上 1右 2下 3左
int n, m, S, w[N][N], b[N][N]; bool v[M];
bool cmp(node n1, node n2){
	return n1.id<n2.id;
}
int calc(int x, int y){
	return (x-1)*m+y;
}
bool jd1(int x, int y, int i, int j){
	int t1=w[x-1][y], t2=w[x][y-1];
	if(a[i].e[j]!=a[b[x-1][y]].e[(w[x-1][y]+2)%4] && x>1) return 0; 
	if(a[i].e[(j+3)%4]!=a[b[x][y-1]].e[(w[x][y-1]+1)%4] && y>1) return 0; 
	return 1;
}
bool jd2(int x, int y, int i, int j){
	if(x!=1 && a[i].e[j%4]==0) return 0; 
	if(x==1 && a[i].e[j%4]!=0) return 0; 
	if(y==1 && a[i].e[(j+3)%4]!=0) return 0; 
	if(y!=1 && a[i].e[(j+3)%4]==0) return 0; 
	if(x!=n && a[i].e[(j+2)%4]==0) return 0; 
	if(x==n && a[i].e[(j+2)%4]!=0) return 0; 	
	if(y==m && a[i].e[(j+1)%4]!=0) return 0; 
	if(y!=m && a[i].e[(j+1)%4]==0) return 0; 
	return 1;
}
bool dfs(int x, int y){
	if(y>m){
		return dfs(x+1, 1);
	}
	if(x>n){
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++){
				printf("%d ", a[b[i][j]].id);
				for(int k=0; k<4; k++){
					int d=a[b[i][j]].e[(k+w[i][j])%4];
					if(d==0) printf("0 ");
					else printf("%c ", d+'a'-1);
				}
				printf("\n");
			}
		return 1;
	}
	for(int i=1; i<=S; i++) if(!v[i]){
		for(int j=0; j<4; j++){
			if(jd1(x, y, i, j) && jd2(x, y, i, j)){
				w[x][y]=j; b[x][y]=i; v[i]=1;
				if(dfs(x, y+1)) return 1;
				w[x][y]=0; b[x][y]=0; v[i]=0;
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d%d", &n, &m); S=n*m;
	for(int i=1; i<=S; i++){
		char s[5]; scanf("%d", &a[i].id);
		for(int j=0; j<4; j++){
			scanf("%s", s);
			if(s[0]=='0') a[i].e[j]=0;
			else a[i].e[j]=s[0]-'a'+1;
		}
	}
	memset(v, 0, sizeof(v));
	memset(w, 0, sizeof(w));
	memset(b, 0, sizeof(b));
	sort(a+1, a+S+1, cmp);;
	bool flag=dfs(1, 1);
	return 0;
}