import java.util.*;
 
class Vyjimka extends Exception {
	String message;
 
	Vyjimka(String m) {
		message = m;
	}
}
 
class Options {
	static int succeeded = 0;
	static int succeeded_hamming = 0;
	static int succeeded_manhattan = 0;
	static int failed = 0;
	static int total = 20;
	static boolean type = false; // false = manhattan, true = hamming
}
 
class VariantList {
 
	public static List<Variant> list = new ArrayList<Variant>();
	public static Integer shortest_path = null;
 
	public static void add(Variant v) {
//		System.out.println("Pridavam\n" + v.info());
		if (list.size() > 0) {
			for (int i = 0; i < list.size(); i++) {
				if (v.fnc() <= list.get(i).fnc()) {
					list.add(i, v);
					return;
				}
			}
		}
		list.add(v);
	}
 
	public static boolean all_checked() {
		Enumeration i = Collections.enumeration(list);
		while (i.hasMoreElements())
			if (((Variant)(i.nextElement())).checked != true)
				return false;
		return true;
	}
 
	public static Variant find_variant(Variant find) {
		Enumeration e = Collections.enumeration(list);
		while (e.hasMoreElements()) {
			Variant v = (Variant)(e.nextElement());
			for (int pos = 0; pos <= 9; pos++) {
				if (pos == 9) return v;
				String fromV = "" + v.tile.elementAt(pos);
				String fromFind = "" + find.tile.elementAt(pos);
				if (Integer.parseInt(fromV) != Integer.parseInt(fromFind))
					break;
			}
		}
		return null;
	}
 
}
 
class Variant {
 
	static Vector<Integer> final_tile = new Vector<Integer>();
	static int turns_max = 2000;
	static int turns_actual = 0;
 
	Vector<Integer> tile;
	boolean checked;
	Variant parent;
	Integer value;
 
	Variant(Vector<Integer> tile) {
		this.tile = (Vector<Integer>)tile.clone();
	}
 
	Variant(Variant parent, Vector<Integer> tile) throws Vyjimka
	{
		this.tile = (Vector<Integer>)tile.clone();
		this.checked = false;
		this.parent = parent;
		this.value = (parent != null) ? parent.value + 1 : 0;
 
		if (this.value > 50) {
//			System.out.println("Cesta delsi nez limit, koncim...");
			return;
		}
 
		if (VariantList.shortest_path != null)
			if (VariantList.shortest_path < value)
				return;
 
		Variant examined = VariantList.find_variant(this);
		if (examined != null) {
			if (this.value < examined.value) {
				examined.value = this.value;
				examined.parent = parent;
			}
//			System.out.println("Duplicitni, rusim hledani");
			return;
		}
 
		VariantList.add(this);
 
		if (this.is_solved()) {
			VariantList.shortest_path = this.value;
			this.print_path();
			throw new Vyjimka("");
		}
	}
 
	static Vector<Integer> swap(Vector<Integer> tile, int s1, int s2) {
		tile.set(s1, new Integer(tile.elementAt(s1) + tile.elementAt(s2)));
		tile.set(s2, new Integer(tile.elementAt(s1) - tile.elementAt(s2)));
		tile.set(s1, new Integer(tile.elementAt(s1) - tile.elementAt(s2)));
		return tile;
	}
 
	void negotiate_next() throws Vyjimka {
		int i = tile.indexOf(0); // index 0 v poli
		if (i != 0 && i != 3 && i != 6)
				negotiate_successor(tile, i, i-1);
		if (i != 2 && i != 5 && i != 8)
				negotiate_successor(tile, i, i+1);
		if (i != 0 && i != 1 && i != 2)
				negotiate_successor(tile, i, i-3);
		if (i != 6 && i != 7 && i != 8)
				negotiate_successor(tile, i, i+3);	
	}
 
	void negotiate_successor(Vector<Integer> prev_tile, int s1, int s2) throws Vyjimka {
		Vector<Integer> new_tile = Variant.swap((Vector<Integer>)prev_tile.clone(), s1, s2);
		Variant v = VariantList.find_variant(new Variant(new_tile));
		if (v == null)
			v = new Variant(this, new_tile);
	}
 
	boolean is_solved() {
		return (this.tile.elementAt(0) == 1 && this.tile.elementAt(1) == 2 && this.tile.elementAt(2) == 3 &&
		        this.tile.elementAt(3) == 8 && this.tile.elementAt(4) == 0 && this.tile.elementAt(5) == 4 &&
		        this.tile.elementAt(6) == 7 && this.tile.elementAt(7) == 6 && this.tile.elementAt(8) == 5);
	}
 
	void print_info() {
		System.out.println(info());
	}
 
	String info() {
		Enumeration e = tile.elements();
		int i = 0;
		String s = "";
		while (e.hasMoreElements()) {
			Integer n = ((Integer)(e.nextElement()));
			s += n;
			if (i == 2 || i == 5 || i == 8)
				s += "\n";
			else
				s += " ";
			i++;
		}
		return s;
	}
 
	Integer fnc() {
		return (Options.type == false) ? manhattan() : hamming();
	}
 
	Integer steps_between(int i, int j) {
		if (i == j )return 0;
		return Math.abs((i/3)-(j/3)) + Math.abs((i%3)-(j%3));
	}
 
	Integer manhattan() {
		int sum = 0;
		for (int i = 0; i <=8; i++) {
			sum += steps_between(this.tile.indexOf(i), Variant.final_tile.indexOf(i));
		}
		return sum;
	}
 
	Integer hamming() {
		int count = 0;
		for (int i = 0; i <=8; i++) {
			if (this.tile.elementAt(i) != Variant.final_tile.elementAt(i))
				count++;
		}
		return new Integer(count);
	}
 
	void print_path() {
		System.out.println("Delka: " + value);
		String path_string = "";
		Variant help = this;
		while (help.parent != null) {
			path_string = help.info() + "\n" + path_string;
			help = help.parent;
		}
		System.out.println("Cesta:\n" + path_string);
		System.out.println("Delka nalezene cesty: " + value + "\n");
	}
 
}
 
public class Game {
 
	public static void main(String[] args) {
 
		// LOOP BEGIN
		for (int i = Options.total; i > 0; i--) {
			System.out.println("Pokus cislo " + (20-i+1));
		// LOOP BEGIN
 
			// vytvoreni statickeho finaloveho vzoru
			Variant.final_tile.add(1);
			Variant.final_tile.add(2);
			Variant.final_tile.add(3);
			Variant.final_tile.add(8);
			Variant.final_tile.add(0);
			Variant.final_tile.add(4);
			Variant.final_tile.add(7);
			Variant.final_tile.add(6);
			Variant.final_tile.add(5);
 
			// vytvoreni nahodneho vzoru
			Vector v = new Vector();
			Random r = new Random();
//			v.add(8); v.add(1); v.add(3);
//			v.add(7); v.add(4); v.add(5);
//			v.add(6); v.add(2); v.add(0);
			v.add(1);
			v.add(r.nextInt(v.size()), 2);
			v.add(r.nextInt(v.size()), 3);
			v.add(r.nextInt(v.size()), 4);
			v.add(r.nextInt(v.size()), 5);
			v.add(r.nextInt(v.size()), 6);
			v.add(r.nextInt(v.size()), 7);
			v.add(r.nextInt(v.size()), 8);
			v.add(r.nextInt(v.size()), 0);
 
			System.out.print("Vzorec:\n" + new Variant(v).info());
 
			for (int j = 0; j <=1; j++) {
				try {
					Options.type = (Options.type == true) ? false : true;
					System.out.println("Funkce: " + (Options.type == false ? "Manhattan" : "Hamming"));
 
					Variant top = new Variant(null, v);
					while (true) {
 
						Variant.turns_actual++;
						if (Variant.turns_actual > Variant.turns_max) {
							System.out.println("Nenalezeno reseni po " + Variant.turns_max + " krocich, koncim...");
							break;
						}
 
//						if (VariantList.all_checked())
//							break;
//						System.out.println("Mam " + VariantList.list.size() + " variant");
						Enumeration e = Collections.enumeration(VariantList.list);
						while (e.hasMoreElements()) {
							Variant a = (Variant)(e.nextElement());
//							System.out.println("Vyjednavani z " + a.info());
							if (a.checked != true) {
								a.checked = true;
								try {a.negotiate_next();} catch (Vyjimka x) {System.out.println(x.message);return;}
								break;
							}
						}
					}
				} catch (Vyjimka x) {}
				finally {
					VariantList.list.clear();
					VariantList.shortest_path = null;
					Variant.turns_actual = 0;
					continue;
				}
			}
 
		// LOOP END
		}
		// LOOP END
	}
 
}