home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / BM_STAR.ZIP / SOURCE.ZIP / ASTAR.C next >
Encoding:
C/C++ Source or Header  |  1992-07-27  |  26.5 KB  |  849 lines
  1. /**************************************************************
  2. //         Title:  Astar.c
  3. //27jul92-bm
  4. //    SOLVE 15-PUZZLE 
  5. // 
  6. //         by:  Bob McIsaac
  7.  **************************************************************/
  8. #include <dos.h>
  9. #include <bios.h>
  10. #include <conio.h>
  11. #include <graph.h>
  12. #include <malloc.h>
  13. #include <memory.h>
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <string.h>
  17. #include <time.h>
  18. #include "astar.h"
  19.  
  20. extern NPTR FreeHead; /* defined in linked.c */
  21.  
  22. /* global variables */
  23. PUZZLE Goal;            /* the ultimate Target */
  24. PUZZLE Source;          /* the input pattern */
  25. PUZZLE Choice;          /* the best one to reach goal */
  26. PUZZLE Tries[POLES];    /* temporary expansions */
  27. NPTR   FreePuzzles;     /* list of spare puzzle nodes */
  28. NPTR   Closed0;         /* list of puzzles already tried S->G */
  29. NPTR   Closed1;         /* list of puzzles already tried G->S */
  30. NPTR   CommonNode;      /* needed for solution path; */
  31. NPTR  Known0[HASH_SIZE];/* hashed list of known puzzles S->G */
  32. NPTR  Known1[HASH_SIZE];/* hashed list of known puzzles G->S */
  33. NPTR  Open0[FN_MAX];    /* heuristically open list S->G */
  34. NPTR  Open1[FN_MAX];    /* heuristically open list G->S */
  35.  
  36. char   *Gp;             /* the current goal */
  37. time_t Time1, Time2;    /* timer variables */
  38. unsigned long
  39.        ExpDown,         /* count of nodes expanded S to G */
  40.        ExpUp,           /* count of nodes expanded G go S */
  41.        Moves;           /* count of expansions attempted */
  42. unsigned int
  43.        Depth,           /* maximum depth of current search */
  44.        Level,           /* current position in a Dfs */
  45.        DownDepth,       /* how far from S->G */
  46.        UpDepth,         /* how far from G->S */
  47.        NodeNum;         /* count of linked nodes in use */
  48. int    Success;         /* set if goal with solution type */
  49. int    Direction;       /* move from goal to source if != 0 */
  50. int    Pausing;         /* pause and test for quit */
  51. int    Listing;         /* show open & closed lists */
  52. int    Puz_Show;        /* show puzzles */
  53. int    ResultInFile;
  54. int    (*Heuristic)();  /* pointer to function returning int */
  55. FILE   *Fp;
  56.  
  57. int JmpDistance[] = { -PW,      /* offset to North */
  58.                       +PW,      /* offset to South */
  59.                       +1,       /* offset to East */
  60.                       -1  };    /* offset to West */
  61. int ValidJmps[] = { 0x6,0xE,0xE,0xA,    /* direction masks */
  62.                     0x7,0xF,0xF,0xB,    /* for move rules */
  63.                     0x7,0xF,0xF,0xB,
  64.                     0x5,0xD,0xD,0x9 };
  65.  
  66. /* function prototypes */
  67. static int    Astar( PUZZLE *Pz, NPTR *Open, NPTR *Known,NPTR Closed );
  68. static int    BiAstar( void );
  69. static int    CharPos( char *Px, int ch );
  70. static void   ClearStates( int All );
  71. static int    DrawSym( int Row, int Col, char *Pz );
  72. static NPTR   DropPuzzles( NPTR Head );
  73. static void   DropTable( NPTR *Table, int Size );
  74. static NPTR   FindPuzLink( NPTR Pos, char *Px );
  75. static NPTR   FromOpen( NPTR *Table );
  76. static int    Generate( NPTR *OpenTable, NPTR *Known, NPTR Link );
  77. static NPTR   HashPuzzle( NPTR *Table, PUZZLE *Pz );
  78. static int    IfExistPuz( char *Pz, int TableNum );
  79. static void   KeyWait( void );
  80. static void   ListInFile( NPTR Head, int Level );
  81. static int    MakeKey( char *Pz );
  82. static NPTR   MakePuzNode( PUZZLE *Pz );
  83. static void   MakeTextRoom( void );
  84. static int    Manhattan( char *Px, char *Gx );
  85. static int    MisMatch( char *Px, char *Gx );
  86. static void   NoRoom( void );
  87. static NPTR   PushToOpen( NPTR *Table, NPTR Link );
  88. static void   ReleasePuzzles( void );
  89. static void   SetPos( char Row, char Col );
  90. static void   ShowHow( void );
  91. static void   ShowList( NPTR Link );
  92. static int    ShowMoves( void );
  93. static void   ShowSuccess( int Success );
  94. static void   ShowTable( NPTR *Table, int Size );
  95. static void   ShowTableLists( NPTR *Table, int Size );
  96. static void   Statistics( void );
  97. static int    TestKey( void );
  98.  
  99. /**************************************************************
  100. //     *** MAIN ***
  101. //
  102.  **************************************************************/
  103. void main( argc, argv ) int argc; char *argv[];
  104. {
  105.    char *Sptr, *Lptr;
  106.    int i, bpos, Done, ch;
  107.    NPTR L1, L2;
  108.    PUZZLE *Px, *Py;
  109.    _clearscreen(0);
  110.    if( strlen(argv[1]) != PSIZE )
  111.        ShowHow(); 
  112.    memcpy( Source.Puz, argv[1], PSIZE );
  113.    Source.Puz[PSIZE]=0;
  114.    strcpy( Source.Puz, strupr( Source.Puz ) );
  115.    strcpy( Goal.Puz, "123456789ABCDEF-" );
  116.    Goal.Gn = Goal.Hn = Source.Gn = Source.Hn = 0;
  117.    Closed0 = Closed1 = NULL;
  118.    NodeNum=0;
  119.    FreePuzzles = FreeHead =  NULL;
  120.    Time1 = Time2 = 0;
  121.    for( i=0; i<POLES; i++ )
  122.    {
  123.         Tries[i].Gn = Tries[i].Hn = INVALID ;
  124.    }
  125.    for( i=0; i<HASH_SIZE; i++ )
  126.    {
  127.        Known0[i] = NULL;        /* forward */
  128.        Known1[i] = NULL;        /* reverse */
  129.    }
  130.  
  131.    for( i=0; i<FN_MAX; i++ )    /* Fn range */
  132.    {
  133.        Open0[i] = NULL;         /* forward */
  134.        Open1[i] = NULL;         /* reverse */
  135.    }
  136.  
  137.    Heuristic = Manhattan;
  138.     memset( Choice.Puz, HOLE, PSIZE );
  139.    time( &Time1 );    /* start timer */
  140.    ShowMoves();
  141.  
  142.    if( argc>2 )
  143.        printf("\n%s  ** %s **",argv[1],argv[2]);
  144.    printf("\n Solve this puzzle <*/N>");
  145.    if( toupper(getch()) =='N' ) exit(0);
  146.    Pausing=NO;
  147.    printf("\n1. Display Puzzles");
  148.    printf("\n2. Display Lists");
  149.    printf("\n3. Save Result in file..BmResult.Tmp");
  150.    printf("\n0. Display Nothing");
  151.    ch = getch();
  152.    Puz_Show = ( ch=='1');
  153.    Listing  = ( ch=='2');
  154.    ResultInFile = ( ch=='3');
  155.  
  156.    if( ResultInFile )
  157.    {
  158.       if(( Fp = fopen( "BMresult.tmp","w" )) == NULL )
  159.       {
  160.           printf(" ** file open error ** ");
  161.           KeyWait();
  162.           exit(0);
  163.       }
  164.       else
  165.          printf("\nSolution File BMresult.tmp is open");
  166.    }
  167.    if( !ResultInFile && Listing||Puz_Show )
  168.    {
  169.       printf("\nPause while displaying 1=yes 0=no");
  170.       Pausing = ( getch()=='1' );
  171.    }
  172.    _clearscreen(0);
  173.    Choice = Source;
  174.     memset( Choice.Puz, HOLE, PSIZE );
  175.    time( &Time1 );
  176.    CommonNode=NULL;
  177.    ShowMoves();
  178.    cputs("\n..busy..");
  179.    Success = BiAstar();
  180.    time( &Time2 );
  181.    ShowMoves();
  182.    MakeTextRoom();
  183.    Statistics();
  184.    ShowSuccess( Success );
  185.    KeyWait();
  186.  
  187.    if( Fp != NULL )
  188.       fprintf(Fp,"\n%s  ** %s **",argv[1],argv[2]);
  189.    i = ( Success == StoG || Success == GtoS || Success == GtoS_K1 );
  190.    if( Fp != NULL && i )
  191.    {
  192.        fprintf(Fp,"\n..Final Closed List..");
  193.        fprintf(Fp,"\n..Trace solution path backwards to source..");
  194.        ShowList( Closed0 );
  195.        fprintf(Fp,"\n..Final Open List..");
  196.        ShowTableLists( Open0, FN_MAX );
  197.    }
  198.    ClearStates(1);
  199.    ReleasePuzzles();
  200.    if( Fp != NULL )
  201.    {  /* use external full screen viewer to scan solution */
  202.       fclose( Fp );
  203.       system("List BMresult.tmp");
  204.    }
  205.    exit(0);
  206. }
  207. /**************************************************************
  208. // Given a source puzzle, pointers to Open and Closed, perform
  209. // an A* search. Initially, Open and Closed are empty.
  210. // return success
  211. // GLOBALS: Choice,Gp,Depth
  212.  **************************************************************/
  213. static int Astar( Pz, OpenTable, Known, Closed )
  214.    PUZZLE *Pz; NPTR *OpenTable; NPTR *Known;  NPTR Closed;
  215. {
  216.    int i, j, Done;
  217.    NPTR L1;
  218.    Pz->Gn = 0;  
  219.    Pz->Hn = Manhattan( Pz->Puz , Gp );
  220.    L1 = MakePuzNode( Pz );
  221.    PushToOpen( OpenTable, L1 );
  222.    HashPuzzle( Known, (PUZZLE*)L1->Dptr );
  223.    Done = Success = NO;
  224.    while( !Done )
  225.    {
  226.       PUZZLE *Py;
  227.       if( Listing )
  228.       {
  229.         printf("\n&&&OPEN&&&");ShowTable(OpenTable, FN_MAX);
  230.         KeyWait;
  231.         printf("\n%%Known%%%");ShowTable( Known,HASH_SIZE);
  232.         KeyWait();
  233.         printf("\n@@Closed@@");ShowList( Closed );
  234.       }
  235.       L1 = FromOpen( OpenTable );
  236.       Closed = PushLink( Closed, L1 );
  237.       Py = (PUZZLE*)(Closed->Dptr);
  238.          if( Direction == FORWARD )
  239.             DownDepth = max( DownDepth, Py->Gn );
  240.          else
  241.             UpDepth = max( UpDepth, Py->Gn );
  242.       Success=( strcmp( Gp, Py->Puz )==0 );
  243.       if( !Success )
  244.       {
  245.          Generate( OpenTable, Known, Closed );
  246.       }
  247.       Done = ( Success || L1==NULL );
  248.    }
  249.    if( Direction == FORWARD )
  250.        Closed0 = Closed;
  251.    else
  252.        Closed1 = Closed;
  253.    return( Success );
  254. }
  255. /**************************************************************
  256. // Bidirectional A* search
  257. // return solution type: goal hit or common node w/ direction
  258. // GLOBALS: Success,Known[],Depth
  259.  **************************************************************/
  260. static int  BiAstar( void )
  261. {
  262.    int Solution = NO;
  263.    Depth = 1;
  264.    Success=NO;
  265.    ExpDown = ExpUp = 0L;  
  266.    DownDepth = UpDepth = 0;
  267.    while( !Success && Depth>0 )
  268.    {
  269.       Direction = FORWARD;
  270.       Gp = Goal.Puz;      
  271.       Solution = StoG;    
  272.       Success = Astar( &Source, Open0, Known0, Closed0 );
  273. Solution = Success;
  274.       if( !Success )
  275.       {
  276.       /* SaveDownData(); */
  277.          ClearStates(0);
  278.          Gp = Source.Puz;
  279.          Direction=REVERSE;
  280.          UpDepth = Depth;
  281.          Solution = GtoS;
  282. /*       Success = Astar( &Goal );*/
  283.       }
  284.    }
  285.    return(Solution);
  286. }
  287. /**************************************************************
  288. // CharPos()
  289. // Determine if 'ch' exists within puzzle string at Sptr.
  290. // Return integer offset from start of string to position.
  291. // Else trap system error.
  292.  **************************************************************/
  293. static int CharPos( Sptr, ch ) char *Sptr; int ch;
  294. {
  295.    static char *Lptr;
  296.    Lptr = strchr( Sptr, ch );
  297.    if ( *Lptr != (char)ch )
  298.    {
  299.       printf("\n** puzzle error ** %s",Sptr);
  300.       exit(0);
  301.    }
  302.    return( Lptr-Sptr );
  303. }
  304. /**************************************************************
  305. // the end of each iteration. That is, except for the nodes of
  306. // the state space at the depth bound. These must be preserved
  307. // before calling this function.
  308. // Note: Single step mode may be exception
  309.  **************************************************************/
  310. static void ClearStates( All ) int All;
  311. {
  312.    Closed0 = DropPuzzles( Closed0 );
  313.    Closed1 = DropPuzzles( Closed1 );
  314.    DropTable( Open0, FN_MAX );
  315.    DropTable( Open1, FN_MAX );
  316.    DropTable( Known0, HASH_SIZE );
  317.    DropTable( Known1, HASH_SIZE );
  318. }
  319. /**************************************************************
  320. // DrawSym()
  321. // display a puzzle given it's string and a starting position
  322.  **************************************************************/
  323. static int DrawSym( Row , Col, Sptr ) int Row; int Col; char *Sptr;
  324. {
  325.    int i,j;
  326.    for( j=0; j<PW; j++ )
  327.    {
  328.       SetPos( (char)Row, (char)Col );
  329.       for( i=0; i<PW; i++ )
  330.       {
  331.          printf(" %c",*Sptr++ );
  332.       }
  333.       Row+=1;
  334.    }
  335.    return(0);
  336. }
  337. /**************************************************************
  338. // DropPUzzles()
  339. // Reuse space already allocated for a Linked list of puzzles
  340. // Put these puzzle nodes on a linked list of free puzzles.
  341. // and return NULL to mark empty list;
  342. // See also SaveDownDat()
  343. // GLOBALS: FreePuzzles
  344.  **************************************************************/
  345. static NPTR   DropPuzzles( Head ) NPTR Head;
  346. {
  347.    NPTR L1;
  348.    while( Head != NULL )
  349.    {
  350.       L1 = Head->Next;
  351.       FreePuzzles = PushLink( FreePuzzles, Head );
  352.       Head = L1;
  353.    }
  354.    return( Head );
  355. }
  356. /**************************************************************
  357.    DropTable()
  358. // Free linked lists connected to a table of pointers
  359.  **************************************************************/
  360. static void   DropTable( Table, Size ) NPTR *Table; int Size;
  361. {
  362.    int i;
  363.    for( i=0; i<Size; i++ )
  364.    {
  365.       Table[i] = DropLinked( Table[i] );
  366.    }
  367. }
  368. /**************************************************************
  369.    FindPuzLink()
  370. // Return pointer to node in linked list of puzzles which
  371. // contains specified puzzle string.
  372. // GLOBALS:
  373.  **************************************************************/
  374. static NPTR   FindPuzLink( Pos, Sp ) NPTR Pos; char *Sp;
  375. {
  376.     int Found = NO;
  377.     while( Pos != NULL && !Found )
  378.     {
  379.        PUZZLE *Tmp = (PUZZLE*)Pos->Dptr;
  380.        Found = ( strcmp( Tmp->Puz, Sp )==0 );
  381.        if( !Found )
  382.           Pos = Pos->Next;
  383.     }
  384.     return( Pos );
  385. }
  386. /**************************************************************
  387.    FromOpen()
  388. // Retrieve item of lowest fn from heuristic open table
  389. // The heuristic table is scanned in ascending order to find
  390. // first pointer. Then the head of list is removed.
  391. // return null if open empty
  392.  **************************************************************/
  393. static NPTR FromOpen( Table ) NPTR *Table;
  394. {
  395.     NPTR L1 = NULL;
  396.     int i;
  397.     for( i=0; i<FN_MAX && L1 == NULL; i++ )
  398.     {
  399.        if( Table[i] != NULL )
  400.        {
  401.           L1 = PopLink( &Table[i] );
  402.        }
  403.     }
  404.     return( L1 );
  405. }
  406. /**************************************************************
  407.    Generate()
  408.  **************************************************************/
  409. static int Generate( OpenTable, Known, Link )
  410.        NPTR *OpenTable; NPTR *Known; NPTR Link;
  411. {
  412.    PUZZLE *Py = (PUZZLE*)Link->Dptr;
  413.    int i, bpos, ch, xd, Mask=1;
  414.    bpos = CharPos( Py->Puz, HOLE );     /* find open square*/
  415.    xd = ValidJmps[bpos];
  416.    for( i=0; i<POLES; i++ )             /* upto 4 moves possible*/
  417.    {  /* if move is possible copy puzzle and switch 2 squares*/
  418.        if( xd & Mask )
  419.        {
  420.             Moves++;    /* total # moves considered*/
  421.             strcpy( Tries[i].Puz, Py->Puz );
  422.             ch = Tries[i].Puz[bpos];    /* get the HOLE*/
  423.             Tries[i].Puz[bpos] = Tries[i].Puz[ bpos+JmpDistance[i] ];
  424.         Tries[i].Puz[ bpos+JmpDistance[i] ] = (char)ch;
  425.             if( !IfExistPuz( Tries[i].Puz, Direction ) )
  426.             {  /* if not in hash table, put new kids on open list*/
  427.                NPTR L1;
  428.                if( Direction != FORWARD )
  429.                  ExpUp++;
  430.                else
  431.                  ExpDown++;
  432.                Tries[i].Dad = Link->Num;        /* remember path*/
  433.                Tries[i].Gn = Py->Gn + 1;        /* increment Gn*/
  434.            Tries[i].Hn = Manhattan( Tries[i].Puz, Gp );
  435.                L1 = MakePuzNode( &Tries[i] );
  436.                PushToOpen( OpenTable, L1 );
  437.            HashPuzzle( Known, (PUZZLE*)L1->Dptr );
  438.             }
  439.        }
  440.        else
  441.             Tries[i].Gn = INVALID ;
  442.        Mask=Mask<<1;
  443.    }
  444.    if( Puz_Show)
  445.    {
  446.       memcpy( &Choice, Py, sizeof( PUZZLE ) );
  447.       ShowMoves();      /* optionally display children*/
  448.    }
  449.    return( 0 );
  450. }
  451. /**************************************************************
  452.    HashPuzzle()
  453. // Store a pointer to a puzzle in a hashed table. Note that a
  454. // puzzle pointer should already exist on the open list and this
  455. // table indirectly points to puzzles on open & closed.
  456. // return puzzle node pointer
  457. // GLOBALS:
  458.  **************************************************************/
  459. static NPTR HashPuzzle( Table, Pz ) NPTR *Table; PUZZLE *Pz;
  460. {
  461.    NPTR L1 ;    /* another link for collision chain*/
  462.    int i;
  463.    L1 = MakeLink( (char*)Pz, 0 );
  464.    if( L1 == NULL )
  465.       NoRoom();
  466.    i = MakeKey( Pz->Puz );      
  467.    Table[i] = PushLink( Table[i], L1 );
  468.    return( L1 );
  469. }
  470. /**************************************************************
  471.    IfExistPuz()
  472. // Determine if a given puzzle already exists in the selected
  473. // forward or reverse hash table.
  474. // GLOBALS: Known[]
  475.  **************************************************************/
  476. static int IfExistPuz( Pz, TableNum ) char *Pz; int TableNum;
  477. {
  478.    int Ans = NO;
  479.    NPTR Link;
  480.    if(  TableNum == FORWARD )
  481.         Link = Known0[ MakeKey( Pz ) ];
  482.    else
  483.         Link = Known1[ MakeKey( Pz ) ];
  484.    if( Link != NULL )
  485.    {
  486.       Link = FindPuzLink( Link, Pz );
  487.       Ans=( Link!=NULL );
  488.    }
  489.    return(Ans);
  490. }
  491. /**************************************************************
  492.  **************************************************************/
  493. static void KeyWait( void )
  494. {
  495.    printf(" ..key?" );
  496.    getch();
  497. }
  498. /**************************************************************
  499.  **************************************************************/
  500. static int Manhattan( Px, Gx ) char *Px; char *Gx;
  501. {
  502.    int xd, r1, r2, c1, c2, Dist;
  503.    r1 = c1 = Dist = 0;
  504.    while( *Px )
  505.    {
  506.        if ( *Px != HOLE  )
  507.        {
  508.            xd = CharPos( Gx, *Px );
  509.            r2 = xd/PW;
  510.            c2 = xd % PW;
  511.            Dist += ( abs( r2-r1 ) + abs( c2-c1 ) );
  512.        }
  513.        Px++;
  514.        c1++;
  515.        if( c1 >= PW )
  516.        {
  517.            c1=0;
  518.            r1++;
  519.        }
  520.    }
  521.    return( Dist );
  522. }
  523. /**************************************************************
  524.    MakeKey()
  525. // Given a 16-char puzzle string, pick every 4th char and
  526. // produce a long integer K by multiplication. Then return a
  527. // 16-bit integer result produced by  K mod Tp where Tp is
  528. // a prime number table size.
  529. // GLOBALS: Tp
  530. //  Letters:  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F  -
  531. //  Codes  : 31 32 33 34 35 36 37 38 39 65 66 67 68 69 70 45
  532.  **************************************************************/
  533. static int MakeKey( Sp ) char *Sp;
  534. {
  535.    ldiv_t Result;
  536.    long K1 ;
  537.    K1 = 1000L * *(Sp+15) + 100L * *(Sp+11) +
  538.           10L * *(Sp+ 7) + *Sp;
  539.    Result = ldiv( K1, (long)HASH_SIZE );
  540.    return( (int)Result.rem );  /* quotient not needed */
  541. }
  542. /**************************************************************
  543.  **************************************************************/
  544. static NPTR   MakePuzNode( Px )  PUZZLE *Px;
  545. {
  546.    NPTR Link = PopLink( &FreePuzzles );  /* recycle an old puzzle*/
  547.    if( Link == NULL )
  548.    {
  549.        PUZZLE *Puz = (PUZZLE*)malloc( sizeof(PUZZLE) );
  550.        if( Puz != NULL )
  551.            Link = MakeLink( (char*)Puz, 0 );
  552.        if( Puz == NULL || Link == NULL )
  553.        {
  554.           NoRoom();
  555.        }
  556.    }
  557.    memcpy( (PUZZLE*)Link->Dptr, Px, sizeof(PUZZLE) );
  558.    Link->Num = ++NodeNum;       /* count puzzles created*/
  559.    return( Link );
  560. }
  561. /**************************************************************
  562.    MakeTextRoom()
  563. // erase expansion area of puzzle screen where child nodes
  564. // are optionally displayed.
  565.  **************************************************************/
  566. static void MakeTextRoom( void )
  567. {
  568.    int Row, Col;
  569.    for( Row=8; Row<23; Row++ )
  570.    {
  571.       SetPos( (char)Row,0);
  572.       for( Col=0; Col < 78; Col++)
  573.           putch(' ');
  574.    }
  575.    SetPos(8,0);
  576. }
  577. /**************************************************************
  578.    MisMatch()
  579. // Compare puzzle string to goal
  580. // return count of mismatches
  581. // GLOBALS:
  582.  **************************************************************/
  583. static int MisMatch( Px, Gx )  char *Px; char *Gx;
  584. {
  585.    int Mis = 0;
  586. /* while( *Px )
  587.    {   // this count includes the "blank"
  588.        Mis += ( *Px++ != *Gx++ );
  589.    } */
  590.    while( *Px )
  591.    {   /* this one does not include the blank */
  592.        Mis += ( *Px != *Gx && *Px != HOLE && *Gx != HOLE );
  593.        Px++;
  594.        Gx++;
  595.    }
  596.    return( Mis );
  597. }
  598. /**************************************************************
  599.  **************************************************************/
  600. static void NoRoom( void )
  601. {
  602.    time( &Time2 );
  603.    MakeTextRoom();
  604.    printf("\n*** no heap space ***\n");
  605.    Statistics();
  606.    ClearStates(1);
  607.    KeyWait();
  608.    exit(0);
  609. }
  610. /**************************************************************
  611.    PushToOpen()
  612. // Add link to specified OPEN table in heuristic order
  613. // Use the Fn value as table index, then push the new
  614. // link on the list of equal values at that location
  615. // return addrs of puzzle link
  616. // GLOBALS: Gp
  617.  **************************************************************/
  618. static NPTR PushToOpen( Table, Link )  NPTR *Table; NPTR Link;
  619. {
  620.     PUZZLE *Px = (PUZZLE*)Link->Dptr;
  621.     int Fn = Px->Hn + Px->Gn;
  622.     if( Fn >= FN_MAX )
  623.     {
  624.        printf("\nProgram Error: Heuristic table too small");
  625.        exit(0);
  626.     }
  627.     Table[Fn] = PushLink( Table[Fn], Link );
  628.     return( Link );
  629. }
  630. /**************************************************************
  631.    ReleasePuzzles()
  632. // Unallocate puzzles kept on spare list
  633. // GLOBALS: FreePuzzles, FreeHead
  634.  **************************************************************/
  635. static void ReleasePuzzles( void )
  636. {
  637.     NPTR Tmp = FreePuzzles;
  638.     PUZZLE *Px;
  639.     while( Tmp != NULL )
  640.     {
  641.         Px = (PUZZLE*)Tmp->Dptr;
  642.         free( Px );
  643.         FreeHead = PushLink( FreeHead, PopLink(  &FreePuzzles ) );
  644.         Tmp = FreePuzzles;
  645.     }
  646.     ReleaseNodes();
  647. }
  648. /**************************************************************
  649. // 
  650.  **************************************************************/
  651. static void SetPos( Row, Col )
  652.             char Row; char Col;
  653. {  _settextposition( Row, Col );
  654. }
  655. /**************************************************************
  656.    ShowList()
  657. // Display a linked list of puzzles, if file is open, also
  658. // output to the text file.
  659. // GLOBALS: FILE *Fp
  660.  **************************************************************/
  661. static void   ShowList( Link )  NPTR Link;
  662. {
  663.    PUZZLE *Pz;
  664.    unsigned int Row=0;
  665.    if( Link== NULL ) printf("\nNULL list..");
  666.    while( Link != NULL )
  667.    {
  668.        Pz = (PUZZLE*)Link->Dptr;
  669.        if( Fp != NULL )
  670.        {  /* if result file open */
  671.           fprintf(Fp,"\n NodeNum: %5d  Gn: %4d  Hn: %3d  Dad %5d  %s",
  672.              Link->Num, Pz->Gn, Pz->Hn,Pz->Dad, Pz->Puz );
  673.        }
  674.        else
  675.        {
  676.           printf("\n NodeNum: %5d  Gn: %4d  Hn: %3d  Dad %5d %s",
  677.               Link->Num, Pz->Gn, Pz->Hn,Pz->Dad, Pz->Puz );
  678.        }
  679.        Link = Link->Next;
  680.        if( ++Row % 12 == 0 && Fp==NULL )
  681.        {
  682.           KeyWait();
  683.        }
  684.    }
  685.    if( Fp==NULL) KeyWait();
  686. }
  687. /**************************************************************
  688.  **************************************************************/
  689. static int ShowMoves( void )
  690. {
  691.    int i;
  692.    time_t Ticks;
  693.    SetPos(0,4);
  694.    printf("-Source-");
  695.  
  696.    DrawSym( 2,4,Source.Puz );
  697.    SetPos(0,16);
  698.    printf("-Choice-");
  699.    DrawSym( 2,16,Choice.Puz );
  700.    SetPos( 0,28 );
  701.    printf("-Goal---");
  702.    DrawSym( 2,28,Goal.Puz );
  703.    SetPos(0,50);
  704.    if( Direction != FORWARD )
  705.       printf("G-->S: %ld",ExpUp);
  706.    else
  707.       printf("S-->G: %ld",ExpDown);
  708.    SetPos(1,50);
  709.       printf("Tries: %ld",ExpDown+ExpUp);
  710.    SetPos(2,50);
  711.    time( &Ticks );
  712.    printf("Clock: %f ",difftime( Ticks, Time1 ) );
  713.    SetPos(3,50);
  714.    printf("Depth: %ld",(long)Depth );
  715.    SetPos(4,50);
  716.    printf("Moves: %ld",(long)Moves );
  717.    SetPos(8,12);printf("\nA-Star Algorithm -- by Bob McIsaac");
  718.    for( i=0; i < POLES; i++ )
  719.        if( Tries[i].Gn == INVALID )
  720.             memset( Tries[i].Puz, HOLE, PSIZE );
  721.    SetPos(12, 4); printf("%5d",Tries[0].Gn );
  722.    SetPos(12,16); printf("%5d",Tries[1].Gn );
  723.    SetPos(12,28); printf("%5d",Tries[2].Gn );
  724.    SetPos(12,40); printf("%5d",Tries[3].Gn );
  725.    printf(" . . . Gn");
  726.    DrawSym(14, 4,Tries[0].Puz );
  727.    DrawSym(14,16,Tries[1].Puz );
  728.    DrawSym(14,28,Tries[2].Puz );
  729.    DrawSym(14,40,Tries[3].Puz );
  730.    putchar('\n');
  731.    if( TestKey() ) exit(0);
  732.    return(0);
  733. }
  734. /**************************************************************
  735.  **************************************************************/
  736. static void   ShowTable( Table, Size )  NPTR *Table; int Size;
  737. {
  738.    PUZZLE *Pz;
  739.    NPTR Link;
  740.    unsigned int i, Row=0;
  741.    for( i=0; i<(UINT)Size; i++ )
  742.    {
  743.       Link = Table[i];
  744.       Row=0;
  745.       while( Link != NULL )
  746.       {
  747.          Pz = (PUZZLE*)Link->Dptr;
  748.          printf("\n Table___: key %4d Gn %4d Hn %4d %s",
  749.                     i,Pz->Gn,Pz->Hn,Pz->Puz );
  750.          Link = Link->Next;
  751.          if( ++Row % 12 == 0 ) KeyWait();
  752.       }
  753.    }
  754. }
  755. /**************************************************************
  756.    ShowTableLists()
  757. // This will show show all the linked list found in an array
  758. // of pointers. Handy for writing the open list to the
  759. // solution file
  760.  **************************************************************/
  761. static void   ShowTableLists( Table, Size )  NPTR *Table; int Size;
  762. {
  763.    int i;
  764.    for( i=0; i<Size; i++ )
  765.    {
  766.       NPTR Link = Table[i];
  767.       if( Link != NULL )
  768.       {
  769.          ShowList( Link );
  770.       }
  771.    }
  772. }
  773. /**************************************************************
  774.  **************************************************************/
  775. static void ShowHow(void)
  776. {
  777.    int i;
  778.    printf("\nUSAGE: Astar <puzzle string>");
  779.    printf("\nEx:");
  780.    printf("\n   Astar 123456789ABCDEF-");
  781.    printf("\n   or use STARTEST.BAT");
  782.    exit(0);
  783. }
  784. /**************************************************************
  785.  **************************************************************/
  786. static void ShowSuccess( Success ) int Success;
  787. {
  788.    printf("\n $$$ success $$$ %d",Success );
  789.    switch( Success )
  790.    {
  791.        case StoG:
  792.           printf("\nGoal found on S->G search (step K)");
  793.           break;
  794.        case GtoS:
  795.           printf("\nSource found on G->S search (step K)");
  796.           break;
  797.        case GtoS_COM:
  798.           printf("\nCommon found on G->S search (step K)");
  799.           break;
  800.        case GtoS_K1:
  801.           printf("\nSource found on G->S search (K+1)");
  802.           break;
  803.        case GtoS_K1_COM:
  804.           printf("\nCommon found on G->S search (K+1)");
  805.           break;
  806.        default: break;
  807.    }
  808. }
  809. /**************************************************************
  810.  **************************************************************/
  811. static int TestKey()
  812. {
  813.    int Ans = 0;
  814.    if( Pausing )
  815.    {
  816.       printf("\n 1=more  0=quit >>" );
  817.       Ans = ( getch()=='0');
  818.    }
  819.    return( Ans );
  820. }
  821. /**************************************************************
  822.  **************************************************************/
  823. static void Statistics( void )
  824. {
  825.    if( Fp == NULL )
  826.    {
  827.       printf("\nClock: %6.2f Seconds",difftime( Time2, Time1 ) );
  828.       printf("\nNodes Expanded: S->G %6ld  Depth %d",
  829.                 ExpDown,DownDepth );
  830.       printf("\nNodes Expanded: G->S %6ld  Depth %d",
  831.                 ExpUp,UpDepth);
  832.       printf("\nMoves Considered:    %6ld", Moves);
  833.       printf("\nPuzzles generated:   %6ld",(long)NodeNum );
  834.    }
  835.    else  /* write to BmResult.Tmp */
  836.    {
  837.       fprintf(Fp,"\n\nA-Star Algorithm --- by Bob McIsaac" );
  838.       fprintf(Fp,"\nUsing Manhattan Heuristic" );
  839.       fprintf(Fp,"\nClock: %6.1f Seconds",difftime( Time2, Time1 ) );
  840.       fprintf(Fp,"\nNodes Expanded: S->G %6ld  Depth %d",
  841.                 ExpDown,DownDepth );
  842.       fprintf(Fp,"\nNodes Expanded: G->S %6ld  Depth %d",
  843.                 ExpUp,UpDepth);
  844.       fprintf(Fp,"\nMoves Considered:    %6ld", Moves);
  845.       fprintf(Fp,"\nPuzzles generated:   %6ld",(long)NodeNum );
  846.    }
  847. }
  848.  
  849.