(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;