package be.qanar.slidingPuzzle;

import java.util.* ;

// inspired by http://thedailywtf.com/Articles/Sliding-Around.aspx

public class Main 
{

	public static void main( String [] args ) 
	{
		int size = 3 ;
		PuzzleState begin    = PuzzleState.createRandom( size, 3 ) ;
		PuzzleState solution = new PuzzleState( size )             ;
		
		depthFirst  ( begin, solution ) ;
		BreadthFirst( begin, solution ) ;
	}
	
	public static void depthFirst( PuzzleState begin, PuzzleState solution )
	{
		Stack  < PuzzleState > open   = new Stack  < PuzzleState >() ;
		Vector < PuzzleState > closed = new Vector < PuzzleState >() ;
				
		PuzzleState current = begin ;
		closed.add( current ) ;
				
		while( ! current.equals( solution ) )
		{
			System.out.println( current.toString() ) ;
			
			for( PuzzleState ps : current.getPossibleMoves() )
			{
				if( ! closed.contains( ps ) )
					open.push( ps ) ;
			}
			
			current = open.pop() ;			
			closed.add( current ) ;
		}
		
		System.out.println( "SOLUTION FOUND" );	
		System.out.println( current.toString() ) ;
	}
	
	public static void BreadthFirst( PuzzleState begin, PuzzleState solution )
	{
		Vector < PuzzleState > open   = new Vector < PuzzleState >() ;
		Vector < PuzzleState > closed = new Vector < PuzzleState >() ;
				
		PuzzleState current = begin ;
		closed.add( current ) ;
				
		while( ! current.equals( solution ) )
		{
			System.out.println( current.toString() ) ;
			
			for( PuzzleState ps : current.getPossibleMoves() )
			{
				if( ! closed.contains( ps ) )
					open.add( ps ) ;
			}
			
			current = open.firstElement() ;	
			
			open  .remove( current ) ;
			closed.add   ( current ) ;
		}
		
		System.out.println( "SOLUTION FOUND" );	
		System.out.println( current.toString() ) ;
	}
}