8puzzle.cpp

////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// STL A* Search implementation
// (C)2001 Justin Heyes-Jones
//
// This uses my A* code to solve the 8-puzzle

////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <new>

#include <ctype.h>

using namespace std;

// Configuration

#define NUM_TIMES_TO_RUN_SEARCH 1
#define DISPLAY_SOLUTION_FORWARDS 1
#define DISPLAY_SOLUTION_BACKWARDS 0
#define DISPLAY_SOLUTION_INFO 1
#define DEBUG_LISTS 0

// AStar search class
#include "stlastar.h" // See header for copyright and usage information

// Global data

#define BOARD_WIDTH   (3)
#define BOARD_HEIGHT  (3)

#define GM_TILE     (-1)
#define GM_SPACE	 (0)
#define GM_OFF_BOARD (1)

// Definitions

// To use the search class you must define the following calls...

// Data
//		Your own state space information
// Functions
//		(Optional) Constructor.
//		Nodes are created by the user, so whether you use a
//      constructor with parameters as below, or just set the object up after the 
//      constructor, is up to you.
//
//		(Optional) Destructor. 
//		The destructor will be called if you create one. You 
//		can rely on the default constructor unless you dynamically allocate something in
//		your data
//
//		float GoalDistanceEstimate( PuzzleState &nodeGoal );
//		Return the estimated cost to goal from this node (pass reference to goal node)
//
//		bool IsGoal( PuzzleState &nodeGoal );
//		Return true if this node is the goal.
//
//		bool GetSuccessors( AStarSearch<PuzzleState> *astarsearch );
//		For each successor to this state call the AStarSearch's AddSuccessor call to 
//		add each one to the current search - return false if you are out of memory and the search
//		will fail
//
//		float GetCost( PuzzleState *successor );
//		Return the cost moving from this state to the state of successor
//
//		bool IsSameState( PuzzleState &rhs );
//		Return true if the provided state is the same as this state

// Here the example is the 8-puzzle state ...
class PuzzleState
{

public:

	// defs

	typedef enum
	{
		TL_SPACE,
		TL_1,
		TL_2,
		TL_3,
		TL_4,
		TL_5,
		TL_6,
		TL_7,
		TL_8

	} TILE;

	// data

	static TILE g_goal[ BOARD_WIDTH*BOARD_HEIGHT];
	static TILE g_start[ BOARD_WIDTH*BOARD_HEIGHT];

	// the tile data for the 8-puzzle
	TILE tiles[ BOARD_WIDTH*BOARD_HEIGHT ];

	// member functions

	PuzzleState() {  
						memcpy( tiles, g_goal, sizeof( TILE ) * BOARD_WIDTH * BOARD_HEIGHT );			
					}

	PuzzleState( TILE *param_tiles ) 
					{
						memcpy( tiles, param_tiles, sizeof( TILE ) * BOARD_WIDTH * BOARD_HEIGHT );			
					}

	float GoalDistanceEstimate( PuzzleState &nodeGoal );
	bool IsGoal( PuzzleState &nodeGoal );
	bool GetSuccessors( AStarSearch<PuzzleState> *astarsearch, PuzzleState *parent_node );
	float GetCost( PuzzleState &successor );
	bool IsSameState( PuzzleState &rhs );
	
	void PrintNodeInfo(); 

private:
	// User stuff - Just add what you need to help you write the above functions...

	void GetSpacePosition( PuzzleState *pn, int *rx, int *ry );
	bool LegalMove( TILE *StartTiles, TILE *TargetTiles, int spx, int spy, int tx, int ty );
	int GetMap( int x, int y, TILE *tiles );




};

// Goal state
PuzzleState::TILE PuzzleState::g_goal[] = 
{
	TL_1,
	TL_2,
	TL_3,
	TL_8,
	TL_SPACE,
	TL_4,
	TL_7,
	TL_6,
	TL_5,
};

// Some nice Start states
PuzzleState::TILE PuzzleState::g_start[] = 
{

	// Three example start states from Bratko's Prolog Programming for Artificial Intelligence

#if 1
	// ex a - 4 steps
	 TL_1 ,
	 TL_3 ,
	 TL_4 ,
	 TL_8 ,
	 TL_SPACE ,
	 TL_2 ,
	 TL_7 ,
	 TL_6 ,
	 TL_5 ,

#elif 0
  
	// ex b - 5 steps
	 TL_2 ,
	 TL_8 ,
	 TL_3 ,
	 TL_1 ,
	 TL_6 ,
	 TL_4 ,
	 TL_7 ,
	 TL_SPACE ,
	 TL_5 ,

#elif 0
	
	// ex c - 18 steps
	 TL_2 ,
	 TL_1 ,
	 TL_6 ,
	 TL_4 ,
	 TL_SPACE ,
	 TL_8 ,
	 TL_7 ,
	 TL_5 ,
	 TL_3 ,

#elif 0
	
	// nasty one - doesn't solve
	 TL_6 ,
	 TL_3 ,	  
	 TL_SPACE ,
	 TL_4 ,
	 TL_8 ,
	 TL_5 ,
	 TL_7 ,
	 TL_2 ,
	 TL_1 ,

#elif 0

	// sent by email - does work though

	 TL_1 ,	 TL_2 ,  TL_3 ,
	 TL_4 ,	 TL_5 ,  TL_6 ,
	 TL_8 ,	 TL_7 ,  TL_SPACE ,

	
// from http://www.cs.utexas.edu/users/novak/asg-8p.html

//Goal:        Easy:        Medium:        Hard:        Worst:

//1 2 3        1 3 4        2 8 1          2 8 1        5 6 7
//8   4        8 6 2          4 3          4 6 3        4   8
//7 6 5        7   5        7 6 5            7 5        3 2 1


#elif 0

	// easy 5 
	 TL_1 ,
	 TL_3 ,	  
	 TL_4 ,

	 TL_8 ,
	 TL_6 ,
	 TL_2 ,
	
	 TL_7 ,
	 TL_SPACE ,
	 TL_5 ,


#elif 0

	// medium 9
	 TL_2 ,
	 TL_8 ,	  
	 TL_1 ,

	 TL_SPACE ,
	 TL_4 ,
	 TL_3 ,
	
	 TL_7 ,
	 TL_6 ,
	 TL_5 ,

#elif 0

	// hard 12
	 TL_2 ,
	 TL_8 ,	  
	 TL_1 ,

	 TL_4 ,
	 TL_6 ,
	 TL_3 ,
	
	 TL_SPACE ,
	 TL_7 ,
	 TL_5 ,

#elif 0

	// worst 30
	 TL_5 ,
	 TL_6 ,	  
	 TL_7 ,

	 TL_4 ,
	 TL_SPACE ,
	 TL_8 ,
	
	 TL_3 ,
	 TL_2 ,
	 TL_1 ,

#elif 0

	//	123
	//	784
	//   65

	// two move simple board
	 TL_1 ,
	 TL_2 ,	  
	 TL_3 ,

	 TL_7 ,
	 TL_8 ,
	 TL_4 ,
	
	 TL_SPACE ,
	 TL_6 ,
	 TL_5 ,

#elif 0
	//  a1 b2 c3 d4 e5 f6 g7 h8 
	//C3,Blank,H8,A1,G8,F6,E5,D4,B2

	 TL_3 ,
	 TL_SPACE ,	  
	 TL_8 ,

	 TL_1 ,
	 TL_8 ,
	 TL_6 ,
	
	 TL_5 ,
	 TL_4 ,
	 TL_2 ,


#endif  

};

bool PuzzleState::IsSameState( PuzzleState &rhs )
{

	for( int i=0; i<(BOARD_HEIGHT*BOARD_WIDTH); i++ )
	{
		if( tiles[i] != rhs.tiles[i] )
		{
			return false;
		}
	}

	return true;

}

void PuzzleState::PrintNodeInfo()
{
	char str[100];
	sprintf( str, "%c %c %c\n%c %c %c\n%c %c %c\n", 
			tiles[0] + '0',
			tiles[1] + '0',
			tiles[2] + '0',
			tiles[3] + '0',
			tiles[4] + '0',
			tiles[5] + '0',
			tiles[6] + '0',
			tiles[7] + '0',
			tiles[8] + '0'
		);

	cout << str;
}

// Here's the heuristic function that estimates the distance from a PuzzleState
// to the Goal. 

float PuzzleState::GoalDistanceEstimate( PuzzleState &nodeGoal )
{

	// Nilsson's sequence score

	int i, cx, cy, ax, ay, h = 0, s, t;

	// given a tile this returns the tile that should be clockwise
	TILE correct_follower_to[ BOARD_WIDTH * BOARD_HEIGHT ] =
	{
		TL_SPACE, // always wrong
		TL_2,
		TL_3,
		TL_4,
		TL_5,
		TL_6,
		TL_7,
		TL_8,
		TL_1,
	};

	// given a table index returns the index of the tile that is clockwise to it 3*3 only
	int clockwise_tile_of[ BOARD_WIDTH * BOARD_HEIGHT ] =
	{
		1, 
		2,  	  // 012	  
		5,  	  // 345	  
		0,  	  // 678	  
		-1,  // never called with center square
		8, 
		3, 
		6, 
		7 
	};

	int tile_x[ BOARD_WIDTH * BOARD_HEIGHT ] =
	{
		/* TL_SPACE */ 1,
		/* TL_1 */ 0,    
		/* TL_2 */ 1,    
		/* TL_3 */ 2,    
		/* TL_4 */ 2,    
		/* TL_5 */ 2,    
		/* TL_6 */ 1,    
		/* TL_7 */ 0,    
		/* TL_8 */ 0,    
	};

	int tile_y[ BOARD_WIDTH * BOARD_HEIGHT ] =
	{
		/* TL_SPACE */ 1,	
		/* TL_1 */ 0,
		/* TL_2 */ 0,
		/* TL_3 */ 0,
		/* TL_4 */ 1,
		/* TL_5 */ 2,
		/* TL_6 */ 2,
		/* TL_7 */ 2,
		/* TL_8 */ 1,
	};

	s=0;
	
	// score 1 point if centre is not correct 
	if( tiles[(BOARD_HEIGHT*BOARD_WIDTH)/2] != nodeGoal.tiles[(BOARD_HEIGHT*BOARD_WIDTH)/2] )
	{
 		s = 1;
	}

	for( i=0; i<(BOARD_HEIGHT*BOARD_WIDTH); i++ )
	{
		// this loop adds up the totaldist element in h and
		// the sequence score in s

		// the space does not count
		if( tiles[i] == TL_SPACE )
		{
			continue;
		}

		// get correct x and y of this tile
		cx = tile_x[tiles[i]];
		cy = tile_y[tiles[i]];

		// get actual
		ax = i % BOARD_WIDTH;
		ay = i / BOARD_WIDTH;

		// add manhatten distance to h
		h += abs( cx-ax );
		h += abs( cy-ay );

		// no s score for center tile
		if( (ax == (BOARD_WIDTH/2)) && (ay == (BOARD_HEIGHT/2)) )
		{
			continue;
		}

		// score 2 points if not followed by successor
		if( correct_follower_to[ tiles[i] ] != tiles[ clockwise_tile_of[ i ] ] )
		{
			s += 2;
		}


	}

	// mult by 3 and add to h
	t = h + (3*s);

	return (float) t;

}

bool PuzzleState::IsGoal( PuzzleState &nodeGoal )
{
	return IsSameState( nodeGoal );
}

// Helper
// Return the x and y position of the space tile
void PuzzleState::GetSpacePosition( PuzzleState *pn, int *rx, int *ry )
{
	int x,y;

	for( y=0; y<BOARD_HEIGHT; y++ )
	{
		for( x=0; x<BOARD_WIDTH; x++ )
		{
			if( pn->tiles[(y*BOARD_WIDTH)+x] == TL_SPACE )
			{
				*rx = x;
				*ry = y;

				return;
			}
		}
	}

	assert( false && "Something went wrong. There's no space on the board" );

}

int PuzzleState::GetMap( int x, int y, TILE *tiles )
{

	if( x < 0 ||
	    x >= BOARD_WIDTH ||
		 y < 0 ||
		 y >= BOARD_HEIGHT
	  )
		return GM_OFF_BOARD;	 

	if( tiles[(y*BOARD_WIDTH)+x] == TL_SPACE )
	{
		return GM_SPACE;
	}

	return GM_TILE;
}

// Given a node set of tiles and a set of tiles to move them into, do the move as if it was on a tile board
// note : returns false if the board wasn't changed, and simply returns the tiles as they were in the target
// spx and spy is the space position while tx and ty is the target move from position

bool PuzzleState::LegalMove( TILE *StartTiles, TILE *TargetTiles, int spx, int spy, int tx, int ty )
{

	int t;
	
	if( GetMap( spx, spy, StartTiles ) == GM_SPACE )
	{
		if( GetMap( tx, ty, StartTiles ) == GM_TILE )
		{

			// copy tiles
			for( t=0; t<(BOARD_HEIGHT*BOARD_WIDTH); t++ )
			{
				TargetTiles[t] = StartTiles[t];
			}


			TargetTiles[ (ty*BOARD_WIDTH)+tx ] = StartTiles[ (spy*BOARD_WIDTH)+spx ];
			TargetTiles[ (spy*BOARD_WIDTH)+spx ] = StartTiles[ (ty*BOARD_WIDTH)+tx ];

			return true;
		}
	}


	return false;

}

// This generates the successors to the given PuzzleState. It uses a helper function called
// AddSuccessor to give the successors to the AStar class. The A* specific initialisation
// is done for each node internally, so here you just set the state information that
// is specific to the application
bool PuzzleState::GetSuccessors( AStarSearch<PuzzleState> *astarsearch, PuzzleState *parent_node )
{
	PuzzleState NewNode;

	int sp_x,sp_y;

	GetSpacePosition( this, &sp_x, &sp_y );

	bool ret;

	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x, sp_y-1 ) == true )
	{
		ret = astarsearch->AddSuccessor( NewNode );

		if( !ret ) return false;
	}

	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x, sp_y+1 ) == true )
	{
		ret = astarsearch->AddSuccessor( NewNode );
		
		if( !ret ) return false;
	}

	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x-1, sp_y ) == true )
	{
		ret = astarsearch->AddSuccessor( NewNode );

		if( !ret ) return false;
	}

	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x+1, sp_y ) == true )
	{
		ret = astarsearch->AddSuccessor( NewNode );
	
		if( !ret ) return false;
	}

	return true; 
}

// given this node, what does it cost to move to successor. In the case
// of our map the answer is the map terrain value at this node since that is 
// conceptually where we're moving

float PuzzleState::GetCost( PuzzleState &successor )
{
	return 1.0f; // I love it when life is simple

}


// Main

int main( int argc, char *argv[] )
{

	cout << "STL A* 8-puzzle solver implementation\n(C)2001 Justin Heyes-Jones\n";

	bool bUserBoard = false;

	if( argc > 1 )
	{
		char *userboard = argv[1];

		int i = 0;
		int c;

		while( c = argv[1][i] )
		{
			if( isdigit( c ) )
			{
				int num = (c - '0');

				PuzzleState::g_start[i] = static_cast<PuzzleState::TILE>(num);
				
			}
		
			i++;
		}


	}

	// Create an instance of the search class...

	AStarSearch<PuzzleState> astarsearch;

	int NumTimesToSearch = NUM_TIMES_TO_RUN_SEARCH;

	while( NumTimesToSearch-- )
	{

		// Create a start state
		PuzzleState nodeStart( PuzzleState::g_start );

		// Define the goal state
		PuzzleState nodeEnd( PuzzleState::g_goal );

		// Set Start and goal states
		astarsearch.SetStartAndGoalStates( nodeStart, nodeEnd );

		unsigned int SearchState;

		unsigned int SearchSteps = 0;

		do
		{
			SearchState = astarsearch.SearchStep();

#if DEBUG_LISTS

			float f,g,h;

			cout << "Search step " << SearchSteps << endl;

			cout << "Open:\n";
			PuzzleState *p = astarsearch.GetOpenListStart( f,g,h );
			while( p )
			{
				((PuzzleState *)p)->PrintNodeInfo();
				cout << "f: " << f << " g: " << g << " h: " << h << "\n\n";
				
				p = astarsearch.GetOpenListNext( f,g,h );
				
			}

			cout << "Closed:\n";
			p = astarsearch.GetClosedListStart( f,g,h );
			while( p )
			{
				p->PrintNodeInfo();
				cout << "f: " << f << " g: " << g << " h: " << h << "\n\n";
				
				p = astarsearch.GetClosedListNext( f,g,h );
			}

#endif

// Test cancel search
#if 0
			int StepCount = astarsearch.GetStepCount();
			if( StepCount == 10 )
			{
				astarsearch.CancelSearch();
			}
#endif
			SearchSteps++;
		}
		while( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_SEARCHING );

		if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_SUCCEEDED )
		{
#if DISPLAY_SOLUTION_FORWARDS
			cout << "Search found goal state\n";
#endif
			PuzzleState *node = astarsearch.GetSolutionStart();

#if DISPLAY_SOLUTION_FORWARDS
			cout << "Displaying solution\n";
#endif
			int steps = 0;

#if DISPLAY_SOLUTION_FORWARDS
			node->PrintNodeInfo();
			cout << endl;
#endif
			for( ;; )
			{
				node = astarsearch.GetSolutionNext();

				if( !node )
				{
					break;
				}

#if DISPLAY_SOLUTION_FORWARDS
				node->PrintNodeInfo();
				cout << endl;
#endif
				steps ++;
			
			};

#if DISPLAY_SOLUTION_FORWARDS
			// todo move step count into main algorithm
			cout << "Solution steps " << steps << endl;
#endif

////////////

			node = astarsearch.GetSolutionEnd();

#if DISPLAY_SOLUTION_BACKWARDS
			cout << "Displaying reverse solution\n";
#endif
			steps = 0;

			node->PrintNodeInfo();
			cout << endl;
			for( ;; )
			{
				node = astarsearch.GetSolutionPrev();

				if( !node )
				{
					break;
				}
#if DISPLAY_SOLUTION_BACKWARDS
				node->PrintNodeInfo();
                cout << endl;
#endif
				steps ++;
			
			};

#if DISPLAY_SOLUTION_BACKWARDS
			cout << "Solution steps " << steps << endl;
#endif

//////////////

			// Once you're done with the solution you can free the nodes up
			astarsearch.FreeSolutionNodes();
		
		}
		else if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_FAILED ) 
		{
#if DISPLAY_SOLUTION_INFO
			cout << "Search terminated. Did not find goal state\n";
#endif		
		}
		else if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_OUT_OF_MEMORY ) 
		{
#if DISPLAY_SOLUTION_INFO
			cout << "Search terminated. Out of memory\n";
#endif		
		}

		

		// Display the number of loops the search went through
#if DISPLAY_SOLUTION_INFO
		cout << "SearchSteps : " << astarsearch.GetStepCount() << endl;
#endif
	}

	return 0;
}