#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

#include <stdio.h>
#include <time.h>
using namespace std;

int dx[] = { 1, -1, 3, -3 };

map<string, int> strtoind;
map<int, string> indtostr;

string ansstr = "XAMELEON.";
int index = 0;
int cntdiff(string s) {
	int firstlet = -1, firstmeet = -1;
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != ansstr[i]) {
			int ind = 0;
			for (int j = 0; ansstr.size(); j++) {
				if (ansstr[j] == s[i]) {
					if (s[i] == 'E') {
						if (firstmeet == 1 && i > firstlet) {
							ind = j;
							break;
						}
						else {
							firstmeet = 1;
							firstlet = i;
							ind = j;
							break;
						}
					}
					ind = j;
					break;
				}
			}

			cnt += abs(ind % 3 - i % 3) + abs(ind / 3 - i / 3);
		}
	}
	return cnt;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first)
		return a.second > b.second;
	else return a.first > b.first;
}
void bfs(string cur, vector<int>& p, vector<int>& was, vector<int>& steps) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, bool(*)(pair<int, int>, pair<int, int>)> pq(cmp);
	if (strtoind.count(cur) == 0) {
		strtoind[cur] = index;
		indtostr[index] =cur;
		index++;
		was.push_back(0);
		p.push_back(0);
		steps.push_back(0);
	}
	was[strtoind[cur]] = 1;

	pq.push({ cntdiff(cur), strtoind[cur] });

	while (!pq.empty()) {
		auto po = pq.top();
		pq.pop();
		int ind = po.second;
		int x = -1;
		cur = indtostr[ind];
		for (int i = 0; i < 9; i++) {

			if (cur[i] == '.') {
				x = i;
				break;
			}

		}
		//cout << "q.front = " << indtostr[ind] << endl;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			if (nx >= 0 && nx < 9) {
				if (x % 3 == 2 && dx[i] == 1 || x % 3 == 0 && dx[i] == -1)
					continue;
				string t = cur;

				swap(t[x], t[nx]);
				if (strtoind.count(t) == 0) {
					strtoind[t] = index;
					indtostr[index] = t;
					index++;
					was.push_back(0);
					p.push_back(0);
					steps.push_back(0);
				}
				int nind = strtoind[t];
				if (!was[nind]) {
					//cout << "new string t = " << t;
					was[nind] = 1;
					pq.push({ cntdiff(t), nind });
					p[nind] = strtoind[cur];
					//cout << "   p[nind] = " << p[nind] << "     ";
					steps[nind] = steps[strtoind[cur]] + 1;
					//cout << "   steps[nind] = " << steps[nind] << endl;
					if (t == ansstr)
						return;
				}
			}
		}
	}
}

int main() {

	indtostr[0] = ansstr;
	strtoind[ansstr] = 0;
	index++;

	cout << "Enter the combination:\n";

	vector<int> pred(index), was(index), steps(index);

	string t;
	for (int i = 0; i < 3; i++) {
		string te;
		cin >> te;
		t += te;
	}
	if (t == ansstr) {
		cout << "That's the answer";
		return 0;
	}
	clock_t start = clock();
	bfs(t, pred, was, steps);

	if (steps[strtoind[ansstr]] == 0) {
		cout << "No solution";
		return 0;
	}

	vector<int> ans;

	index = strtoind[ansstr];

	while (index != strtoind[t]) {
		ans.push_back(index);
		index = pred[index];
	}

	reverse(begin(ans), end(ans));


	for (int i = 0; i < ans.size(); i++) {
		string t = indtostr[ans[i]];
		for (int i = 0; i < 9; i += 3) {
			for (int j = 0; j < 3; j++)
				cout << t[i + j];
			cout << endl;
		}
		cout << endl;
	}

	clock_t end = clock();
	double seconds = (double)(end - start) / CLOCKS_PER_SEC;
	cout << "time: " << seconds << endl << endl;
	cout << "You need " <<  steps[strtoind[ansstr]] << " step(s)" << endl;


	return 0;
}