eight_puzzle.java

来自「利用深度遍历的方法来检查8数码问题是否有解。」· Java 代码 · 共 251 行

import java.util.Vector;

public class Eight_Puzzle
{
	public static void main(String[] args)
	{
		char[][] BeginNode=new char[3][3];
		BeginNode[0][0]=' ';
		BeginNode[0][1]='2';
		BeginNode[0][2]='3';
		BeginNode[1][0]='1';
		BeginNode[1][1]='8';
		BeginNode[1][2]='4';
		BeginNode[2][0]='7';
		BeginNode[2][1]='6';
		BeginNode[2][2]='5';
		
		
		MatrixNode beginNode=new MatrixNode();
		beginNode.setNode(BeginNode);
		
		System.out.println("The Begin Node: ");
		beginNode.displayNode();
		
		char[][] EndNode=new char[3][3];
		EndNode[0][0]='1';
		EndNode[0][1]='2';
		EndNode[0][2]='3';
		EndNode[1][0]='8';
		EndNode[1][1]=' ';
		EndNode[1][2]='4';
		EndNode[2][0]='7';
		EndNode[2][1]='6';
		EndNode[2][2]='5';		
		MatrixNode endNode=new MatrixNode();
		endNode.setNode(EndNode);
		System.out.println("The End Node: ");
		endNode.displayNode();
		
		
//		System.out.println(beginNode.check(endNode));
		
		System.out.println("The transform result: "+eightPuzzle(beginNode,endNode));
		
	}
	
	public static boolean eightPuzzle(MatrixNode beginNode,MatrixNode endNode)
	{
		Vector nodeVector=new Vector();
		nodeVector.add(beginNode);
		
		DQueue queue=new DQueue();
		queue.push(beginNode);
	
		while(true)
		{
			if(queue.empty())
				return false;
				
			MatrixNode node=(MatrixNode)queue.pop();
			
			if(node.check(endNode))
				return true;
			
			Vector vector=FindNextNode(node);		
				
			for(int i=0;i<vector.size();i++)
			{
				MatrixNode item=(MatrixNode)vector.get(i);
				if(check(item,nodeVector))
				{
					queue.push(item);
					nodeVector.add(item);
				}
			}
		}
	}
	
	public static Vector FindNextNode(MatrixNode node)
	{
		Vector vector=new Vector();
		
		DPoint point=node.getBlank();
		int x=point.x;
		int y=point.y;
		
		vector.add(node);
		
		if(x==0&&y==0)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x,y+1);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x+1,y);
			vector.add(itemNode2);
			
			vector.remove(0);						
		}
		
		else if(x==0&&y==2)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x,y-1);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x+1,y);
			vector.add(itemNode2);
			
			vector.remove(0);						
		}		
		
		else if(x==2&&y==0)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x-1,y);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x,y+1);
			vector.add(itemNode2);
			
			vector.remove(0);						
		}		
		
		else if(x==0&&y!=0&&y!=2)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x,y-1);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x,y+1);
			vector.add(itemNode2);
			
			MatrixNode itemNode3=new MatrixNode();
			itemNode3.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode3.transform(x,y,x+1,y);
			vector.add(itemNode3);
						
			vector.remove(0);						
		}				

		else if(x==2&&y!=0&&y!=2)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x,y-1);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x,y+1);
			vector.add(itemNode2);
			
			MatrixNode itemNode3=new MatrixNode();
			itemNode3.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode3.transform(x,y,x-1,y);
			vector.add(itemNode3);
						
			vector.remove(0);						
		}				
		
		else if(y==0&&x!=0&&x!=2)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x+1,y);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x-1,y);
			vector.add(itemNode2);
			
			MatrixNode itemNode3=new MatrixNode();
			itemNode3.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode3.transform(x,y,x,y+1);
			vector.add(itemNode3);
						
			vector.remove(0);						
		}				

		else if(y==2&&x!=0&&x!=2)
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x-1,y);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x+1,y);
			vector.add(itemNode2);
			
			MatrixNode itemNode3=new MatrixNode();
			itemNode3.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode3.transform(x,y,x,y-1);
			vector.add(itemNode3);
						
			vector.remove(0);						
		}				

		else 
		{
			MatrixNode itemNode=new MatrixNode();
			itemNode.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode.transform(x,y,x-1,y);
			vector.add(itemNode);

			MatrixNode itemNode2=new MatrixNode();
			itemNode2.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode2.transform(x,y,x+1,y);
			vector.add(itemNode2);
			
			MatrixNode itemNode3=new MatrixNode();
			itemNode3.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode3.transform(x,y,x,y-1);
			vector.add(itemNode3);

			MatrixNode itemNode4=new MatrixNode();
			itemNode4.setNode(((MatrixNode)(vector.get(0))).matrix);	
			itemNode4.transform(x,y,x,y+1);
			vector.add(itemNode4);
									
			vector.remove(0);									
		}
		
		return vector;
	}	
	
	public static boolean check(MatrixNode node,Vector vector)
	{
		for(int i=0;i<vector.size();i++)
		{
			if(node.check((MatrixNode)vector.get(i)))
				return false;
		}
		return true;
	}
}