class tilePuzzle
{
 public static void main(String[] args) 
 {
    int current=0;
    int numNode=500;
    int goalFound = 0;
    int zeroSpot = 0;
    int expandedNode = current;
    int [][] initialState = new int[numNode][9];
    int [][] goalState= new int[1][9];
    int [] fArray = new int[numNode];
    int [] aMove = new int[numNode];
    aMove[0]=4;
    int aMoveFlag = 0;
    
    goalState[0][0]=2;
    goalState[0][1]=8;
    goalState[0][2]=3;
    goalState[0][3]=4;
    goalState[0][4]=5;
    goalState[0][5]=6;
    goalState[0][6]=0;
    goalState[0][7]=7; 
    goalState[0][8]=1;   
    
    initialState[0][0]=2;
    initialState[0][1]=8;
    initialState[0][2]=3;
    initialState[0][3]=4;
    initialState[0][4]=5;
    initialState[0][5]=0;
    initialState[0][6]=7;
    initialState[0][7]=1; 
    initialState[0][8]=6;
    
    if(initialState[current][0]!=goalState[0][0]) 
    { fArray[current]=fArray[current] +1;}
    if(initialState[current][1]!=goalState[0][1]) 
    { fArray[current]=fArray[current] +1;}		
   	if(initialState[current][2]!=goalState[0][2])
   	{ fArray[current]=fArray[current] +1;}
    if(initialState[current][3]!=goalState[0][3])
    { fArray[current]=fArray[current] +1;}
	if(initialState[current][4]!=goalState[0][4])
	{ fArray[current]=fArray[current] +1;}
   	if(initialState[current][5]!=goalState[0][5])
   	{ fArray[current]=fArray[current] +1;}
   	if(initialState[current][6]!=goalState[0][6])
   	{ fArray[current]=fArray[current] +1;}
   	if(initialState[current][7]!=goalState[0][7])
   	{ fArray[current]=fArray[current] +1;}
   			
   	int count=0;
   			
    do
    {
    

    	if (fArray[expandedNode] == 0) {goalFound = 1;}
    	
    
    	
    
    	if (goalFound == 0)
    	{
    
    
    		
    	
    		for(int h=0;h<9;h++)
    		{
    			if (initialState[expandedNode][h] == 0) {zeroSpot=h;}
    		}
    		 
    	
    			if ( zeroSpot != 0 &&zeroSpot != 6 &&zeroSpot != 7 && aMove[expandedNode]!=2)
    			{
    				
    				for(int j=0;j<9;j++)
    				{
    					initialState[current+1][j]=initialState[expandedNode][j];
    				}
    				
    				
    				current=current+1;
    				aMove[current]=0;
    				
    				
    				if (zeroSpot == 1) 
    				{
    					initialState[current][zeroSpot] = initialState[current][0];
    					initialState[current][0] = 0;
    				}
    				if (zeroSpot == 2) 
    				{
    					initialState[current][zeroSpot] = initialState[current][1];
    					initialState[current][1] = 0;
    				}
    				if (zeroSpot == 3) 
    				{
    					initialState[current][zeroSpot] = initialState[current][8];
    					initialState[current][8] = 0;
    				}
    				if (zeroSpot == 4) 
    				{
    					initialState[current][zeroSpot] = initialState[current][5];
    					initialState[current][5] = 0;
    				}
    				if (zeroSpot == 5) 
    				{
    					initialState[current][zeroSpot] = initialState[current][6];
    					initialState[current][6] = 0;
    				}
    				if (zeroSpot == 8) 
    				{
    					initialState[current][zeroSpot] = initialState[current][7];
    					initialState[current][7] = 0;
    				}
    			
    		
    		if(initialState[current][0]!=goalState[0][0]) 
    		{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][1]!=goalState[0][1]) 
    		{ fArray[current]=fArray[current] +1;}		
   			if(initialState[current][2]!=goalState[0][2])
   			{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][3]!=goalState[0][3])
    		{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][4]!=goalState[0][4])
    		{ fArray[current]=fArray[current] +1;}
			if(initialState[current][5]!=goalState[0][5])
			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][6]!=goalState[0][6])
   			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][7]!=goalState[0][7])
   			{ fArray[current]=fArray[current] +1;}
   			
   		}
    		
    			
   
    			if ( zeroSpot != 0 &&zeroSpot != 1 &&zeroSpot != 2 && aMove[expandedNode]!=3)
    			{
    				
    				for(int j=0;j<9;j++)
    				{
    					initialState[current+1][j]=initialState[expandedNode][j];
    				}
    				
    				
    				current=current+1;
    				
    				aMove[current]=1;
    				
    				
    				if (zeroSpot == 3) 
    				{
    					initialState[current][zeroSpot] = initialState[current][2];
    					initialState[current][2] = 0;
    				}
    				if (zeroSpot == 4) 
    				{
    					initialState[current][zeroSpot] = initialState[current][3];
    					initialState[current][3] = 0;
    				}
    				if (zeroSpot == 5) 
    				{
    					initialState[current][zeroSpot] = initialState[current][8];
    					initialState[current][8] = 0;
    				}
    				if (zeroSpot == 6) 
    				{
    					initialState[current][zeroSpot] = initialState[current][7];
    					initialState[current][7] = 0;
    				}
    				if (zeroSpot == 7) 
    				{
    					initialState[current][zeroSpot] = initialState[current][8];
    					initialState[current][8] = 0;
    				}
    				if (zeroSpot == 8) 
    				{
    					initialState[current][zeroSpot] = initialState[current][1];
    					initialState[current][1] = 0;
    				}
    			
    		
    		if(initialState[current][0]!=goalState[0][0]) 
    		{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][1]!=goalState[0][1]) 
    		{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][2]!=goalState[0][2])
    		{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][3]!=goalState[0][3])
   			{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][4]!=goalState[0][4])
    		{ fArray[current]=fArray[current] +1;}
			if(initialState[current][5]!=goalState[0][5])
			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][6]!=goalState[0][6])
   			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][7]!=goalState[0][7])
   			{ fArray[current]=fArray[current] +1;}
   			
   		}
    	
    			if ( zeroSpot != 2 &&zeroSpot != 3 &&zeroSpot != 4 && aMove[expandedNode]!=0)
    			{
    				//replicate current initialState
    				for(int j=0;j<9;j++)
    				{
    					initialState[current+1][j]=initialState[expandedNode][j];
    				}
    				
    				//add 1 to current
    				current=current+1;
    				//set move for this move to right=2
    				aMove[current]=2;
    				
    				//move replicated new initialState left
    				if (zeroSpot == 0) 
    				{
    					initialState[current][zeroSpot] = initialState[current][1];
    					initialState[current][1] = 0;
    				}
    				if (zeroSpot == 1) 
    				{
    					initialState[current][zeroSpot] = initialState[current][2];
    					initialState[current][2] = 0;
    				}
    				if (zeroSpot == 5) 
    				{
    					initialState[current][zeroSpot] = initialState[current][4];
    					initialState[current][4] = 0;
    				}
    				if (zeroSpot == 6) 
    				{
    					initialState[current][zeroSpot] = initialState[current][5];
    					initialState[current][5] = 0;
    				}
    				if (zeroSpot == 7) 
    				{
    					initialState[current][zeroSpot] = initialState[current][8];
    					initialState[current][8] = 0;
    				}
    				if (zeroSpot == 8) 
    				{
    					initialState[current][zeroSpot] = initialState[current][3];
    					initialState[current][3] = 0;
    				}
    			
    		// calculate f(n)
    		if(initialState[current][0]!=goalState[0][0]) 
    		{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][1]!=goalState[0][1]) 
    		{ fArray[current]=fArray[current] +1;}		
   			if(initialState[current][2]!=goalState[0][2])
   			{ fArray[current]=fArray[current] +1;}
    		if(initialState[current][3]!=goalState[0][3])
    		{ fArray[current]=fArray[current] +1;}
			if(initialState[current][4]!=goalState[0][4])
			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][5]!=goalState[0][5])
   			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][6]!=goalState[0][6])
   			{ fArray[current]=fArray[current] +1;}
   			if(initialState[current][7]!=goalState[0][7])
   			{ fArray[current]=fArray[current] +1;}
   		}//end of check right if initialStatement
   		
    		//check down
    		//make sure the zero is not in spot that cannont move down
    		//and make sure that the previous move was not up so 
    		//that a move down will not incur the previous initialState
    			if ( zeroSpot != 4 &&zeroSpot != 5 &&zeroSpot != 6 && aMove[expandedNode]!=1)
    			{
    				//replicate current initialState
    				for(int j=0;j<9;j++)
    				{
    					initialState[current+1][j]=initialState[expandedNode][j];
    				}
    				
    				//add 1 to current
    				current=current+1;
    				//set move for this move to down=3
    				aMove[current]=3;
    				
    				//move replicated new initialState left
    				if (zeroSpot == 0) 
    				{
    					initialState[current][zeroSpot] = initialState[current][7];
    					initialState[current][7] = 0;
    				}
    				if (zeroSpot == 1) 
    				{
    					initialState[current][zeroSpot] = initialState[current][8];
    					initialState[current][8] = 0;
    				}
    				if (zeroSpot == 2) 
    				{
    					initialState[current][zeroSpot] = initialState[current][3];
    					initialState[current][3] = 0;
    				}
    				if (zeroSpot == 3) 
    				{
    					initialState[current][zeroSpot] = initialState[current][4];
    					initialState[current][4] = 0;
    				}
    				if (zeroSpot == 7) 
    				{
    					initialState[current][zeroSpot] = initialState[current][6];
    					initialState[current][6] = 0;
    				}
    				if (zeroSpot == 8) 
    				{
    					initialState[current][zeroSpot] = initialState[current][5];
    					initialState[current][5] = 0;
    				}
    			
    		// calculate f(n)
    		if(initialState[current][0]!=goalState[0][0]) { fArray[current]=fArray[current] +1;
    		}
    		if(initialState[current][1]!=goalState[0][1]) { fArray[current]=fArray[current] +1;
    		}		
   			if(initialState[current][2]!=goalState[0][2]){ fArray[current]=fArray[current] +1;
   			}
    		if(initialState[current][3]!=goalState[0][3]){ fArray[current]=fArray[current] +1;
    		}
			if(initialState[current][4]!=goalState[0][4]){ fArray[current]=fArray[current] +1;
			}
   			if(initialState[current][5]!=goalState[0][5]){ fArray[current]=fArray[current] +1;
   			}
   			if(initialState[current][6]!=goalState[0][6]){ fArray[current]=fArray[current] +1;
   			}
   			if(initialState[current][7]!=goalState[0][7]){ fArray[current]=fArray[current] +1;
   			}
   		}//end of check down if initialStatement	
   		
   	
    				
    		//find smallest f(n)
    		int smallest=500;	
    		int fSmallest=0;
    		//NOT TO numNode BUT TO HIGHEST	
    	System.out.println("Smallest"+smallest);
    		for(int h=0;h<current+1;h++)
    		//for(int h=0;h<numNode;h++)
    		{
    		
    		System.out.println("h: "+ h);
    		System.out.println("fArray[h]: "+fArray[h]);
    		
    		if(fArray[h] < smallest ) 
    			{ 
    				smallest=fArray[h];
    				fSmallest=h;
    			}
    			System.out.println("Smallest"+smallest);
    		
    			if(fArray[h] != 0)
    			{
    				
    				if (fArray[h] < smallest) 
    				{ 
    					System.out.println("fArray[h]"+fArray[h]);
    					System.out.println("h"+h);
    					smallest=fArray[h];
    					fSmallest=h;
    				}
    			}
    		}
    		
    		System.out.println("Smallest"+smallest);
    		//finds the smallest f(n) and then uses that
    		//node to expand
    		expandedNode = fSmallest;
    		System.out.println("ExpandedNode num in array"+expandedNode);
    		//goalFound = 1;
    		System.out.println("they weren't equal but set to 1.");
    		
    	}
   
   if (count==1){goalFound = 1;}
   	if (fArray[expandedNode] == 0) {goalFound = 1;}
   count=count+1;
    }
    while(goalFound==0);
 }
}
//need to change f(n) calculations to add in g(n)
//need to change so that can repeat-highest in array num

//CHANGE FN SEE ABOVE
//REMEMBER TO CHECK H NOT F IF WANT TO END AND LET GOALFOUND=1
//AND HAVE ALREADY EXPANDED ARRAY AND IF IN LOOP THE SMALLEST IS
//ALREADY EXPANDED THEN PICK ANOTHER