#include <iostream>
#include <stack>

using namespace std;

int x, i, j, i_0 = 0, j_0 = 0, dist[4], mindist, min_i;

stack <int> step;

struct matrix
{
	int arr[3][3];
};

struct Pair
{
	int x;
	int y;
};

Pair search(int a, int(&arr2)[3][3])
{
	Pair xy;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (arr2[i][j] == a)
			{
				xy.x = i;
				xy.y = j;
				return xy;
			}
}

int sum(int(&arr1)[3][3], int(&arr2)[3][3])
{
	int dist = 0;
	Pair arg;
	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
		{
			Pair arg = search(x, arr2);
			dist = dist + abs(arg.x - i) + abs(arg.y - j);
		}
	return dist;
}

int arr1[3][3]
{
	{ 1, 2, 3 },
	{ 8, 0, 4 },
	{ 7, 6, 5 }
};
int arr2[3][3]
{
	{5, 3, 4},
	{6, 0, 7},
	{8, 2, 1}
};

int main()
{/*
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cin >> arr1[i][j];
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cin >> arr2[i][j];*/
	while (arr1 != arr2)
	{
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if (arr1[i][j] == 0)
				{
					i_0 = i;
					j_0 = j;
					if (i_0 < 2)										//шаг вниз
					{
						swap(arr1[i_0][j_0], arr1[i_0 + 1][j_0]);
						dist[0] = sum(arr1, arr2);
						swap(arr1[i_0][j_0], arr1[i_0 + 1][j_0]);
						cout << endl;
						//for (int i = 0; i < 3; i++)
						//	for (int j = 0; j < 3; j++);
						//		/*cout << arr1[i][j];*/
					};
					if (i_0 > 0)										//шаг вверх
					{
						swap(arr1[i_0][j_0], arr1[i_0 - 1][j_0]);
						dist[1] = sum(arr1, arr2);
						swap(arr1[i_0][j_0], arr1[i_0 - 1][j_0]);
						cout << endl;
						//for (int i = 0; i < 3; i++)
						//	for (int j = 0; j < 3; j++);
						//		/*cout << arr1[i][j];*/
					}
					if (j_0 < 2)										//шаг вправо
					{
						swap(arr1[i_0][j_0], arr1[i_0][j_0 + 1]);
						dist[2] = sum(arr1, arr2);
						swap(arr1[i_0][j_0], arr1[i_0][j_0 + 1]);
						cout << endl;
						//for (int i = 0; i < 3; i++)
						//	for (int j = 0; j < 3; j++);
						//		/*cout << arr1[i][j];*/
					}
					if (j_0 > 0)										//шаг влево
					{
						swap(arr1[i_0][j_0], arr1[i_0][j_0 - 1]);
						dist[3] = sum(arr1, arr2);
						swap(arr1[i_0][j_0], arr1[i_0][j_0 - 1]);
						cout << endl;
						//for (int i = 0; i < 3; i++)
						//	for (int j = 0; j < 3; j++);
						//		/*cout << arr1[i][j];*/
					}
					cout << endl;
					for (int i = 0; i < 3; i++)
						for (int j = 0; j < 3; j++)
							cout << arr1[i][j];

					mindist = dist[0];
					for (int i = 1; i < 4; i++)
						if (dist[i] < mindist)
						{
							mindist = dist[i];
							min_i = i;
						}

					if (min_i == 0)
						swap(arr1[i_0][j_0], arr1[i_0 + 1][j_0]);
					if (min_i == 1)
						swap(arr1[i_0][j_0], arr1[i_0 - 1][j_0]);
					if (min_i == 2)
						swap(arr1[i_0][j_0], arr1[i_0][j_0 + 1]);
					if (min_i == 3)
						swap(arr1[i_0][j_0], arr1[i_0][j_0 - 1]);

					cout << endl;
					for (int i = 0; i < 3; i++)
						for (int j = 0; j < 3; j++)
							cout << arr1[i][j];
					/*matrix m;
					m.arr[3][3] = arr1[3][3];
					step.push(m.arr[3][3]);*/
				}
	}

	return 0;

}