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