import java.util.*;

public class Puzzle {		
	// The goal array	 
	final int[][] goal = {
		{ 1, 2, 3 },
		{ 4, 5, 6 },
		{ 7, 8, 0 } 
	};
	int[][] number;//For the init set
	public Puzzle(int[][] n) {
		number = new int[3][3];		
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				number[i][j] = n[i][j];
	}
	public boolean	isSolved() {
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if (number[i][j] != goal[i][j]) return false;
		return true;
	}
	public Xy getXy(int n) {
		return getXy(n,number);
	}
	//Find number in given array
	public Xy getXy(int n, int[][] array) {
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if (array[i][j] == n) return new Xy(i, j);
		return new Xy(-1, -1);
	}
	public boolean legal(int n) {
		Xy blankXy = getXy(0);
		Xy numberXy = getXy(n);
		int dx = blankXy.x - numberXy.x;
		int dy = blankXy.y - numberXy.y;
		if (! (  (dx == 0 && Math.abs(dy)== 1)
			  || (dy == 0 && Math.abs(dx)== 1)))
			return false;
		return true;
	}
	public void	move(int n) {
		if (legal(n)) {
			Xy blankXy = getXy(0);
			Xy numberXy = getXy(n);
			//Swap
			number[blankXy.x][blankXy.y] = n;
			number[numberXy.x][numberXy.y] = 0;			
		}
	}
	public void	shuffle(int times) {
		Random random = new Random(System.currentTimeMillis());
		for (int i = 0; i < times; i++){
			int n = random.nextInt() % 8 + 1;
			if(legal(n))move(n);
				else i--;			
		}
	}
	public int numberAt(int i, int j) {
		return number[i][j];
	}
	public int	totalCost() {
		int total = 0;
		for (int i = 1; i <= 8; i++) {
			Xy puzzleXy = getXy(i);
			Xy goalXy = getXy(i, goal);

			total += Math.abs(puzzleXy.x - goalXy.x) 
			       + Math.abs(puzzleXy.y - goalXy.y);
		}
		return total;
	}
	public void	print() {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (number[i][j] > 0) {
					System.out.print(number[i][j] + " ");
				} else {
					System.out.print("  ");
				}
			}
			System.out.println();
		}
	}
	public void setNewNumber(int[][] num){
		number = num;
	}
}