说明

本题要求解决一个由九块拼图组成的谜题，每块拼图的四边都有图片的半边。目标是将这些拼图排列成一个3x3的网格，使得相邻边的图片能够匹配。中间的拼图必须保持原始方向，其他拼图可以旋转。程序需要找到所有可能的解法，若存在唯一解则输出，否则提示多种解法或无解。

算法标签

回溯算法：通过深度优先搜索尝试所有可能的拼图组合。

哈希映射：快速查找匹配的拼图边。

模拟旋转：处理拼图的四种旋转状态。

解题思路 旋转处理：每块拼图可旋转四次，生成不同方向的边排列。

映射表构建：为每个边（顶、右、底、左）建立哈希映射，记录所有可能的拼图旋转实例。

中心枚举：遍历每块拼图作为中心，保持其原始方向。

邻边匹配：根据中心拼图的边，找到上下左右四个相邻拼图的候选。

角落匹配：进一步处理四个角落的拼图，确保所有边匹配且拼图唯一使用。

解验证：若找到所有九块拼图的唯一组合，则输出解；否则继续搜索。

分析

旋转生成：每个拼图有四个旋转状态，对应不同的边排列顺序。

边匹配规则：相邻拼图的边必须为对应的左右半部分（如BL匹配BR）。

剪枝策略：通过哈希映射快速筛选候选拼图，减少无效搜索。

唯一性检查：使用集合跟踪已使用的拼图，确保每块仅用一次。

实现步骤

输入解析：读取每个问题的九块拼图信息。

旋转生成：为每块拼图生成四种旋转状态。

哈希映射构建：记录每个边对应的所有拼图旋转实例。

中心拼图遍历：尝试每块拼图作为中心，保持其原始方向。

邻边匹配：根据中心拼图的边，查找上下左右四个位置的候选拼图。

角落处理：通过多层循环匹配四个角落的拼图，确保所有边满足条件。

解输出：若找到唯一解，按格式输出；否则提示无解或多解。

代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

struct Rotation {
	int piece_id;
	int rot;
	string top;
	string right;
	string bottom;
	string left;
};

vector<Rotation> rotations[9];
unordered_map<string, vector<Rotation>> top_map, right_map, bottom_map, left_map;

string get_matching_edge(string edge) {
	if (edge.size() != 2) return "";
	char c = edge[0];
	char lr = edge[1];
	if (lr == 'L') return string(1, c) + "R";
	else return string(1, c) + "L";
}

void generate_rotations(int id, string t, string r, string b, string l) {
	rotations[id].clear();
	rotations[id].push_back({id, 0, t, r, b, l});
	rotations[id].push_back({id, 1, l, t, r, b});
	rotations[id].push_back({id, 2, b, l, t, r});
	rotations[id].push_back({id, 3, r, b, l, t});
}

void build_maps() {
	top_map.clear();
	right_map.clear();
	bottom_map.clear();
	left_map.clear();
	for (int i = 0; i < 9; ++i) {
		for (auto &rot : rotations[i]) {
			top_map[rot.top].push_back(rot);
			right_map[rot.right].push_back(rot);
			bottom_map[rot.bottom].push_back(rot);
			left_map[rot.left].push_back(rot);
		}
	}
}

void print_solution(vector<vector<Rotation>> &grid) {
	for (int row = 0; row < 3; ++row) {
		for (int line = 0; line < 3; ++line) {
			for (int col = 0; col < 3; ++col) {
				Rotation r = grid[row][col];
				if (line == 0) {
					cout << "   " << r.top << "  ";
				} else if (line == 1) {
					cout << r.left << " " << (r.piece_id + 1) << " " << r.right;
				} else {
					cout << "   " << r.bottom << "  ";
				}
				if (col != 2) cout << " ";
			}
			cout << endl;
		}
		if (row != 2) cout << endl;
	}
}

void solve(int problem_num) {
	bool found = false;
	vector<vector<Rotation>> grid(3, vector<Rotation>(3));
	
	for (int center = 0; center < 9; ++center) {
		if (rotations[center].empty()) continue;
		Rotation center_rot = rotations[center][0];
		string T = center_rot.top;
		string R = center_rot.right;
		string B = center_rot.bottom;
		string L = center_rot.left;
		
		string T_match = get_matching_edge(T);
		string R_match = get_matching_edge(R);
		string B_match = get_matching_edge(B);
		string L_match = get_matching_edge(L);
		
		vector<Rotation> up_candidates = bottom_map[T_match];
		for (auto &up_rot : up_candidates) {
			if (up_rot.piece_id == center) continue;
			set<int> used = {center, up_rot.piece_id};
			
			vector<Rotation> right_candidates = left_map[R_match];
			for (auto &right_rot : right_candidates) {
				if (used.count(right_rot.piece_id)) continue;
				used.insert(right_rot.piece_id);
				
				vector<Rotation> down_candidates = top_map[B_match];
				for (auto &down_rot : down_candidates) {
					if (used.count(down_rot.piece_id)) continue;
					used.insert(down_rot.piece_id);
					
					vector<Rotation> left_candidates = right_map[L_match];
					for (auto &left_rot : left_candidates) {
						if (used.count(left_rot.piece_id)) continue;
						used.insert(left_rot.piece_id);
						
						string upper_left_right = get_matching_edge(up_rot.left);
						string upper_left_bottom = get_matching_edge(left_rot.top);
						vector<Rotation> ul_candidates = right_map[upper_left_right];
						for (auto &ul_rot : ul_candidates) {
							if (used.count(ul_rot.piece_id) || ul_rot.bottom != upper_left_bottom) continue;
							used.insert(ul_rot.piece_id);
							
							string upper_right_left = get_matching_edge(up_rot.right);
							string upper_right_bottom = get_matching_edge(right_rot.top);
							vector<Rotation> ur_candidates = left_map[upper_right_left];
							for (auto &ur_rot : ur_candidates) {
								if (used.count(ur_rot.piece_id) || ur_rot.bottom != upper_right_bottom) continue;
								used.insert(ur_rot.piece_id);
								
								string lower_right_left = get_matching_edge(down_rot.right);
								string lower_right_top = get_matching_edge(right_rot.bottom);
								vector<Rotation> lr_candidates = left_map[lower_right_left];
								for (auto &lr_rot : lr_candidates) {
									if (used.count(lr_rot.piece_id) || lr_rot.top != lower_right_top) continue;
									used.insert(lr_rot.piece_id);
									
									string lower_left_right = get_matching_edge(down_rot.left);
									string lower_left_top = get_matching_edge(left_rot.bottom);
									vector<Rotation> ll_candidates = right_map[lower_left_right];
									for (auto &ll_rot : ll_candidates) {
										if (used.count(ll_rot.piece_id) || ll_rot.top != lower_left_top) continue;
										used.insert(ll_rot.piece_id);
										
										if (used.size() == 9) {
											grid[1][1] = center_rot;
											grid[0][1] = up_rot;
											grid[1][2] = right_rot;
											grid[2][1] = down_rot;
											grid[1][0] = left_rot;
											grid[0][0] = ul_rot;
											grid[0][2] = ur_rot;
											grid[2][2] = lr_rot;
											grid[2][0] = ll_rot;
											
											cout << problem_num << ":" << endl;
											print_solution(grid);
											cout << endl;
											found = true;
											return;
										}
										used.erase(ll_rot.piece_id);
									}
									used.erase(lr_rot.piece_id);
								}
								used.erase(ur_rot.piece_id);
							}
							used.erase(ul_rot.piece_id);
						}
						used.erase(left_rot.piece_id);
					}
					used.erase(down_rot.piece_id);
				}
				used.erase(right_rot.piece_id);
			}
			used.erase(up_rot.piece_id);
		}
	}
	
	if (!found) {
		cout << problem_num << ":" << endl;
		cout << "No Solution" << endl << endl;
	}
}

int main() {
	int problem_num = 1;
	while (true) {
		cin >> problem_num;
		if (problem_num == 0) break;
		
		for (int i = 0; i < 9; ++i) {
			int id;
			string t, r, b, l;
			cin >> id >> t >> r >> b >> l;
			generate_rotations(id-1, t, r, b, l);
		}
		
		build_maps();
		
		solve(problem_num);
	}
	
	return 0;
}