searchtree.java

用A star

import java.util.LinkedList;


public class SearchTree 
{
	LinkedList open, closed;
	boolean trace = true;
	
	public SearchTree()		//init
	{
	}
	
	void setTrace(boolean in)
	{
		trace = in;
	}
	
	int scoreBoard(int[] board)		//score computation - bad evaluation of board
	{
		int score=0;
		for(int i=0; i<9;i++)
		{
			if(board[i]==i)
				score++;
		}
		return score;
	}
	
	LinkedList genSucc(int[] board)			//generate successors of current board
	{
		LinkedList out;
		out = new LinkedList();
		int[] newboard = new int[9];
		System.arraycopy(board,0,newboard,0,9);
		int pos=0;
		while(board[pos]!=0)				//look at position of 0 piece
			pos++;							
											//look at possible moves and create legal boards
		if((pos-3)>=0)						
		{
			newboard[pos]=newboard[pos-3];
			newboard[pos-3]=0;
			out.add(new int[9]);
			System.arraycopy(newboard,0,out.getLast(),0,9);
			System.arraycopy(board,0,newboard,0,9);
		}
		if(pos%3!=0)
		{
			newboard[pos]=newboard[pos-1];
			newboard[pos-1]=0;
			out.add(new int[9]);
			System.arraycopy(newboard,0,out.getLast(),0,9);
			System.arraycopy(board,0,newboard,0,9);
		}
		if(pos%3!=2)
		{
			newboard[pos]=newboard[pos+1];
			newboard[pos+1]=0;
			out.add(new int[9]);
			System.arraycopy(newboard,0,out.getLast(),0,9);
			System.arraycopy(board,0,newboard,0,9);
		}
		if((pos+3)<9)
		{
			newboard[pos]=newboard[pos+3];
			newboard[pos+3]=0;
			out.add(new int[9]);
			System.arraycopy(newboard,0,out.getLast(),0,9);
		}
		return out;
	}	
	
	void valsort(LinkedList inlist)   //do bubblesort according to scores on both lists
	{
		int[] tmp = new int[11];
		int n=inlist.size();
		for(int i=0; i<n-1; i++) 
		{
		  for(int j=0; j<n-1-i; j++)
			if(((int[])inlist.get(j+1))[9] > ((int[])inlist.get(j))[9]) 
			{
			  	tmp = (int[]) inlist.get(j);
			  	inlist.set(j,(int[]) inlist.get(j+1));
			  	inlist.set(j+1, tmp);
		    }
		}
	}
	
	int contains(LinkedList in1, int[] in2)   //check if in2 is somewhere in in1, return position
	{
		boolean val = true;
		int[] temp = new int[9];
		for(int i=0; i<in1.size(); i++)
		{
			System.arraycopy((int[])in1.get(i),0,temp,0,9);
			for(int j=0; j<9;j++)
			{
				val = val && (in2[j]==temp[j]);
			}
			if(val)
				return i;
			else
				val = true;
		}
		return -1;
	}
	
	void printsc(LinkedList inlist)			//print boards scores in open
	{
		int n=inlist.size();
		
		if(n>0)
		{			
			System.out.print("Next Scores:");
			for(int i=0; i<n && i<15; i++) 
			{		  
				System.out.print(" " + ((int[])inlist.get(i))[9]); 
			}
			System.out.print("\n");
		}
	}	
	
	void print(LinkedList in)			//print boards from in
	{
		int[] temp;
		for(int i=0; i<in.size(); i++)
		{
			temp = (int[])in.get(i);
			for(int j=0; j<9;j++)
			{
				if(j%3==0)
					System.out.print("\n");
				System.out.print(temp[j]+" ");
			}
			System.out.print("\n");
		}
	}
	
	public int[] bfs(int[] board, int cutoff)			// do best first search
	{
		int[] data = new int[3];	//time and boards
		data[0] = data[1] = 0;
		
		open = new LinkedList();		//search lists
		closed = new LinkedList();
		
		int[] x = new int[11];			//current board
		int[] temp = new int[11];		//comparison board
		
		System.arraycopy(board,0,x,0,9);
		int score = scoreBoard(x);
		
		int[] time = new int[1];		//temporal time
		time[0] = 0;
		
		LinkedList succ = new LinkedList();	//successors and their number
		int noofsucc = 0;
		
		x[9]= score;			//update score and time on board
		x[10]=data[0];
		
		open.add(new int[11]);				//add first board to open queue
		System.arraycopy(x, 0, open.getLast(),0,11);		
		
		int cfound, ofound = -1;	//locations for found items in open/closed
		
		while (open.size()!=0)
		{
			data[0]++;	//increase time
							
			System.arraycopy(open.getFirst(),0,x,0,11);	// look at first board in open list & get score

			if(x[9]==9)				//found goal board, success, print boards, return info
			{
				System.arraycopy(x,0,board,0,9);
				print(closed);
				data[2]=x[10];
				return data;			
			}
			
			if(trace)
			{
				printsc(open);
				System.out.println("Time: " + data[0] + "  Size of open: " + open.size() + "  Size of closed: " + closed.size());
			}
			
			if(data[0]>cutoff-1)				//failed due to time limit
			{	
				data[0]=data[0]*-1;
				return data;
			}				
			else						//otherwise generate possible moves and check them
			{
				succ = genSucc(x);		
				noofsucc = succ.size();
				data[1] += noofsucc;	//update boards expanded
				
				if(trace)
					System.out.print("Successors: ");
				
				for(int i=0; i<noofsucc; i++)
				{
					System.arraycopy(succ.get(i),0,temp,0,9);
					ofound = contains(open, temp);
					cfound = contains(closed, temp);
					
					if((ofound==-1) && (cfound==-1))	//if not looked at so far
					{
						if(trace)
							System.out.print("new ");
						temp[10] = x[10]+1;
						temp[9] = scoreBoard(temp);		//score and add to open queue
						open.add(new int[11]);
						System.arraycopy(temp,0,open.getLast(),0,11);
					}
					
					else if((ofound!=-1))				//if already in open
					{
						if(trace)
							System.out.print("open ");
						System.arraycopy(open.get(ofound),10,time,0,1);
						
						if(time[0] > x[10]+1)	//if reached faster
						{
							time[0] = x[10]+1;
							System.arraycopy(open.get(ofound),10,time,0,1);
						}
					}
					
					else if((cfound!=-1))				//if already in closed
					{
						if(trace)
							System.out.print("closed ");
						System.arraycopy(closed.get(cfound),10,time,0,1);
						
						if(time[0] > x[10]+1)	//if reached faster
						{
							time[0] = x[10]+1;
							System.arraycopy(closed.get(cfound),10,time,0,1);
							System.arraycopy(closed.get(cfound),0,temp,0,11);
							closed.remove(cfound);
							open.add(new int[11]);
							System.arraycopy(temp,0,open.getLast(),0,11);
						}
					}
					
				}
			}
			if(trace)
				System.out.print("\n\n");
			ofound = contains(open,x);			//remove x from open and put on closed
			open.remove(ofound);
			closed.add(new int[11]);
			System.arraycopy(x,0,closed.getLast(),0,11);		
			valsort(open);						//resort list for best score
			
		}
		
		System.arraycopy(x,0,board,0,9);	//if reached then no solution, print path, return
		if(trace)
			print(closed);
		data[2]=x[10]*-1;
		return data;		
	}
}