public class State {
	
private int[]  state = new int[9];
private int size = 1;
private State[] expendStates;

public State(int[] s){
  int i;
  for(i=0;i<9;i++){
  state[i] = s[i];
  }
}

public State(String t){
  if(t.equals("d")){
	  state = new int[]{2,8,3,1,0,4,7,6,5};
  }
  else if(t.equals("d1")){
	  state = new int[]{2,8,0,1,3,4,7,6,5};
  }
}//默認初始數組*******************測試用

public boolean equals(State st){
	
	int[] s = st.getState();
	for(int i=0;i<9;i++){
		if(s[i]!=state[i])return false;
	}
	return true;
}//判斷狀態是否相同

public int[] getState(){
	return state;
}//返回state數組

public int getBlank(){
	for(int i = 0;i<9;i++){
		if(state[i]==0)return i;
	}
	return -1;
}//返回空格的位置

public int expandSize(){
	//有三種情況
	//當空格在中間時，有四種可能的移動
	//當空格在四個角上時，有二種可能的移動
	//當空格在四邊上時，有三種可能的移動
	if(state[4]==0) size = 4;
	else if(state[0]==0 || state[2]==0 || state[6]==0 || state[8]==0) size = 2;
	else size = 3;
	expendStates = new State[size];
	return size;
}

public State[] expandState(){

	int[] exState = getState().clone();
	int[] temp = getState().clone();
	expendStates[0] = new State(temp);//初始化數組
	
    if(size == 1) expandSize();
    int blank = getBlank();
    
	if(size == 4){//當空格在中間時，size = 4，空格的位置是4
		//上格下移
		temp[4] = temp[1];
		temp[1] = 0;
		expendStates[0] = new State(temp);
		//左格右移
		temp = exState.clone();
		temp[4] = temp[3];
		temp[3] = 0;
		expendStates[1] = new State(temp);
		//下格上移
		temp = exState.clone();
		temp[4] = temp[7];
		temp[7] = 0;
		expendStates[2] = new State(temp);
		//右格左移
		temp = exState.clone();
		temp[4] = temp[5];
		temp[5] = 0;
		expendStates[3] = new State(temp);
	}
	
	else if(size == 2){	//當空格在四個角上時，有二種可能的移動,size =2，空格的位置是0，2，6，8
		if(blank == 0){//當空格在左上角時
			//右格左移
			temp = exState.clone();
			temp[0] = temp[1];
			temp[1] = 0;
			expendStates[0] = new State(temp);
			//下格上移
			temp = exState.clone();
			temp[0] = temp[3];
			temp[3] = 0;
			expendStates[1] = new State(temp);
		}
		else if(blank == 2){//當空格在右上角時
			//左格右移
			temp = exState.clone();
			temp[2] = temp[1];
			temp[1] = 0;
			expendStates[0] = new State(temp);
			//下格上移
			temp = exState.clone();
			temp[2] = temp[5];
			temp[5] = 0;
			expendStates[1] = new State(temp);
		}
		else if(blank == 6){//當空格在左下角時
			//右格左移
			temp = exState.clone();
			temp[6] = temp[7];
			temp[7] = 0;
			expendStates[0] = new State(temp);
			//上格下移
			temp = exState.clone();
			temp[6] = temp[3];
			temp[3] = 0;
			expendStates[1] = new State(temp);
		}
		else if(blank == 8){//當空格在右下角時
			//左格右移
			temp = exState.clone();
			temp[8] = temp[7];
			temp[7] = 0;
			expendStates[0] = new State(temp);
			//上格下移
			temp = exState.clone();
			temp[8] = temp[5];
			temp[5] = 0;
			expendStates[1] = new State(temp);
		}
	}
	
	//temp = exState;
	else if(size == 3){	//當空格在四個邊上時，有三種可能的移動,size =3，空格的位置是1，3，5，7
		if(blank == 1){//當空格在上邊時
			//下格上移
			temp = exState.clone();
			temp[1] = temp[4];
			temp[4] = 0;
			expendStates[0] = new State(temp);
			//左格右移
			temp = exState.clone();
			temp[1] = temp[0];
			temp[0] = 0;
			expendStates[1] = new State(temp);
			//右格左移
			temp = exState.clone();
			temp[1] = temp[2];
			temp[2] = 0;
			expendStates[2] = new State(temp);
		}
		else if(blank == 3){//當空格在左邊時
			//上格下移
			temp = exState.clone();
			temp[3] = temp[0];
			temp[0] = 0;
			expendStates[0] = new State(temp);
			//右格左移
			temp = exState.clone();
			temp[3] = temp[4];
			temp[4] = 0;
			expendStates[1] = new State(temp);
			//下格上移
			temp = exState.clone();
			temp[3] = temp[6];
			temp[6] = 0;
			expendStates[2] = new State(temp);
		}
		else if(blank == 5){//當空格在右邊時
			//上格下移
			temp = exState.clone();
			temp[5] = temp[2];
			temp[2] = 0;
			expendStates[0] = new State(temp);
			//左格右移
			temp = exState.clone();
			temp[5] = temp[4];
			temp[4] = 0;
			expendStates[1] = new State(temp);
			//下格上移
			temp = exState.clone();
			temp[5] = temp[8];
			temp[8] = 0;
			expendStates[2] = new State(temp);
		}
		else if(blank == 7){//當空格在下邊時
			//上格下移
			temp = exState.clone();
			temp[7] = temp[4];
			temp[4] = 0;
			expendStates[0] = new State(temp);
			//左格右移
			temp = exState.clone();
			temp[7] = temp[6];
			temp[6] = 0;
			expendStates[1] = new State(temp);
			//右格左移
			temp = exState.clone();
			temp[7] = temp[8];
			temp[8] = 0;
			expendStates[2] = new State(temp);
		}
	}
	
	return expendStates;
}

public void printState(){
	System.out.println();
	for(int i=0;i<9;i++){
		System.out.print(state[i]+"  ");
		if(i%3==2&&i!=0)System.out.println();
	}
	System.out.println();
}//打印狀態

public int moveTo(State st){
	int[] s = st.getState();
	int i;
	for(i=0;i<9;i++ )
	{
	if(s[i] != state[i] && s[i]!=0)
	return i;
	}
	return -1;
}//返回移動后的棋子的位置


}