hexpuzzleitems.java

source codes to solve Hexpuzzle problem

import java.util.ArrayList;
import java.util.LinkedList;

public class HexpuzzleItems {
	private Item[] puzzleItems;
	private int heuristicNum;
	
	HexpuzzleItems(String items, int heuristicNum)
	{		
		if(checkItemstring(items) && heuristicNum >=1 && heuristicNum <=3)
		{
			this.heuristicNum = heuristicNum;
			
			puzzleItems = new Item[17];
			items = items.trim();
			int pos = 0;
			for(int i = 0; i < 31; i=i+2)
			{
				pos++;
				char data = items.charAt(i);
				Item newItem = new Item(data, pos);
				puzzleItems[pos] = newItem;
			}
			
			this.connectItems();
		}
		else
		{
			System.out.println("Please check the input string");
			System.exit(1);			
		}
	}
	
	HexpuzzleItems(HexpuzzleItems puzzileItems)
	{
		if(puzzileItems != null)
		{
			this.heuristicNum = puzzileItems.heuristicNum;
			
			this.puzzleItems = new Item[17];
			
			for(int i = 1; i < 17; i++)
			{
				Item oldItem = puzzileItems.getItem(i);
				Item newItem = new Item(oldItem);
				
				this.puzzleItems[i] = newItem;				
			}
		}
	}
	
	private boolean checkItemstring(String items)
	{
		items = items.trim();		
		if(items != null && items.length() == 31)
		{
			for(int i = 0; i <= 31; i++)
			{
				char cr1 = items.charAt(i);
				if((cr1 < 65 || cr1 > 79) && cr1 != '_')
					return false;
					
				for(int j = i+2; j < 31; j=j+2)
				{
					char cr2 = items.charAt(j);
					if(cr1 == cr2) return false;
				}
				i++;
				if(i != 31 && items.charAt(i) != ' ') return false;
			}
		}
		return true;
	}
	
	public Item getItem(int pos)
	{
		if(pos > 0 && pos < 17)
		{
			return this.puzzleItems[pos];
		}
		return null;
	}
	
	private void connectItems()
	{
		for(int i = 1; i <= 11; i++)
		{
			this.puzzleItems[i].connectItem(this.puzzleItems[i+1]);
			this.puzzleItems[i+1].connectItem(this.puzzleItems[i]);
		}
		
		/*the 12th item*/
		//connect between the 12th item and the 1st item 
		this.puzzleItems[12].connectItem(this.puzzleItems[1]);
		this.puzzleItems[1].connectItem(this.puzzleItems[12]);
		
		/*the 13th item*/
		//connect between the 13th item and the 12th item 
		this.puzzleItems[12].connectItem(this.puzzleItems[13]);
		this.puzzleItems[13].connectItem(this.puzzleItems[12]);
		
		//connect between the 13th item and the 1st item
		this.puzzleItems[1].connectItem(this.puzzleItems[13]);
		this.puzzleItems[13].connectItem(this.puzzleItems[1]);
		
		//connect between the 13th item and the 2nd item
		this.puzzleItems[2].connectItem(this.puzzleItems[13]);
		this.puzzleItems[13].connectItem(this.puzzleItems[2]);
		
		/*the 14th item*/
		//connect between the 14th item and the 8th item 
		this.puzzleItems[8].connectItem(this.puzzleItems[14]);
		this.puzzleItems[14].connectItem(this.puzzleItems[8]);
		
		//connect between the 14th item and the 9th item
		this.puzzleItems[9].connectItem(this.puzzleItems[14]);
		this.puzzleItems[14].connectItem(this.puzzleItems[9]);
		
		//connect between the 14th item and the 10th item
		this.puzzleItems[10].connectItem(this.puzzleItems[14]);
		this.puzzleItems[14].connectItem(this.puzzleItems[10]);
		
		/*the 15th item*/
		//connect between the 15th item and the 4th item 
		this.puzzleItems[4].connectItem(this.puzzleItems[15]);
		this.puzzleItems[15].connectItem(this.puzzleItems[4]);
		
		//connect between the 15th item and the 5th item
		this.puzzleItems[5].connectItem(this.puzzleItems[15]);
		this.puzzleItems[15].connectItem(this.puzzleItems[5]);
		
		//connect between the 15th item and the 6th item
		this.puzzleItems[6].connectItem(this.puzzleItems[15]);
		this.puzzleItems[15].connectItem(this.puzzleItems[6]);
		
		/*the 16th--central item*/
		//connect between the 16th item and the 13th item 
		this.puzzleItems[13].connectItem(this.puzzleItems[16]);
		this.puzzleItems[16].connectItem(this.puzzleItems[13]);
		
		//connect between the 16th item and the 14th item
		this.puzzleItems[14].connectItem(this.puzzleItems[16]);
		this.puzzleItems[16].connectItem(this.puzzleItems[14]);
		
		//connect between the 16th item and the 15th item
		this.puzzleItems[15].connectItem(this.puzzleItems[16]);
		this.puzzleItems[16].connectItem(this.puzzleItems[15]);
	}
	
	public String toString()
	{
		String str = "";
		for(int i = 1; i <= 15; i++)
		{
			str += this.puzzleItems[i].getData();
			str += " ";
		}
		str += this.puzzleItems[16].getData();
		
		return str;
	}
	
	public boolean equals(Object obj)
	{
		HexpuzzleItems temp = (HexpuzzleItems)obj;
		
		for(int i = 1; i<=16; i++)
		{
			Item item1 = this.puzzleItems[i];
			Item item2 = temp.puzzleItems[i];
			
			if(!item1.equals(item2)) return false;
		}
		return true;
	}
	public Item findBlankItem()
	{
		for(int i = 1; i <= 16; i++)
		{
			char temp = this.puzzleItems[i].getData();
			if(temp == '_') return this.puzzleItems[i];
		}
		return null;
	}
	
	public void swapItems(Item item1, Item item2)
	{
		int pos1 = 0;
		int pos2 = 0;	
		
		for(int i = 1; i <= 16; i++)
		{			
			if( this.puzzleItems[i].getData() == item1.getData() && 
				this.puzzleItems[i].getPosition() == item1.getPosition())
					pos1 = i;
		}
		
		for(int i = 1; i <= 16; i++)
		{			
			if( this.puzzleItems[i].getData() == item2.getData() && 
				this.puzzleItems[i].getPosition() == item2.getPosition())
					pos2 = i;
		}
		
		if(pos1 > 0 && pos2 > 0)
			this.puzzleItems[pos1].swapItem(this.puzzleItems[pos2]);
	}
	
	/*use misplay as heuristic funciton*/
	private int heuristicF1()
	{
		int cost = 0;
		for(int i = 1; i <= 16; i++)
		{
			char item = this.puzzleItems[i].getData();
			if(item!= '_' && item != 64+i)
				cost++;
		}
		return cost;
	}
	
	/*use Manhattan distance as heuristic funciton*/
	private int heuristicF2()
	{
		int cost = 0;
		for(int i = 1; i <= 16; i++)
		{
			int diff = 0;
			char item = this.puzzleItems[i].getData();			
			if(item!= '_')
			{
				diff = Math.abs(item-64-i);
				if (diff != 0)
				{
					int[] markList = new int[17];
					for(int j=0;j<17;j++)
						markList[j] = 0;
					markList[i] = 1;
					
					ArrayList<Item> adjList = this.puzzleItems[i].getAdjacentItems();
					LinkedList<Path> pathCostList = new LinkedList<Path>();
					for(int k=0; k<adjList.size(); k++)
					{
						Path path = new Path(adjList.get(k), 1);
						pathCostList.addFirst(path);
					}
					
					while(!pathCostList.isEmpty())
					{
						Path tmpPath = pathCostList.removeLast();
						Item tmpItem = tmpPath.getData();
						
						if(tmpItem.getData() == item)
						{
							diff = tmpPath.getCost();
							break;
						}
						else
						{
							int pos = tmpItem.getPosition();
							markList[pos] = 1;
							
							adjList = tmpItem.getAdjacentItems();
							for(int l=0; l<adjList.size(); l++)
							{
								pos = adjList.get(l).getPosition();
								if(markList[pos] == 0)
								{
									Path path = new Path(adjList.get(l), tmpPath.getCost()+1);
									pathCostList.addFirst(path);
								}
							}
						}
					}
					
				}
			}
			cost += diff;
		}						
		return cost;
	}
		
	/*user defined heuristic funciton*/
	private int heuristicF3()
	{
		return this.heuristicF1()*3+ this.heuristicF2()*7;
	}
	
	public int getHeuristicCost()
	{
		switch(this.heuristicNum)
		{
		case 1:
			return this.heuristicF1();
		case 2:
			return this.heuristicF2();
		case 3:
			return this.heuristicF3();
		default:
			return 0;	
		}
	}
	
	public boolean goalTest()
	{
		for(int i = 1; i <= 15; i++)
		{
			char item = this.puzzleItems[i].getData();
			if(item != 64+i) return false;
		}
		return true;
	}
}