zibbr

Random 3d and p2p stuff that was originally the beginnings of an overly ambitious p2p virtual world thingy
git clone https://code.literati.org/zibbr.git
Log | Files | Refs

8puzzle.cpp (15412B)


      1 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
      2 // STL A* Search implementation
      3 // (C)2001 Justin Heyes-Jones
      4 //
      5 // This uses my A* code to solve the 8-puzzle
      6 
      7 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
      8 
      9 #include <iostream>
     10 #include <assert.h>
     11 #include <new>
     12 
     13 #include <ctype.h>
     14 
     15 using namespace std;
     16 
     17 // Configuration
     18 
     19 #define NUM_TIMES_TO_RUN_SEARCH 1
     20 #define DISPLAY_SOLUTION_FORWARDS 1
     21 #define DISPLAY_SOLUTION_BACKWARDS 0
     22 #define DISPLAY_SOLUTION_INFO 1
     23 #define DEBUG_LISTS 0
     24 
     25 // AStar search class
     26 #include "stlastar.h" // See header for copyright and usage information
     27 
     28 // Global data
     29 
     30 #define BOARD_WIDTH   (3)
     31 #define BOARD_HEIGHT  (3)
     32 
     33 #define GM_TILE     (-1)
     34 #define GM_SPACE	 (0)
     35 #define GM_OFF_BOARD (1)
     36 
     37 // Definitions
     38 
     39 // To use the search class you must define the following calls...
     40 
     41 // Data
     42 //		Your own state space information
     43 // Functions
     44 //		(Optional) Constructor.
     45 //		Nodes are created by the user, so whether you use a
     46 //      constructor with parameters as below, or just set the object up after the 
     47 //      constructor, is up to you.
     48 //
     49 //		(Optional) Destructor. 
     50 //		The destructor will be called if you create one. You 
     51 //		can rely on the default constructor unless you dynamically allocate something in
     52 //		your data
     53 //
     54 //		float GoalDistanceEstimate( PuzzleState &nodeGoal );
     55 //		Return the estimated cost to goal from this node (pass reference to goal node)
     56 //
     57 //		bool IsGoal( PuzzleState &nodeGoal );
     58 //		Return true if this node is the goal.
     59 //
     60 //		bool GetSuccessors( AStarSearch<PuzzleState> *astarsearch );
     61 //		For each successor to this state call the AStarSearch's AddSuccessor call to 
     62 //		add each one to the current search - return false if you are out of memory and the search
     63 //		will fail
     64 //
     65 //		float GetCost( PuzzleState *successor );
     66 //		Return the cost moving from this state to the state of successor
     67 //
     68 //		bool IsSameState( PuzzleState &rhs );
     69 //		Return true if the provided state is the same as this state
     70 
     71 // Here the example is the 8-puzzle state ...
     72 class PuzzleState
     73 {
     74 
     75 public:
     76 
     77 	// defs
     78 
     79 	typedef enum
     80 	{
     81 		TL_SPACE,
     82 		TL_1,
     83 		TL_2,
     84 		TL_3,
     85 		TL_4,
     86 		TL_5,
     87 		TL_6,
     88 		TL_7,
     89 		TL_8
     90 
     91 	} TILE;
     92 
     93 	// data
     94 
     95 	static TILE g_goal[ BOARD_WIDTH*BOARD_HEIGHT];
     96 	static TILE g_start[ BOARD_WIDTH*BOARD_HEIGHT];
     97 
     98 	// the tile data for the 8-puzzle
     99 	TILE tiles[ BOARD_WIDTH*BOARD_HEIGHT ];
    100 
    101 	// member functions
    102 
    103 	PuzzleState() {  
    104 						memcpy( tiles, g_goal, sizeof( TILE ) * BOARD_WIDTH * BOARD_HEIGHT );			
    105 					}
    106 
    107 	PuzzleState( TILE *param_tiles ) 
    108 					{
    109 						memcpy( tiles, param_tiles, sizeof( TILE ) * BOARD_WIDTH * BOARD_HEIGHT );			
    110 					}
    111 
    112 	float GoalDistanceEstimate( PuzzleState &nodeGoal );
    113 	bool IsGoal( PuzzleState &nodeGoal );
    114 	bool GetSuccessors( AStarSearch<PuzzleState> *astarsearch, PuzzleState *parent_node );
    115 	float GetCost( PuzzleState &successor );
    116 	bool IsSameState( PuzzleState &rhs );
    117 	
    118 	void PrintNodeInfo(); 
    119 
    120 private:
    121 	// User stuff - Just add what you need to help you write the above functions...
    122 
    123 	void GetSpacePosition( PuzzleState *pn, int *rx, int *ry );
    124 	bool LegalMove( TILE *StartTiles, TILE *TargetTiles, int spx, int spy, int tx, int ty );
    125 	int GetMap( int x, int y, TILE *tiles );
    126 
    127 
    128 
    129 
    130 };
    131 
    132 // Goal state
    133 PuzzleState::TILE PuzzleState::g_goal[] = 
    134 {
    135 	TL_1,
    136 	TL_2,
    137 	TL_3,
    138 	TL_8,
    139 	TL_SPACE,
    140 	TL_4,
    141 	TL_7,
    142 	TL_6,
    143 	TL_5,
    144 };
    145 
    146 // Some nice Start states
    147 PuzzleState::TILE PuzzleState::g_start[] = 
    148 {
    149 
    150 	// Three example start states from Bratko's Prolog Programming for Artificial Intelligence
    151 
    152 #if 1
    153 	// ex a - 4 steps
    154 	 TL_1 ,
    155 	 TL_3 ,
    156 	 TL_4 ,
    157 	 TL_8 ,
    158 	 TL_SPACE ,
    159 	 TL_2 ,
    160 	 TL_7 ,
    161 	 TL_6 ,
    162 	 TL_5 ,
    163 
    164 #elif 0
    165   
    166 	// ex b - 5 steps
    167 	 TL_2 ,
    168 	 TL_8 ,
    169 	 TL_3 ,
    170 	 TL_1 ,
    171 	 TL_6 ,
    172 	 TL_4 ,
    173 	 TL_7 ,
    174 	 TL_SPACE ,
    175 	 TL_5 ,
    176 
    177 #elif 0
    178 	
    179 	// ex c - 18 steps
    180 	 TL_2 ,
    181 	 TL_1 ,
    182 	 TL_6 ,
    183 	 TL_4 ,
    184 	 TL_SPACE ,
    185 	 TL_8 ,
    186 	 TL_7 ,
    187 	 TL_5 ,
    188 	 TL_3 ,
    189 
    190 #elif 0
    191 	
    192 	// nasty one - doesn't solve
    193 	 TL_6 ,
    194 	 TL_3 ,	  
    195 	 TL_SPACE ,
    196 	 TL_4 ,
    197 	 TL_8 ,
    198 	 TL_5 ,
    199 	 TL_7 ,
    200 	 TL_2 ,
    201 	 TL_1 ,
    202 
    203 #elif 0
    204 
    205 	// sent by email - does work though
    206 
    207 	 TL_1 ,	 TL_2 ,  TL_3 ,
    208 	 TL_4 ,	 TL_5 ,  TL_6 ,
    209 	 TL_8 ,	 TL_7 ,  TL_SPACE ,
    210 
    211 	
    212 // from http://www.cs.utexas.edu/users/novak/asg-8p.html
    213 
    214 //Goal:        Easy:        Medium:        Hard:        Worst:
    215 
    216 //1 2 3        1 3 4        2 8 1          2 8 1        5 6 7
    217 //8   4        8 6 2          4 3          4 6 3        4   8
    218 //7 6 5        7   5        7 6 5            7 5        3 2 1
    219 
    220 
    221 #elif 0
    222 
    223 	// easy 5 
    224 	 TL_1 ,
    225 	 TL_3 ,	  
    226 	 TL_4 ,
    227 
    228 	 TL_8 ,
    229 	 TL_6 ,
    230 	 TL_2 ,
    231 	
    232 	 TL_7 ,
    233 	 TL_SPACE ,
    234 	 TL_5 ,
    235 
    236 
    237 #elif 0
    238 
    239 	// medium 9
    240 	 TL_2 ,
    241 	 TL_8 ,	  
    242 	 TL_1 ,
    243 
    244 	 TL_SPACE ,
    245 	 TL_4 ,
    246 	 TL_3 ,
    247 	
    248 	 TL_7 ,
    249 	 TL_6 ,
    250 	 TL_5 ,
    251 
    252 #elif 0
    253 
    254 	// hard 12
    255 	 TL_2 ,
    256 	 TL_8 ,	  
    257 	 TL_1 ,
    258 
    259 	 TL_4 ,
    260 	 TL_6 ,
    261 	 TL_3 ,
    262 	
    263 	 TL_SPACE ,
    264 	 TL_7 ,
    265 	 TL_5 ,
    266 
    267 #elif 0
    268 
    269 	// worst 30
    270 	 TL_5 ,
    271 	 TL_6 ,	  
    272 	 TL_7 ,
    273 
    274 	 TL_4 ,
    275 	 TL_SPACE ,
    276 	 TL_8 ,
    277 	
    278 	 TL_3 ,
    279 	 TL_2 ,
    280 	 TL_1 ,
    281 
    282 #elif 0
    283 
    284 	//	123
    285 	//	784
    286 	//   65
    287 
    288 	// two move simple board
    289 	 TL_1 ,
    290 	 TL_2 ,	  
    291 	 TL_3 ,
    292 
    293 	 TL_7 ,
    294 	 TL_8 ,
    295 	 TL_4 ,
    296 	
    297 	 TL_SPACE ,
    298 	 TL_6 ,
    299 	 TL_5 ,
    300 
    301 #elif 0
    302 	//  a1 b2 c3 d4 e5 f6 g7 h8 
    303 	//C3,Blank,H8,A1,G8,F6,E5,D4,B2
    304 
    305 	 TL_3 ,
    306 	 TL_SPACE ,	  
    307 	 TL_8 ,
    308 
    309 	 TL_1 ,
    310 	 TL_8 ,
    311 	 TL_6 ,
    312 	
    313 	 TL_5 ,
    314 	 TL_4 ,
    315 	 TL_2 ,
    316 
    317 
    318 #endif  
    319 
    320 };
    321 
    322 bool PuzzleState::IsSameState( PuzzleState &rhs )
    323 {
    324 
    325 	for( int i=0; i<(BOARD_HEIGHT*BOARD_WIDTH); i++ )
    326 	{
    327 		if( tiles[i] != rhs.tiles[i] )
    328 		{
    329 			return false;
    330 		}
    331 	}
    332 
    333 	return true;
    334 
    335 }
    336 
    337 void PuzzleState::PrintNodeInfo()
    338 {
    339 	cout << 
    340 		(char) (tiles[0] + '0') << 
    341 		(char) (tiles[1] + '0') <<
    342 		(char) (tiles[2] + '0') << endl <<
    343 		(char) (tiles[3] + '0') <<
    344 		(char) (tiles[4] + '0') << 
    345 		(char) (tiles[5] + '0') << endl << 
    346 		(char) (tiles[6] + '0') << 
    347 		(char) (tiles[7] + '0') << 
    348 		(char) (tiles[8] + '0') << endl; 
    349 }
    350 
    351 // Here's the heuristic function that estimates the distance from a PuzzleState
    352 // to the Goal. 
    353 
    354 float PuzzleState::GoalDistanceEstimate( PuzzleState &nodeGoal )
    355 {
    356 
    357 	// Nilsson's sequence score
    358 
    359 	int i, cx, cy, ax, ay, h = 0, s, t;
    360 
    361 	// given a tile this returns the tile that should be clockwise
    362 	TILE correct_follower_to[ BOARD_WIDTH * BOARD_HEIGHT ] =
    363 	{
    364 		TL_SPACE, // always wrong
    365 		TL_2,
    366 		TL_3,
    367 		TL_4,
    368 		TL_5,
    369 		TL_6,
    370 		TL_7,
    371 		TL_8,
    372 		TL_1,
    373 	};
    374 
    375 	// given a table index returns the index of the tile that is clockwise to it 3*3 only
    376 	int clockwise_tile_of[ BOARD_WIDTH * BOARD_HEIGHT ] =
    377 	{
    378 		1, 
    379 		2,  	  // 012	  
    380 		5,  	  // 345	  
    381 		0,  	  // 678	  
    382 		-1,  // never called with center square
    383 		8, 
    384 		3, 
    385 		6, 
    386 		7 
    387 	};
    388 
    389 	int tile_x[ BOARD_WIDTH * BOARD_HEIGHT ] =
    390 	{
    391 		/* TL_SPACE */ 1,
    392 		/* TL_1 */ 0,    
    393 		/* TL_2 */ 1,    
    394 		/* TL_3 */ 2,    
    395 		/* TL_4 */ 2,    
    396 		/* TL_5 */ 2,    
    397 		/* TL_6 */ 1,    
    398 		/* TL_7 */ 0,    
    399 		/* TL_8 */ 0,    
    400 	};
    401 
    402 	int tile_y[ BOARD_WIDTH * BOARD_HEIGHT ] =
    403 	{
    404 		/* TL_SPACE */ 1,	
    405 		/* TL_1 */ 0,
    406 		/* TL_2 */ 0,
    407 		/* TL_3 */ 0,
    408 		/* TL_4 */ 1,
    409 		/* TL_5 */ 2,
    410 		/* TL_6 */ 2,
    411 		/* TL_7 */ 2,
    412 		/* TL_8 */ 1,
    413 	};
    414 
    415 	s=0;
    416 	
    417 	// score 1 point if centre is not correct 
    418 	if( tiles[(BOARD_HEIGHT*BOARD_WIDTH)/2] != nodeGoal.tiles[(BOARD_HEIGHT*BOARD_WIDTH)/2] )
    419 	{
    420  		s = 1;
    421 	}
    422 
    423 	for( i=0; i<(BOARD_HEIGHT*BOARD_WIDTH); i++ )
    424 	{
    425 		// this loop adds up the totaldist element in h and
    426 		// the sequence score in s
    427 
    428 		// the space does not count
    429 		if( tiles[i] == TL_SPACE )
    430 		{
    431 			continue;
    432 		}
    433 
    434 		// get correct x and y of this tile
    435 		cx = tile_x[tiles[i]];
    436 		cy = tile_y[tiles[i]];
    437 
    438 		// get actual
    439 		ax = i % BOARD_WIDTH;
    440 		ay = i / BOARD_WIDTH;
    441 
    442 		// add manhatten distance to h
    443 		h += abs( cx-ax );
    444 		h += abs( cy-ay );
    445 
    446 		// no s score for center tile
    447 		if( (ax == (BOARD_WIDTH/2)) && (ay == (BOARD_HEIGHT/2)) )
    448 		{
    449 			continue;
    450 		}
    451 
    452 		// score 2 points if not followed by successor
    453 		if( correct_follower_to[ tiles[i] ] != tiles[ clockwise_tile_of[ i ] ] )
    454 		{
    455 			s += 2;
    456 		}
    457 
    458 
    459 	}
    460 
    461 	// mult by 3 and add to h
    462 	t = h + (3*s);
    463 
    464 	return (float) t;
    465 
    466 }
    467 
    468 bool PuzzleState::IsGoal( PuzzleState &nodeGoal )
    469 {
    470 	return IsSameState( nodeGoal );
    471 }
    472 
    473 // Helper
    474 // Return the x and y position of the space tile
    475 void PuzzleState::GetSpacePosition( PuzzleState *pn, int *rx, int *ry )
    476 {
    477 	int x,y;
    478 
    479 	for( y=0; y<BOARD_HEIGHT; y++ )
    480 	{
    481 		for( x=0; x<BOARD_WIDTH; x++ )
    482 		{
    483 			if( pn->tiles[(y*BOARD_WIDTH)+x] == TL_SPACE )
    484 			{
    485 				*rx = x;
    486 				*ry = y;
    487 
    488 				return;
    489 			}
    490 		}
    491 	}
    492 
    493 	assert( false && "Something went wrong. There's no space on the board" );
    494 
    495 }
    496 
    497 int PuzzleState::GetMap( int x, int y, TILE *tiles )
    498 {
    499 
    500 	if( x < 0 ||
    501 	    x >= BOARD_WIDTH ||
    502 		 y < 0 ||
    503 		 y >= BOARD_HEIGHT
    504 	  )
    505 		return GM_OFF_BOARD;	 
    506 
    507 	if( tiles[(y*BOARD_WIDTH)+x] == TL_SPACE )
    508 	{
    509 		return GM_SPACE;
    510 	}
    511 
    512 	return GM_TILE;
    513 }
    514 
    515 // 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
    516 // note : returns false if the board wasn't changed, and simply returns the tiles as they were in the target
    517 // spx and spy is the space position while tx and ty is the target move from position
    518 
    519 bool PuzzleState::LegalMove( TILE *StartTiles, TILE *TargetTiles, int spx, int spy, int tx, int ty )
    520 {
    521 
    522 	int t;
    523 	
    524 	if( GetMap( spx, spy, StartTiles ) == GM_SPACE )
    525 	{
    526 		if( GetMap( tx, ty, StartTiles ) == GM_TILE )
    527 		{
    528 
    529 			// copy tiles
    530 			for( t=0; t<(BOARD_HEIGHT*BOARD_WIDTH); t++ )
    531 			{
    532 				TargetTiles[t] = StartTiles[t];
    533 			}
    534 
    535 
    536 			TargetTiles[ (ty*BOARD_WIDTH)+tx ] = StartTiles[ (spy*BOARD_WIDTH)+spx ];
    537 			TargetTiles[ (spy*BOARD_WIDTH)+spx ] = StartTiles[ (ty*BOARD_WIDTH)+tx ];
    538 
    539 			return true;
    540 		}
    541 	}
    542 
    543 
    544 	return false;
    545 
    546 }
    547 
    548 // This generates the successors to the given PuzzleState. It uses a helper function called
    549 // AddSuccessor to give the successors to the AStar class. The A* specific initialisation
    550 // is done for each node internally, so here you just set the state information that
    551 // is specific to the application
    552 bool PuzzleState::GetSuccessors( AStarSearch<PuzzleState> *astarsearch, PuzzleState *parent_node )
    553 {
    554 	PuzzleState NewNode;
    555 
    556 	int sp_x,sp_y;
    557 
    558 	GetSpacePosition( this, &sp_x, &sp_y );
    559 
    560 	bool ret;
    561 
    562 	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x, sp_y-1 ) == true )
    563 	{
    564 		ret = astarsearch->AddSuccessor( NewNode );
    565 
    566 		if( !ret ) return false;
    567 	}
    568 
    569 	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x, sp_y+1 ) == true )
    570 	{
    571 		ret = astarsearch->AddSuccessor( NewNode );
    572 		
    573 		if( !ret ) return false;
    574 	}
    575 
    576 	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x-1, sp_y ) == true )
    577 	{
    578 		ret = astarsearch->AddSuccessor( NewNode );
    579 
    580 		if( !ret ) return false;
    581 	}
    582 
    583 	if( LegalMove( tiles, NewNode.tiles, sp_x, sp_y, sp_x+1, sp_y ) == true )
    584 	{
    585 		ret = astarsearch->AddSuccessor( NewNode );
    586 	
    587 		if( !ret ) return false;
    588 	}
    589 
    590 	return true; 
    591 }
    592 
    593 // given this node, what does it cost to move to successor. In the case
    594 // of our map the answer is the map terrain value at this node since that is 
    595 // conceptually where we're moving
    596 
    597 float PuzzleState::GetCost( PuzzleState &successor )
    598 {
    599 	return 1.0f; // I love it when life is simple
    600 
    601 }
    602 
    603 
    604 // Main
    605 
    606 int main( int argc, char *argv[] )
    607 {
    608 
    609 	cout << "STL A* 8-puzzle solver implementation\n(C)2001 Justin Heyes-Jones\n";
    610 
    611 	bool bUserBoard = false;
    612 
    613 	if( argc > 1 )
    614 	{
    615 		char *userboard = argv[1];
    616 
    617 		int i = 0;
    618 		int c;
    619 
    620 		while( c = argv[1][i] )
    621 		{
    622 			if( isdigit( c ) )
    623 			{
    624 				int num = (c - '0');
    625 
    626 				PuzzleState::g_start[i] = static_cast<PuzzleState::TILE>(num);
    627 				
    628 			}
    629 		
    630 			i++;
    631 		}
    632 
    633 
    634 	}
    635 
    636 	// Create an instance of the search class...
    637 
    638 	AStarSearch<PuzzleState> astarsearch;
    639 
    640 	int NumTimesToSearch = NUM_TIMES_TO_RUN_SEARCH;
    641 
    642 	while( NumTimesToSearch-- )
    643 	{
    644 
    645 		// Create a start state
    646 		PuzzleState nodeStart( PuzzleState::g_start );
    647 
    648 		// Define the goal state
    649 		PuzzleState nodeEnd( PuzzleState::g_goal );
    650 
    651 		// Set Start and goal states
    652 		astarsearch.SetStartAndGoalStates( nodeStart, nodeEnd );
    653 
    654 		unsigned int SearchState;
    655 
    656 		unsigned int SearchSteps = 0;
    657 
    658 		do
    659 		{
    660 			SearchState = astarsearch.SearchStep();
    661 
    662 #if DEBUG_LISTS
    663 
    664 			float f,g,h;
    665 
    666 			cout << "Search step " << SearchSteps << endl;
    667 
    668 			cout << "Open:\n";
    669 			PuzzleState *p = astarsearch.GetOpenListStart( f,g,h );
    670 			while( p )
    671 			{
    672 				((PuzzleState *)p)->PrintNodeInfo();
    673 				cout << "f: " << f << " g: " << g << " h: " << h << "\n\n";
    674 				
    675 				p = astarsearch.GetOpenListNext( f,g,h );
    676 				
    677 			}
    678 
    679 			cout << "Closed:\n";
    680 			p = astarsearch.GetClosedListStart( f,g,h );
    681 			while( p )
    682 			{
    683 				p->PrintNodeInfo();
    684 				cout << "f: " << f << " g: " << g << " h: " << h << "\n\n";
    685 				
    686 				p = astarsearch.GetClosedListNext( f,g,h );
    687 			}
    688 
    689 #endif
    690 
    691 // Test cancel search
    692 #if 0
    693 			int StepCount = astarsearch.GetStepCount();
    694 			if( StepCount == 10 )
    695 			{
    696 				astarsearch.CancelSearch();
    697 			}
    698 #endif
    699 			SearchSteps++;
    700 		}
    701 		while( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_SEARCHING );
    702 
    703 		if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_SUCCEEDED )
    704 		{
    705 #if DISPLAY_SOLUTION_FORWARDS
    706 			cout << "Search found goal state\n";
    707 #endif
    708 			PuzzleState *node = astarsearch.GetSolutionStart();
    709 
    710 #if DISPLAY_SOLUTION_FORWARDS
    711 			cout << "Displaying solution\n";
    712 #endif
    713 			int steps = 0;
    714 
    715 #if DISPLAY_SOLUTION_FORWARDS
    716 			node->PrintNodeInfo();
    717 			cout << endl;
    718 #endif
    719 			for( ;; )
    720 			{
    721 				node = astarsearch.GetSolutionNext();
    722 
    723 				if( !node )
    724 				{
    725 					break;
    726 				}
    727 
    728 #if DISPLAY_SOLUTION_FORWARDS
    729 				node->PrintNodeInfo();
    730 				cout << endl;
    731 #endif
    732 				steps ++;
    733 			
    734 			};
    735 
    736 #if DISPLAY_SOLUTION_FORWARDS
    737 			// todo move step count into main algorithm
    738 			cout << "Solution steps " << steps << endl;
    739 #endif
    740 
    741 ////////////
    742 
    743 			node = astarsearch.GetSolutionEnd();
    744 
    745 #if DISPLAY_SOLUTION_BACKWARDS
    746 			cout << "Displaying reverse solution\n";
    747 #endif
    748 			steps = 0;
    749 
    750 			node->PrintNodeInfo();
    751 			cout << endl;
    752 			for( ;; )
    753 			{
    754 				node = astarsearch.GetSolutionPrev();
    755 
    756 				if( !node )
    757 				{
    758 					break;
    759 				}
    760 #if DISPLAY_SOLUTION_BACKWARDS
    761 				node->PrintNodeInfo();
    762                 cout << endl;
    763 #endif
    764 				steps ++;
    765 			
    766 			};
    767 
    768 #if DISPLAY_SOLUTION_BACKWARDS
    769 			cout << "Solution steps " << steps << endl;
    770 #endif
    771 
    772 //////////////
    773 
    774 			// Once you're done with the solution you can free the nodes up
    775 			astarsearch.FreeSolutionNodes();
    776 		
    777 		}
    778 		else if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_FAILED ) 
    779 		{
    780 #if DISPLAY_SOLUTION_INFO
    781 			cout << "Search terminated. Did not find goal state\n";
    782 #endif		
    783 		}
    784 		else if( SearchState == AStarSearch<PuzzleState>::SEARCH_STATE_OUT_OF_MEMORY ) 
    785 		{
    786 #if DISPLAY_SOLUTION_INFO
    787 			cout << "Search terminated. Out of memory\n";
    788 #endif		
    789 		}
    790 
    791 		
    792 
    793 		// Display the number of loops the search went through
    794 #if DISPLAY_SOLUTION_INFO
    795 		cout << "SearchSteps : " << astarsearch.GetStepCount() << endl;
    796 #endif
    797 	}
    798 
    799 	return 0;
    800 }
    801 
    802