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