(very long) development styles

Lynn H. Maxson lmaxson@pacbell.net
Mon, 21 Aug 2000 22:38:10 -0700 (PDT)


I offer the following PL/I version of the peg solitaire game.  While any successful 
solution is as good as any other (as they all require the same number of moves) this 
program will run until stopped by the user or until it runs to completion 
(unlikely).  Every successful solution found will be appended to the output file 
'pegboard.txt', which can be processed (read) by another program while this one is 
running.  It also means that if stopped by the user, all successful solutions found 
up to that point are saved.

 peg_sol4:
   Proc options (main);

     /*
       Overview
     */

     /*
       This program defines a depth-first approach to the solution of
       peg solitaire where success occurs when no valid move is
       possible and only one peg remains (level 32).

       A valid move is possible from any row or column in which either
       a 'pp.' or '.pp' exists.  The move replaces the patterns with
       '..p' or 'p..' respectively.  As a result each move reduces the
       number of pegs by one (or increases the set of empty peg holes
       by one).

       The algorithm assumes an initial move (level 1) in which a
       single peg is removed from the center position (4,4) of the
       board.  There are then 32 possible board levels where the
       level number equals the number of empty peg holes.

       The depth-first approach uses recursion, knowing that the number
       of levels cannot exceed 32.  This sets a finite limit on path
       length from the initial board.  The depth-first approach
       explores every path from the initial board to every end node,
       a node from which no further move is possible.

       If a "no move possible" occurs at level 32, i.e. only a single
       peg remains, the entire level array, representing the complete
       path of the successful solution, is written out (appended) to
       a file.  The file is opened, written, and closed each time.
       This allows the user to stop the processing at any point with
       the successful solutions up to that point saved.

       This algorithm takes advantage of the fact that the four valid
       moves from the initial board are topologically equivalent.  Thus
       we need only solve for one of the four possible moves.  For any
       successful solution we can rotate it 90, 180, and 270 degrees to
       determine the solutions for the other three moves.
     */



     /*
       initialize levels in level array
     */
     do i1 = 1 to 32;
       lev_a(i1).level           = i1;
     end; /* do i1 */

     /*
       create initial pegboard (level 1)
     */
     pbap                           = addr(lev_a(1).peg_b(1,1));
     pbv(1), pbv(2), pbv(6), pbv(7) = '--ppp--';
     pbv(3), pbv(5)                 = 'ppppppp';
     pbv(4)                         = 'ppp.ppp';

     /*
       create pre-determined first move pegboard
     */
     pbap                           = addr(lev_a(2).peg_b(1,1));
     pbv(1), pbv(2), pbv(6), pbv(7) = '--ppp--';
     pbv(3), pbv(5)                 = 'ppppppp';
     pbv(4)                         = 'p..pppp';

     /*
       Search for solution
     */
     curr_move  = addr(lev_a(2).peg_b(1,1));
     curr_lev  = lev_a(2).level;
     rc = create_moves(curr_move, curr_lev);
     return;
    /*
      Data Definitions
    */

    /*
      PL/I builtin functions used
    */
     dcl addr      builtin;
     dcl plimove   builtin;

    /*
      Miscellaneous variables
    */

     dcl rc        fixed bin (31) static;
     dcl curr_move ptr static;
     dcl curr_lev  fixed bin(31) static;
     dcl i1        fixed bin(31) static;

    /*
      Overlay definitions for level array pegboard
    */

     dcl pbv (7)   char(7) based (pbap);
     dcl pbap      ptr static;

     /*
       Define level array
     */
     dcl 1 lev_a (32) static aligned,
           2 level fixed bin(31),
           2 peg_b (7,7) char(1);

     /*
       Define output file
     */
     dcl file_a file record output sequential;

     /*
 set dd:file_a=pegboard.txt,append(y),recsize(1789),share(read),
 type(crlf)
     */

     /*
       End data definitions
     */

     create_moves:
       proc (curr_mov, curr_lev) returns(fixed bin(31)) recursive;
         /*
           if this level 32 (a successful solution), then write the
           entire path to an external data set.
         */
         if curr_lev = 32
         then do;
           open file(file_a);
           write file(file_a) from (lev_a);
           close file(file_a);
           return(0);
         end; /* then */
         /*
           Set up address this level
         */
         next_lev                = curr_lev + 1;
         next_mov                = addr(lev_a(next_lev).peg_b(1,1));
         do i1 = 1 to 7;
           do i2 = 1 to 5;
             /* search rows
             */
             /* case 1
             */
             if curr_mov->pba(i1,i2)   = 'p' &
                curr_mov->pba(i1,i2+1) = 'p' &
                curr_mov->pba(i1,i2+2) = '.'
             then do;
               call plimove(next_mov, curr_mov, 49);
               next_mov->pba(i1,i2)    = '.';
               next_mov->pba(i1,i2+1)  = '.';
               next_mov->pba(i1,i2+2)  = 'p';
               rc = create_moves(next_mov, next_lev);
             end; /* then */
             /* case 2
             */
             if curr_mov->pba(i1,i2)   = '.' &
                curr_mov->pba(i1,i2+1) = 'p' &
                curr_mov->pba(i1,i2+2) = 'p'
             then do;
               call plimove(next_mov, curr_mov, 49);
               next_mov->pba(i1,i2)    = 'p';
               next_mov->pba(i1,i2+1)  = '.';
               next_mov->pba(i1,i2+2)  = '.';
               rc = create_moves(next_mov, next_lev);
             end; /* then */

             /* search columns
             */
             /* case 3
             */
             if curr_mov->pba(i2,i1)   = 'p' &
                curr_mov->pba(i2+1,i1) = 'p' &
                curr_mov->pba(i2+2,i1) = '.'
             then do;
               call plimove(next_mov, curr_mov, 49);
               next_mov->pba(i2,i1)    = '.';
               next_mov->pba(i2+1,i1)  = '.';
               next_mov->pba(i2+2,i1)  = 'p';
               rc = create_moves(next_mov, next_lev);
             end; /* then */
             /* case 4
             */
             if curr_mov->pba(i2,i1)   = '.' &
                curr_mov->pba(i2+1,i1) = 'p' &
                curr_mov->pba(i2+2,i1) = 'p'
             then do;
               call plimove(next_mov, curr_mov, 49);
               next_mov->pba(i2,i1)    = 'p';
               next_mov->pba(i2+1,i1)  = '.';
               next_mov->pba(i2+2,i1)  = '.';
               rc = create_moves(next_mov, next_lev);
             end; /* then */
           end; /* do i2 */
         end; /* do i1 */
         return(0);
         /*
           Data definitions for create_moves
         */
         dcl (i1, i2) fixed bin (31);
         dcl next_lev fixed bin(31);
         dcl curr_lev fixed bin(31);
         dcl curr_mov ptr;
         dcl next_mov ptr;
         dcl pba (7,7) char(1) based;
         /*
           End data definitions
         */
       end create_moves;

   End  peg_sol4;