import java.io.*;
import java.util.*;
//主類
public class EightDigit{
	public static void main(String args[]){
		int a[][]=new int[3][3];//存放由文件讀入的初始狀態
		int judge[]=new int[9];//判斷逆序數所用數組
		int c=0;//初始狀態的逆序數對數
		Eight start=new Eight();//初始狀態結點
		try{
			BufferedReader reader;
			FileInputStream fi;
			StringBuffer sb=new StringBuffer();
			int p=0;
			while((p=System.in.read())!=13){//從命令行讀入文件名，暫存在一個字符串緩沖區，結束條件為讀入回車
				sb.append((char)p);
			}
			String name=new String(sb);//由字符串緩沖區中的字符序列新建一個字符串，代表讀入的文件名
			fi=new FileInputStream(name);
			reader=new BufferedReader(new InputStreamReader(fi));
			StringBuffer s;
			String str;	
			int n=0;
			int m=0;
			while((str=reader.readLine())!=null){//以行為單位讀入
				StringBuffer ss=new StringBuffer(str);
				//根據文件內容格式，分別將每一行代表數字的三個字符轉化為整型，存入數組相應位置
				a[n][0]=((int)ss.charAt(0))-48;
				a[n][1]=((int)ss.charAt(2))-48;
				a[n][2]=((int)ss.charAt(4))-48;
				//按順序存放在判斷逆序數的數組中
				judge[m]=a[n][0];
				judge[m+1]=a[n][1];
				judge[m+2]=a[n][2];
				n=n+1;
				m=m+3;
			}
			reader.close();//關閉流
			int loc=0;
			//尋找0在逆序數組中的位置
			for(int i=0;i<9;i++){
				if(judge[i]==0){
					loc=i;
				}
			}
			//將0忽略
			for(int i=loc;i<8;i++){
				judge[i]=judge[i+1];
			}
			//計算逆序數對數
			for(int i=0;i<7;i++){
				for(int j=i+1;j<8;j++){
					if(judge[i]>judge[j]){
						c++;
					}
				}
			}
			//目標狀態逆序數共奇數對，所以初始狀態若為偶數對，則無解，直接輸出no solution并返回
			if(c%2==0){
				System.out.println("no solution");
				return;
			}
			//建立初始結點
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					start.state[i][j]=a[i][j];
					if(a[i][j]==0){
						start.faX=i;
						start.faY=j;
					}
				}	
			}
			start.calculate_f();//計算初始結點的f值
			EightList open=new EightList();//建立open表
			EightList close=new EightList();//建立close表
			EightList son=new EightList();//擴展結點時用作暫存的表
			open.addLast(start);//初始結點存入open表
			Eight here=new Eight();//搜索過程中用到的臨時變量
			Eight temp1=new Eight();//同上
			Eight temp2=new Eight();//同上
			int depth=0;
			//搜索開始
			while(open.size()!=0){//結束條件：open表不空
				here=open.poll();//取出open表中第一個元素，并將之從open表中刪除
				if(here.h==0){//達到目標狀態條件：h函數值為0（此處h函數定義為不在位的將牌數）
					here.listall();//達到目標狀態時輸出整個路徑
					System.out.println("total steps:"+here.f);//輸出總步數，即目標狀態的f值
					return;//返回
				}
				//未達到目標狀態
				son=here.expand();//對于取出的結點進行擴展，暫存入son表中
				int count=son.size();//得到擴展出的結點個數
				if(count==0)continue;//無新擴展結點，則繼續循環
				else{//否則對于每個擴展出來的結點進行判斷
					for(int i=0;i<count;i++){
						temp1=son.get(i);//暫存當前擴展出的結點
						if(!open.contains(temp1)&&!close.contains(temp1)){//如果該結點在open表和close表中都不存在
							open.insert(temp1);//將新結點插入到open表相應位置（根據f值判斷）
						}
						else if(open.contains(temp1)){//若open表中已有表示該狀態的結點
							int pos=open.indexOf(temp1);
							temp2=open.get(pos);//取出open表中相同狀態的結點
							if(temp1.f<temp2.f){//比較兩者f值的大小，將小者重新存入open表，大者忽略
								open.remove(temp2);//將原結點從open表中刪除
								open.insert(temp1);//將新結點加入open表中
							}
						}
						else if(close.contains(temp1)){//若在close表中有表示該狀態的結點
							int pos=close.indexOf(temp1);
							temp2=close.get(pos);//取出close表中相同狀態的結點
							if(temp1.f<temp2.f){//若當前結點的f值比close表中表示相同狀態的結點的f值小
								close.remove(temp1);//則將原結點其從close表中刪除
								open.insert(temp1);//將新結點加入open表
							}
						}
					}
					close.addLast(here);//將此次擴展的結點加入到close表中
				}
				
			}
			System.out.println("no solution");//open表空，未找到解，輸出無解
			return;
			}catch(FileNotFoundException e){//異常處理
			System.out.println("Catch "+e);
			}catch(IOException i){//異常處理
			System.out.println("Catch "+i);
			}
	}
}

//八數碼狀態結點類
class Eight{
	int state[][]=new int[3][3];//保存當前的八數碼狀態
	static int dest[][]={{1,2,3},{8,0,4},{7,6,5}};//標準狀態
	int faX,faY;//記錄0所在位置
	int f;//估計函數值
	int h;//h函數值
	Eight former;//當前狀態的前一狀態
	//構造函數，將所有值初始化
	Eight(){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				state[i][j]=0;
			}
		}
		faX=-1;
		faY=-1;
		f=-1;
		h=-1;
		former=null;
	}
	//拷貝構造函數，將對應的狀態結點拷貝到當前新結點
	Eight(Eight other){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				state[i][j]=other.state[i][j];
			}
		}
		faX=other.faX;
		faY=other.faY;
		f=other.f;
		h=other.h;
		former=other.former;
	}
	//輸出當前結點
	public void print(){
		for(int i=0;i<3;i++){ 
			for(int j=0;j<3;j++){ 
				System.out.print(state[i][j]+" ");
			}
			System.out.println(); 
		}
		System.out.println();
	}
	//計算f函數值
	public void calculate_f(){
		h=0;//將當前結點的h函數先清0
		for(int i=0;i<3;i++){//對于所有位置上的數字進行掃描，若與目標狀態不同，則將h函數值加1
			for(int j=0;j<3;j++){
				if(state[i][j]!=dest[i][j]){
					h++;
				}
			}
		}
		if(this.former!=null){//若存在父結點，則g函數的值為其父結點f函數與h函數之差加1（因為每條路徑的耗散值均為1），而當前f函數值即g+h
			f=h+this.former.f-this.former.h+1;
		}
		else f=h;//若不存在父結點，即初始結點，則f=h
	}
	//按順序列出所有步數
	public void listall(){
		Eight e=new Eight(this);
		if(e.former.former!=null){//判斷當前結點的父結點是否為第一步，若不是，遞歸輸出前一結點
			e.former.listall();
		}
		e.print();//輸出當前結點
	}
	//對當前結點擴展，返回一個存放擴展出的所有結點的sons表
	public EightList expand(){
		EightList sons=new EightList();//初始化sons表
		//每一步最多擴展出四個結點
		Eight son1=new Eight(this);
		Eight son2=new Eight(this);
		Eight son3=new Eight(this);
		Eight son4=new Eight(this);
		//羅列所有0可能在的位置，對每一種情況列出其所有的擴展結點狀態，并記錄新的0位，記錄其父結點，并計算其對應的f值，最后加入到sons表中
		if(faX==0&&faY==0){//0在第一行第一列，則有兩個擴展結點，分別是將第一行第二列的左移，與將第二行第一列的上移
			son1.state[0][0]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][0]=this.state[1][0];
			son2.state[1][0]=0;
			son2.faX=1;
			son2.faY=0;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==0&&faY==1){//0在第一行第二列，有三個擴展結點，為第一行第一列右移，第一行第三列左移和第二行第二列上移
			son1.state[0][1]=this.state[0][0];
			son1.state[0][0]=0;
			son1.faX=0;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][1]=this.state[0][2];
			son2.state[0][2]=0;
			son2.faX=0;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[0][1]=this.state[1][1];
			son3.state[1][1]=0;
			son3.faX=1;
			son3.faY=1;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==0&&faY==2){//0在第一行第三列，有兩個擴展結點，為第一行第二列右移和第二行第三列上移
			son1.state[0][2]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][2]=this.state[1][2];
			son2.state[1][2]=0;
			son2.faX=1;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==1&&faY==0){//0在第二行第一列，有三個擴展結點，為第一行第一列下移，第二行第二列左移和第三行第一列上移
			son1.state[1][0]=this.state[0][0];
			son1.state[0][0]=0;
			son1.faX=0;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][0]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][0]=this.state[2][0];
			son3.state[2][0]=0;
			son3.faX=2;
			son3.faY=0;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==1&&faY==1){//0在第二行第二列，有四個擴展結點，為第一行第二列下移，第二行第一列右移，第二行第三列左移和第三行第二列上移
			son1.state[1][1]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][1]=this.state[1][0];
			son2.state[1][0]=0;
			son2.faX=1;
			son2.faY=0;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][1]=this.state[1][2];
			son3.state[1][2]=0;
			son3.faX=1;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
			son4.state[1][1]=this.state[2][1];
			son4.state[2][1]=0;
			son4.faX=2;
			son4.faY=1;
			son4.former=this;
			son4.calculate_f();
			sons.addLast(son4);
		}
		else if(faX==1&&faY==2){//0在第二行第三列，有三個擴展結點，為第一行第三列下移，第二行第二列右移和第三行第三列上移
			son1.state[1][2]=this.state[0][2];
			son1.state[0][2]=0;
			son1.faX=0;
			son1.faY=2;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][2]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][2]=this.state[2][2];
			son3.state[2][2]=0;
			son3.faX=2;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==2&&faY==0){//0在第三行第一列，有兩個擴展結點，為第二行第一列下移和第三行第二列左移
			son1.state[2][0]=this.state[1][0];
			son1.state[2][0]=0;
			son1.faX=2;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][0]=this.state[2][1];
			son2.state[2][1]=0;
			son2.faX=2;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==2&&faY==1){//0在第三行第二列，有三個擴展結點，為第三行第一列右移，第三行第三列左移和第二行第二列下移
			son1.state[2][1]=this.state[2][0];
			son1.state[2][0]=0;
			son1.faX=2;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][1]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[2][1]=this.state[2][2];
			son3.state[2][2]=0;
			son3.faX=2;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==2&&faY==2){//0在第三行第三列，有兩個擴展結點，為第三行第二列右移和第二行第三列下移
			son1.state[2][2]=this.state[2][1];
			son1.state[2][1]=0;
			son1.faX=2;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][2]=this.state[1][2];
			son2.state[1][2]=0;
			son2.faX=1;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		return sons;
	}
	//判斷兩個結點的狀態是否相同，相同返回true，否則false
	public boolean equals(Eight e){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(state[i][j]!=e.state[i][j]){
					return false;
				}
			}
		}
		return true;
	}
}

//列表類，用來存放八數碼問題中的結點
class EightList{
	Eight ee[]=new Eight[181440];
	private int size;
	//構造函數，初始化大小為0
	EightList(){
		size=0;
	}
	//往表的最后添加指定元素
	public void addLast(Eight e){
		ee[size]=e;
		size++;
	}
	//判斷該表是否包含指定的狀態結點，是返回true，否則false
	public boolean contains(Eight e){
		if(size==0){
			return false;
		}
		else{
			for(int i=0;i<size;i++){
				if(ee[i].equals(e)){
					return true;
				}
			}
			return false;
		}
	}
	//取出并刪除表中的第一個元素，返回該元素
	public Eight poll(){
		Eight e=ee[0];
		for(int i=0;i<size-1;i++){
			ee[i]=ee[i+1];
		}
		size--;
		return e;
	}
	//獲得該表的大小
	public int size(){
		return size;
	}
	//得到表中指定位置的元素
	public Eight get(int pos){
		return ee[pos];
	}
	//查找表中指定元素所在的位置
	public int indexOf(Eight e){
		for(int i=0;i<size;i++){
			if(ee[i].equals(e)){
				return i;
			}
		}
		return -1;
	}
	//刪除表中某個元素，同時將其后所有元素前移一位，表的大小減一。若不存在該元素，則直接返回
	public void remove(Eight e){
		int pos=-1;
		for(int i=0;i<size;i++){
			if(ee[i].equals(e)){
				pos=i;
				break;
			}
		}
		if(pos==-1)return;
		for(int i=pos;i<size-1;i++){
			ee[i]=ee[i+1];
		}
		size--;
	}
	//插入函數，將新結點根據其f值插入到相應位置
	public void insert(Eight e){
		int pos=size;
		Eight temp1=new Eight();
		Eight temp2=new Eight();
		temp2=e;
		for(int i=0;i<size;i++){
			if(e.f<=ee[i].f){
				pos=i;
				break;
			}
		}
		size++;
		for(int i=pos;i<size;i++){
			temp1=ee[i];
			ee[i]=temp2;
			temp2=temp1;
		}
	}
	
}