Peg Solitaire - SAS Code To Solve The Triangular Board

SAS Code To Solve The Triangular Board

This solution has been proposed by Houliang Li, Frederick, MD. The board is represented as a string of hexadecimal integers starting from the top and going left to right. The empty space is indexed by zero.

options nosymbolgen nomprint nomlogic mcompilenote=NOAUTOCALL; /***it takes about six minutes to find a solution starting with the hole at the top of the pegboard***/ %macro pegboard (start, moves, backtostart=NO, allsolutions=NO) ; /*start is the peg lineup for each function call and is always 15 character long*/ /*moves keeps track of all legal moves made so far*/ /*backstart=YES if the solution in which the final peg is in the initial hole is desired*/ /*allsolutions=YES if all solutions to a particular starting lineup are requested*/ /*initial setup*/ %local index;/*it is local so that it can keep a separate record of the iterations over the possible legal moves during each macro's execution*/ %if %length(%sysfunc(compress(&start, 0)))=14 %then %do; %global originalstart starthole success legalmoves; %let originalstart=&start; %let starthole= %index(&start,0); %let success = 0 ; %let legalmoves=124|247|47b|b74|742|421|136|36a|6af|fa6|a63|631|bcd|cde|def|fed|edc||dcb|358|58c|c85|853|259|59e|e95|952|789|89a|a98|987|69d|d96|48d|d84|456|654; %end; /*loop over possible legal moves*/ %do index=1 %to 36;/***>>><<<***/ %if not &success or (&success and %upcase(&allsolutions)=YES) %then %do;/***XXXXXX***/ /*if it is not a solution and there are no particular request made with the macro parameters*/ /*PREPARE FOR THE INDEX-TH MOVE*/ %let nextmove=%scan(&legalmoves,&index, |); /*extract from string legalmoves the index-th word (i.e. a single move) and put it in the variable next move*/ %let first=%substr(&nextmove,1,1); /*name the pegs involved in the move*/ %let second=%substr(&nextmove,2,1); %let third=%substr(&nextmove,3,1); /*conversion from hexadecimal digits, used in parts to represent pegs, to decimal equivalents*/ %if &first > 9 %then %let first=%eval(%sysfunc(rank(&first))-87); /*rank returns an integer that represent the character in the ASCII collating sequence*/ %if &second > 9 %then %let second=%eval(%sysfunc(rank(&second))-87); %if &third > 9 %then %let third=%eval(%sysfunc(rank(&third))-87); %if %substr(&start,&first,1)>0 and %substr(&start,&second,1)>0 and %substr(&start,&third,1)=0 %then %do; /***§§§§§§***/ /*if the first peg can jump over the second and land in a hole*/ /*DO THE INDEX-TH MOVE*/ %let allmoves = &moves &first - &second - &third; /* take note of the move in the variable allmoves*/ %if &first = 1 %then /*if the jumping peg was in the move is at the top of the pegboard*/ %let newstart=0%substr(&start,2);/*put a hole in the starting point of the jumping peg in the new pegboard*/ %else %if &first=15 %then /*if the first peg involved in the move is at the bottom right angle of the pegboard*/ %let newstart=%substr(&start,1,14)0;/*put a hole in the new pegboard in the bottom right angle*/ %else %let newstart=%substr(&start,1,&first - 1)0%substr(&start,&first + 1); /*put a hole in the new pegboard at the starting position of the jumping peg*/ %let newstart=%substr(&newstart,1,&second - 1)0%substr(&newstart,&second + 1); /*put a hole at the place of the jumped peg which is taken away from the pegboard*/ %if &third=1 %then /*if the third place involved in the move, the landing place of the jumping peg, is the top place of the pegboard*/ %let newstart=%substr(&start,&first,1)%substr(&newstart,2); /*take the first peg involved in the move and put it in the first place of the new pegboard*/ %else %if &third=15 %then /*if the third place of the move is the bottom right angle*/ %let newstart=%substr(&newstart,1,14)%substr(&start,&first,1); /*put the jumping peg in the bottom right angle of the new pegboard*/ %else %let newstart = %substr(&newstart,1,&third - 1)%substr(&start,&first,1)%substr(&newstart,&third +1); /*put in the landing place of the new pegboard the jumping peg involved in the move*/ %if %length(%sysfunc(compress(&newstart,0)))=1 and (%upcase(&backtostart)=NO or %upcase(&backtostart)=YES and %substr(&newstart,&starthole,1)>0) %then %do; /*if the new pegboard has a unique peg and there are no particular request made with the macro parameter */ %let success=1; %put Starting position is: &originalstart; %put successful moves are: &allmoves; %end; %else %do; %pegboard(&newstart,&allmoves); %end; %end;/***§§§§§§***/ %end;/***XXXXXX***/ %end;/***>>><<<***/ %mend pegboard;

To execute this program the following call has to be done with the initial configuration of the board passed as a parameter.

%pegboard(023456789abcdef, )