######################################################################
##PEG: Save this file as PEG. To use it, stay in the                 #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read PEG: <Enter>                                 #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Temple University ,                   #
#zeilberg@math.temple.edu.                                           # 
#######################################################################
 
#Created: MAy 12, 2000
#This version: May 12, 2000
#PEG: A Maple package to study the PEG-Solitaire
#Please report bugs to zeilberg@math.temple.edu
 
 
 
print(`Created: May 12, 2000.`):
print(`This version: May 12, 2000`):
lprint(``):
print(`PEG: A Maple package to play Peg-Solitaire on general boards`):
print(`Written by Doron Zeilberger, zeilberg@math.temple.edu`):
lprint(``):
print(`Please report bugs to zeilberg@math.temple.edu`):
lprint(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.temple.edu/~zeilberg/`):
 print(`For a list of the MAIN procedures type ezra(), for help with`):
 print(`For a list of all procedures type ezra1(), for help with`):
 print(`a specific procedure, type ezra(procedure_name)`):
 print(``):
ezra1:=proc()
if args=NULL then
 print(`Contains the following procedures: BestRand, `):
 print(` BestRandC, BestRandE, BestRandR, BestRandT`):
 print(` BoardCross, BoardRect, BoardTri, BTpath,BTpathE, BTpathR, BTpathT,`):
 print(` ChopFvar, CompoundMoves, CompoundMovesSt, CrossTriples `):
 print(` Demo, DemoE, DemoT, DemoTg`):
 print(` DemoTPH, Desc, DescS, DescT, DescST,DrawPOS ,`):
 print(` DrawPOSAB, DrawPOSABg, DrawPOSABPH`):
 print(` IniRect, IniTri, MinPath, MinPathC, MinPathE,,`):
 print(` MinPathT, NextMoves, NextMovesRank, NextMovesSt, NuSons `):
 print(`Path, Path1, Paths, PathT, PlayGreedy, `):
 print(` PlayGreedyT,PlayRand, PlayRandT, PreviousMoves,RecTriples, `):
 print(` TriTriples `):
 print(``):
 print(` For help with any procedure, type: ezra(proc_name): `);
fi:
 
end:
ezra:=proc()
if args=NULL then
 print(`Contains the following procedures: BestRand, BestRandC `):
 print(` BestRandE, BestRandR, BestRandT`):
 print(`  BoardTri, BTpath, BTpathE, BTpathR, BTpathT, `):
 print(` Demo, DemoE, DemoT,Desc, DescS , DescT, DescST , MinPath, `):
 print(` MinPathC, MinPathE, MinPathT  `):
 print(`  NextMoves, Path, Paths, PathT, PlayGreedy, `):
 print(` PlayGreedyT,PlayRand, PlayRandT  `):
 print(``):
 print(`We also have 3 pre-computed solutions: Best5 for Hi-Q of size 5`):
 print(` i.e. an equilateral-triangle board of size 5 `):
 print(` Best6 for Hi-Q of size 6`):
 print(` i.e. an equilateral-triangle board of size 6 `):
 print(` BestE for standard Peg-Solitaire of an English Board`):
fi:
 
if nops([args])=1 and op(1,[args])=BestRand then
print(`BestRand(POS,TRIPLES,K): by playing randomly K times`):
print(`finds the best sequence of moves, if it encounters 1`):
print(`peg left, it stops right away`):
fi:
 
if nops([args])=1 and op(1,[args])=BestRandC then
print(`BestRandC(X,Y,x1,x2,y1,y2,loca,K): Plays up to K randon`):
print(` Solitaire game on a board given by BoardCross(X,Y,x1,x2,y1,y2)`):
print(`loca is empty; it picks the best`):
fi:
 
if nops([args])=1 and op(1,[args])=BestRandE then
print(`BestRandE(K): Plays up to K randon Peg-Solitaire game`):
print(`on a standard English board with the middle peg removed `):
fi:
 
if nops([args])=1 and op(1,[args])=BestRandR then
print(`BestRandR(a,b,loca,K): Plays up to K randon Solitaire game`):
print(`on an a by b rectangular board where the location`):
print(`loca is empty; it picks the best`):
fi:
 
if nops([args])=1 and op(1,[args])=BestRandT then
print(`BestRandT(n,K): Plays K randon Solitaire game`):
print(`on an equilateral-triangular board of side n`):
print(`where the top peg is removed and picks the best`):
fi:
 
if nops([args])=1 and op(1,[args])=BoardCross then
print(`BoardCross(X,Y,x1,x2,y1,y2): The `):
print(` board of a Cross-shaped with a center part `):
print(`that is [0,X-1]x[0,Y-1] and on the right side there is a rectangle`):
print(`[X,X+x2-1]x[0,Y-1], on the left there is the rectangle`):
print(`[-(x1-1),0]x[0,Y-1], on the top there is the rectangle`):
print(`[0,X-1]x[Y,Y+y2-1], and on the bottom there is the retangle`):
print(`[0,X-1]x[-y1,-1], and loca removed`):
fi:
 
if nops([args])=1 and op(1,[args])=BoardRect then
print(`BoardRect(a,b): The locations in an a by b rectangular board`):
fi:
 
if nops([args])=1 and op(1,[args])=BoardTri then
print(`BoardTri(n): The locations in an equilateral`):
print(`triangle board of side n`):
fi:
 
if nops([args])=1 and op(1,[args])=BTpath then
print(`BTpath(POS,TRIPLES): finds a path with optimal end`):
print(`starting at position POS, in a Peg-Solitaire game `):
print(`defined by the set of triples TRIPLES`):
fi:
 
if nops([args])=1 and op(1,[args])=BTpathE then
print(`BTpathE(): Using BackTrack to solve the Peg-Solitaire puzzle`):
print(`on a standard English board  `):
fi:
 
if nops([args])=1 and op(1,[args])=BTpathR then
print(`BTpathR(a,b,loca): Using BackTrack to solve the Peg-Solitaire puzzle`):
print(`for an a by b rect. board with the inital location loca empty`):
fi:
 
if nops([args])=1 and op(1,[args])=BTpathT then
print(`BTpathT(n): Using BackTrack to solve the Peg-Solitaire puzzle`):
fi:
 
if nops([args])=1 and op(1,[args])=ChopFvar then
print(`ChopFvar(F,var): Given a polynomial F in the variables in`):
print(`the set var, only retains the terms where the powers of`):
print(`the elements of var have degree 0 or 1`):
fi:
 
if nops([args])=1 and op(1,[args])=CompoundMoves then
print(`CompoundMoves(POS,TRIPLES): All the compund moves that`):
print(`from position POS, with the triples TRIPLES`):
fi:
 
if nops([args])=1 and op(1,[args])=CompoundMovesSt then
print(`CompoundMovesSt(POS,TRIPLES,St): All the compund moves that`):
print(`at St from position POS, with the triples TRIPLES`):
fi:
 
if nops([args])=1 and op(1,[args])=CrossTriples then
print(`CrossTriples(X,Y,x1,x2,y1,y2): all the Triples in `):
print(`a cross board given by BoardCross(X,Y,x1,x2,y1,y2)`):
fi:
 
if nops([args])=1 and op(1,[args])=Demo then
print(`Demo(INI,hole,Moves,A,B): Given the initial postion of the`):
print(`locations of pegs (a set of points), the hole, and`):
print(`a sequence of Moves, and two strings A and B`):
print(`shows the sequence of partial positions, and which peg`):
print(`(denoted by A) to go over the peg marked with B`):
fi:
 
if nops([args])=1 and op(1,[args])=DemoE then
print(`DemoE(Moves,A,B): Given a sequence of moves Moves`):
print(`for Peg-Solitaire on the standard English boarda`):
print(` with the hole at the middle, returns the sequence`):
print(`of plots that demonstrate the moves and the partial`):
print(`results, where A is denotes the peg to be lifted`):
print(`and B the neigboring peg over which it is to be lifted`):
fi:
 
if nops([args])=1 and op(1,[args])=DemoT then
print(`DemoT(n,hole,Moves,A,B): Given a sequence of moves Moves`):
print(`for Peg-Solitaire on the equilateral triangular-board of`):
print(`side n, with the hole at hole, returns the sequence`):
print(`of plots that demonstrate the moves and the partial`):
print(`results, where A is denotes the peg to be lifted`):
print(`and B the neigboring peg over which it is to be lifted`):
fi:
 
if nops([args])=1 and op(1,[args])=DemoTg then
print(`DemoTg(n,hole,Moves,A,B): `):
print(`Like DemoT(n,hole,Moves,A,B): but Moves is a sequence`):
print(`of compound moves`):
fi:
 
if nops([args])=1 and op(1,[args])=DemoTPH then
print(`DemoTPH(n,hole,Moves,A,B,P,H): Given a sequence of moves Moves`):
print(`for Peg-Solitaire on the equilateral triangular-board of`):
print(`side n, with the hole at hole, returns the sequencea`):
print(`of plots that demonstrate the moves and the partial`):
print(`results, where A is denotes the peg to be lifted`):
print(`and B the neigboring peg over which it is to be lifted`):
print(`P denotes a peg, and H denotes a hole`):
fi:
 
if nops([args])=1 and op(1,[args])=Desc then
print(`Desc(POS,Board,Triples,x,T,N): All positions rechable, in`):
print(`N steps, from position POS, in Peg-Solitaire with board Board`):
print(`and set of triples Triples, using the variable x`):
print(`It also tells you how to get there, using the variable T `):
fi:
 
if nops([args])=1 and op(1,[args])=DescS then
print(`DescS(POS,Board,Triples,x,N): All positions rechable, in`):
print(`N steps, from position POS, in Peg-Solitaire with board Board`):
print(`and set of triples Triples, using the variable x`):
fi:
 
if nops([args])=1 and op(1,[args])=DescST then
print(`DescST(loca,n,x,N): All positions rechable, in`):
print(`N steps, from the initial full  board, in Peg-Solitaire with `):
print(`side-n trinagular board , with loca removed, using the variable x .`):
fi:
 
 
if nops([args])=1 and op(1,[args])=DescT then
print(`DescT(loca,n,x,T,N): All positions rechable, in`):
print(`N steps, from the initial full  board, in Peg-Solitaire with `):
print(`side-n trinagular board , with loca removed, using the variable x .`):
print(`It also tells you how to get there, using the variable T `):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=DrawPOS then
print(`DrawPOS(Cr,Ci): Draws the position in Solitaire where`):
print(`the pegs are in the locations of the set Cr`):
print(`and the holes in the locations of the set Ci`):
fi:
 
if nops([args])=1 and op(1,[args])=DrawPOSAB then
print(`DrawPOSAB(Cr,Ci,loc1,loc2,A,B): Draws the position in`):
print(` Solitaire where the pegs are in the locations of the set Cr`):
print(`and the holes in the locations of the set Ci`):
print(`and the peg to be moved is in location loc1 denoted by A`):
print(`and it is to be moved over the peg at location loc2, denoted`):
print(` by B `):
 
fi:
 
if nops([args])=1 and op(1,[args])=DrawPOSABg then
print(`DrawPOSABg(Cr,Ci,Setloc1,Setloc2,A,B): Draws the position `):
print(`in Solitaire where`):
print(`the pegs are in the locations of the set Cr`):
print(`and the holes in the locations of the set Ci`):
print(`and the peg to be moved are in locations Setloc1 denoted by A`):
print(`and it is to be moved over the pegs at location Setloc2, denoted`):
print(` by B `):
fi:
 
if nops([args])=1 and op(1,[args])=DrawPOSABPH then
print(`DrawPOSABPH(Cr,Ci,loc1,loc2,A,B,P,H): Draws the position `):
print(`in Solitaire where`):
print(`the pegs are in the locations of the set Cr denoted by P`):
print(`and the holes in the locations of the set Ci denoted by H`):
print(`and the peg to be moved is in location loc1 denoted by A`):
print(`and it is to be moved over the peg at location loc2, denoted`):
print(` by B `):
fi:
 
if nops([args])=1 and op(1,[args])=IniCross then
print(`IniCross(X,Y,x1,x2,y1,y2,loca): The initial POSITION in`):
print(` Peg-Solitaire whose board is Cross-shaped with a center part `):
print(`that is [0,X-1]x[0,Y-1] and on the right side there is a rectangle`):
print(`[X,X+x2-1]x[0,Y-1], on the left there is the rectangle`):
print(`[-(x1-1),0]x[0,Y-1], on the top there is the rectangle`):
print(`[0,X-1]x[Y,Y+y2-1], and on the bottom there is the retangle`):
print(`[0,X-1]x[-y1,-1], and loca removed`):
fi:
 
if nops([args])=1 and op(1,[args])=IniRect then
print(`IniRect(a,b,loca): The initial POSITION in Peg-Solitaire`):
print(`on an a by b rectangular board, with the peg at location loca`):
print(` removed `):
fi:
 
if nops([args])=1 and op(1,[args])=IniTri then
print(`IniTri(n,loca): The initial POSITION in Peg-Solitaire`):
print(`on a triangular board, with the peg at location loca removed `):
fi:
 
if nops([args])=1 and op(1,[args])=MinPath then
print(`MinPath(POS1,POS2,TRIPLES): One Minimal path, expressed in terms of`):
print(`a sequence of compound moves (a list of lists of triples), `):
print(`that join POS1 and POS2 or empty`):
fi:
 
if nops([args])=1 and op(1,[args])=MinPathC then
print(`MinPathC(X,Y,x1,x2,y1,y2,loca):A Minimal path from the full `):
print(` Cross  board, given by CrossBoard(X,Y,x1,x2,y1,y2) `):
print(`with loca removed to just loca`):
fi:
 
if nops([args])=1 and op(1,[args])=MinPathE then
print(`MinPathE():A Minimal path from the full English `):
print(` board, given by CrossBoard(3,3,2,2,2,2) `):
print(`with the central location removed to just it`):
fi:
 
if nops([args])=1 and op(1,[args])=MinPathT then
print(`MinPathT(n,loca):A Minimal path from the full triangular board`):
print(`with loca removed to just loca`):
fi:
 
if nops([args])=1 and op(1,[args])=NextMoves then
print(`NextMoves(POS,TRIPLES): given a Solitaire position, given`):
print(`as the set of locations occupied by pegs, and the`):
print(`set of all triples of the game, lists all valid moves (triples)`):
print(`and the resulting position`):
fi:
 
if nops([args])=1 and op(1,[args])=NextMovesRank then
print(`NextMovesRank(POS,TRIPLES): given a Solitaire position, given`):
print(`as the set of locations occupied by pegs, and the`):
print(`set of all triples of the game, lists all valid moves (triples)`):
print(`and the resulting position, in order of decreasing number `):
print(`of children`):
fi:
if nops([args])=1 and op(1,[args])=NextMovesSt then
print(`NextMovesSt(POS,TRIPLES,St): given a Solitaire position, given`):
print(`as the set of locations occupied by pegs, and the`):
print(`set of all triples (that start with St)`):
print(` of the game, lists all valid moves (triples)`):
print(`and the resulting position, `):
fi:
 
if nops([args])=1 and op(1,[args])=NuSons then
print(`NuSons(POS,TRIPLES): the number of positions reachable from`):
print(`POS in one move`):
fi:
 
if nops([args])=1 and op(1,[args])=Path then
print(`Path(POS1,POS2,TRIPLES): Returns a path, expressed in terms of`):
print(`a sequence of triples, that join POS1 and POS2`):
print(` or 0, if there is no path `):
fi:
 
if nops([args])=1 and op(1,[args])=Path1 then
print(`Path(POS1,POS2,TRIPLES): Returns a path, expressed in terms of`):
print(`a sequence of triples, that join POS1 and POS2`):
print(` or 0, if there is no path. Does exactly the same as Path `):
print(` but working backwards, usig PreviousMoves `):
fi:
 
if nops([args])=1 and op(1,[args])=Paths then
print(`Paths(POS1,POS2,TRIPLES): all the paths, expressed in terms of`):
print(`a sequence of triples, that join POS1 and POS2`):
fi:
 
if nops([args])=1 and op(1,[args])=PathT then
print(`PathT(n,loca):A path from the full triangular board`):
print(`with loca removed to just loca`):
fi:
 
if nops([args])=1 and op(1,[args])=PlayGreedy then
print(`PlayGreedy(POS,TRIPLES): Starting at positions POS,`):
print(`with TRIPLES the set of triples, plays by`):
print(`taking the move that would yield the most prolific`):
print(` position `):
fi:
 
if nops([args])=1 and op(1,[args])=PlayGreedyT then
print(`PlayGreedyT(n): Plays a greedy Solitaire game`):
print(`on an equilateral-triangular board of side n`):
print(`where the top peg is removed`):
fi:
 
if nops([args])=1 and op(1,[args])=PlayRand then
print(`PlayRand(POS,TRIPLES): Starting at positions POS,`):
print(`with TRIPLES the set of triples, plays by`):
print(`taking random moves amongst what's available`):
print(`until it gets stuck`):
fi:
 
if nops([args])=1 and op(1,[args])=PlayRandT then
print(`PlayRandT(n): Plays a randon Solitaire game`):
print(`on an equilateral-triangular board of side n`):
print(`where the top peg is removed`):
fi:
 
 
if nops([args])=1 and op(1,[args])=PreviousMoves then
print(`PreviousMoves(POS,TRIPLES): given a Solitaire position, given`):
print(`as the set of locations occupied by pegs, and the`):
print(`set of all triples of the game, lists all valid moves (triples)`):
print(`and the resulting position, going backwards`):
fi:
 
if nops([args])=1 and op(1,[args])=RecTriples then
print(`RecTriples(a,b): all the Triples in an a by b rectangular board`):
print(`where the locations are represented as [i,j], 0<=i<a, 0<=j<b`):
fi:
 
if nops([args])=1 and op(1,[args])=TriTriples then
 print(`TriTriples(n): all the TriTriplesples in an equilateral-triangle`):
 print(` board of side n, where the locations are represented as [i,j] `):
fi:
 
end:
 
 
 
#BestRand(POS,TRIPLES,K): by playing randomly K times
#finds the best sequence of moves, if it encounters 1
#peg left, it stops right away
BestRand:=proc(POS,TRIPLES,K)
local aluf,muam:
aluf:=PlayRand(POS,TRIPLES):
 
from 2 to K do
muam:=PlayRand(POS,TRIPLES):
if nops(muam[2])<nops(aluf[2]) then
 aluf:=muam:
if nops(aluf[2])=1 then
 RETURN(aluf):
fi:
fi:
od:
aluf:
end:
 
 
#BestRand1(POS,TRIPLES,K,MAX): by playing randomly K times
#finds the best sequence of moves, if it encounters 1
#peg left, it stops right away, BUT going backwards
BestRand1:=proc(POS,TRIPLES,K,MAX)
local aluf,muam:
aluf:=PlayRand1(POS,TRIPLES):
 
from 2 to K do
muam:=PlayRand1(POS,TRIPLES):
if nops(muam[2])>nops(aluf[2]) then
 aluf:=muam:
if nops(aluf[2])=MAX then
 RETURN(aluf):
fi:
fi:
od:
aluf:
end:
 
 
#BestRandC(X,Y,x1,x2,y1,y2,loca,K): Plays up to K randon Solitaire game
#on a board given by BoardCross(X,Y,x1,x2,y1,y2)
#loca is empty; it picks the best
BestRandC:=proc(X,Y,x1,x2,y1,y2,loca,K)
BestRand(IniCross(X,Y,x1,x2,y1,y2,loca) ,
CrossTriples(X,Y,x1,x2,y1,y2),K):
end:
 
 
#BestRandE(K): Plays up to K randon Peg-Solitaire game
#on a standard English board with the middle peg
#removed 
BestRandE:=proc(K):
BestRandC(3,3,2,2,2,2,[1,1],K):
end:
 
 
#BestRandR(a,b,loca,K): Plays up to K randon Solitaire game
#on an a by b rectangular board where the location
#loca is empty; it picks the best
BestRandR:=proc(a,b,loca,K):
BestRand(IniRect(a,b,loca) ,RecTriples(a,b),K):
end:
 
#BestRandT(n,K): Plays K randon Solitaire game
#on an equilateral-triangular board of side n
#where the top peg is removed and picks the best
BestRandT:=proc(n,K):
BestRand(IniTri(n,[n-1,n-1]),TriTriples(n),K):
end:
 
#BestRandT1(n,K): Plays K randon Solitaire game
#on an equilateral-triangular board of side n
#where the top peg is removed and picks the best
BestRandT1:=proc(n,K):
BestRand1({[n-1,n-1]},TriTriples(n),K,binomial(n+1,2)-1):
end:
 
 
#BoardCross(X,Y,x1,x2,y1,y2): The 
# board of a Cross-shaped with a center part 
#that is [0,X-1]x[0,Y-1] and on the right side there is a rectangle
#[X,X+x2-1]x[0,Y-1], on the left there is the rectangle
#[-(x1-1),0]x[0,Y-1], on the top there is the rectangle
#[0,X-1]x[Y,Y+y2-1], and on the bottom there is the retangle
#[0,X-1]x[-y1,-1], and loca removed
BoardCross:=proc(X,Y,x1,x2,y1,y2)
local gu,i,j:
gu:={}:
 
for i from 0 to X-1 do
for j from -y1 to Y+y2-1 do
gu:=gu union {[i,j]}:
od:
od:
 
 
for i from -x1 to X+x2-1 do
for j from 0 to Y-1 do
gu:=gu union {[i,j]}:
od:
od:
gu:
 
end:
 
#BoardRect(a,b): The locations in an a by b rectangular board
BoardRect:=proc(a,b)
local gu,i,j:
gu:={}:
 
for i from 0 to a-1 do
for j from 0 to b-1 do
 gu:=gu union {[i,j]}:
od:
od:
gu:
end:
 
#BoardTri(n): The locations in an equilateral
#triangle board of side n 
BoardTri:=proc(n)
local gu,i,j:
gu:={}:
 
for j from 0 to n-1 do
for i from j by 2 to 2*n-2-j  do
 gu:=gu union {[i,j]}:
od:
od:
gu:
end:
 
#BTpath(POS,TRIPLES): finds a path with optimal end
#starting at position POS, in a Peg-Solitaire game 
#defined by the set of triples TRIPLES
BTpath:=proc(POS,TRIPLES)
local PP,PPt,RO,lu,aluf,aluf1,mu,lu1,POS1:
 
PP:=[POS]: PPt:=[]:
aluf:=PP:
aluf1:=PPt:
lu:=convert(NextMoves(POS,TRIPLES),list):
RO:=[lu]:
 
while PP<>[] do
lu:=RO[nops(RO)]:
 if lu<>[] then
  lu1:=[op(2..nops(lu),lu)]:
  RO:=[op(1..nops(RO)-1,RO),lu1]:
  POS1:=lu[1]:
  PP:=[op(PP),POS1[2]]:PPt:=[op(PPt),POS1[1]]:
  RO:=[op(RO),convert(NextMoves(POS1[2],TRIPLES),list)]:
  if nops(PP[nops(PP)])=1 then
   RETURN(PP,PPt):
  fi:
 else
   if nops(PP[nops(PP)])<nops(aluf[nops(aluf)]) then
    aluf:=PP: aluf1:=PPt:
  print(`So far the best path is`, aluf1):
 print(`It leads to `, nops(aluf[nops(aluf)]), ` pegs `):
 
   fi:
 
 
   PP:=[op(1..nops(PP)-1,PP)]:
   PPt:=[op(1..nops(PPt)-1,PPt)]:
   if PP=[] then
    RETURN(aluf,aluf1):
   fi:
   mu:=RO[nops(RO)-1]:
 
 
  if mu<>[] then
   RO:=[op(1..nops(RO)-2,RO),[op(2..nops(mu),mu)]]:
  else
   RO:=[op(1..nops(RO)-2,RO),mu]:
  fi:
 fi:
od:
aluf,aluf1:
end:
 
 
#BTpath1(POS,TRIPLES): finds a path with optimal end
#starting at position POS, in a Peg-Solitaire game 
#defined by the set of triples TRIPLES, by preferentail
#backtrack
BTpath1:=proc(POS,TRIPLES)
local PP,PPt,RO,lu,aluf,aluf1,mu,lu1,POS1:
 
PP:=[POS]: PPt:=[]:
aluf:=PP:
aluf1:=PPt:
lu:=NextMovesRank(POS,TRIPLES):
RO:=[lu]:
 
while PP<>[] do
lu:=RO[nops(RO)]:
 if lu<>[] then
  lu1:=[op(2..nops(lu),lu)]:
  RO:=[op(1..nops(RO)-1,RO),lu1]:
  POS1:=lu[1]:
  PP:=[op(PP),POS1[2]]:PPt:=[op(PPt),POS1[1]]:
  RO:=[op(RO),NextMovesRank(POS1[2],TRIPLES)]:
  if nops(PP[nops(PP)])=1 then
   RETURN(PP,PPt):
  fi:
 else
   if nops(PP[nops(PP)])<nops(aluf[nops(aluf)]) then
    aluf:=PP: aluf1:=PPt:
  print(`So far the best path is`, aluf1):
 print(`It leads to `, nops(aluf[nops(aluf)]), ` pegs `):
 
   fi:
 
 
   PP:=[op(1..nops(PP)-1,PP)]:
   PPt:=[op(1..nops(PPt)-1,PPt)]:
   if PP=[] then
    RETURN(aluf,aluf1):
   fi:
   mu:=RO[nops(RO)-1]:
 
 
  if mu<>[] then
   RO:=[op(1..nops(RO)-2,RO),[op(2..nops(mu),mu)]]:
  else
   RO:=[op(1..nops(RO)-2,RO),mu]:
  fi:
 fi:
od:
aluf,aluf1:
end:
 
#BTpathE(): Using BackTrack to solve the Peg-Solitaire puzzle
#on a standard English board  
BTpathE:=proc(): BTpath(
IniCross(3,3,2,2,2,2,[1,1]),CrossTriples(3,3,2,2,2,2)):end:
 
#BTpathE1(): Using BackTrack to solve the Peg-Solitaire puzzle
#on a standard English board  
BTpathE1:=proc(): BTpath1(
IniCross(3,3,2,2,2,2,[1,1]),CrossTriples(3,3,2,2,2,2)):end:
 
#BTpathR(a,b,loca): Using BackTrack to solve the Peg-Solitaire puzzle
#for an a by b rect. board with the inital location loca empty
BTpathR:=proc(a,b,loca): BTpath(IniRect(a,b,loca),RecTriples(a,b)):end:
 
#BTpathR1(a,b,loca): Using BackTrack to solve the Peg-Solitaire puzzle
#for an a by b rect. board with the inital location loca empty
BTpathR1:=proc(a,b,loca): BTpath1(IniRect(a,b,loca),RecTriples(a,b)):end:
 
#BTpathT(n): Using BackTrack to solve the Peg-Solitaire puzzle
BTpathT:=proc(n): BTpath(IniTri(n,[n-1,n-1]),TriTriples(n)):end:
 
#BTpathT1(n): Using BackTrack to solve the Peg-Solitaire puzzle
BTpathT1:=proc(n): BTpath1(IniTri(n,[n-1,n-1]),TriTriples(n)):end:
 
#ChopFvar(F,var): Given a polynomial F in the variables in
#the set var, only retains the terms where the powers of
#the elements of var have degree 0 or 1
ChopFvar:=proc(F,var)
local i,x,gu:
gu:=expand(F):
for i from 1 to nops(var) do
x:=var[i]:
gu:=expand(coeff(gu,x,0)+coeff(gu,x,1)*x):
od:
gu:
end:
 
#CompoundMoves(POS,TRIPLES): All the compund moves that
#from position POS, with the triples TRIPLES
CompoundMoves:=proc(POS,TRIPLES)
local St,i,gu:
gu:={}:
 
for i from 1 to nops(POS) do
 St:=op(i,POS):
 gu:=gu union CompoundMovesSt(POS,TRIPLES,St):
od:
 
gu:
end:
 
#CompoundMovesSt(POS,TRIPLES,St): All the compund moves that
#start at St from position POS, with the triples TRIPLES
CompoundMovesSt:=proc(POS,TRIPLES,St)
local mu,gu,i,mu1,lu,j:
mu:=NextMovesSt(POS,TRIPLES,St):
gu:={}:
for i from 1 to nops(mu) do
mu1:=mu[i]:
gu:=gu union {[[mu1[1]],mu1[2]]}:
lu:=CompoundMovesSt(mu1[2],TRIPLES,mu1[1][3]):
 for j from 1 to nops(lu) do
   gu:=gu union {[[mu1[1],op(lu[j][1]) ], lu[j][2] ] }:
 od:
od:
gu:
end:
 
 
#CrossTriples(X,Y,x1,x2,y1,y2): all the Triples in 
#a cross board given by BoardCross(X,Y,x1,x2,y1,y2)
CrossTriples:=proc(X,Y,x1,x2,y1,y2)
local gu,t,i,mu,x,y:
mu:=BoardCross(X,Y,x1,x2,y1,y2):
gu:={}:
for i from 1 to nops(mu) do
x:=mu[i][1]:y:=mu[i][2]:
 
t:=[[x,y],[x+1,y],[x+2,y]]:
 
if {op(t)} minus mu={} then
gu:=gu union {t, [[x+2,y],[x+1,y],[x,y]]}:
fi:
 
t:=[[x,y],[x,y+1],[x,y+2]]:
 
if {op(t)} minus mu={} then
gu:=gu union {t, [[x,y+2],[x,y+1],[x,y]]}:
fi:
od:
gu:
end:
 
 
#Demo(INI,hole,Moves,A,B): Given the initial postion of the
#locations of pegs (a set of points), the hole, and
#a sequence of Moves, and two strings A and B
#shows the sequence of partial positions, and which peg
#(denoted by A) to go over the peg marked with B
Demo:=proc(INI,hole,Moves,A,B)
local i,PEGS,HOLES,tri,PICS:
 
PEGS:=INI:
HOLES:={hole}:
tri:=Moves[1]:
PICS:=[DrawPOSAB(PEGS,HOLES,tri[1],tri[2],A,B)]:
 
for i from 2 to nops(Moves) do
PEGS:=PEGS minus {tri[1],tri[2]} union {tri[3]}:
HOLES:=HOLES union {tri[1],tri[2]} minus {tri[3]}:
tri:=Moves[i]:
PICS:=[op(PICS),DrawPOSAB(PEGS,HOLES,tri[1],tri[2],A,B)]:
od:
PEGS:=PEGS minus {tri[1],tri[2]} union {tri[3]}:
HOLES:=HOLES union {tri[1],tri[2]} minus {tri[3]}:
[op(PICS),DrawPOS(PEGS,HOLES)]:
end:
 
 
 
#DemoE(Moves,A,B): Given a sequence of moves Moves
#for Peg-Solitaire on the standard English board
# with the hole at the middle, returns the sequence
#of plots that demonstrate the moves and the partial
#results, where A is denotes the peg to be lifted
#and B the neigboring peg over which it is to be lifted
DemoE:=proc(Moves,A,B)
local INI:
INI:=IniCross(3,3,2,2,2,2,[1,1]):
Demo(INI,[1,1],Moves,A,B):
end:
 
#Demog(INI,hole,Moves,A,B): 
#Like Demo(INI,hole,Moves,A,B), but the Moves is a sequence
#of compound moves
 
Demog:=proc(INI,hole,Moves,A,B)
local i,PEGS,HOLES,tri,PICS,guA,guB,i1:
 
PEGS:=INI:
HOLES:={hole}:
tri:=Moves[1]:
guA:={tri[1][1]}:
guB:={seq(tri[i][2],i=1..nops(tri))}:
PICS:=[DrawPOSABg(PEGS,HOLES,guA,guB,A,B)]:
 
for i from 2 to nops(Moves) do
PEGS:=PEGS minus (guA union guB) union {tri[nops(tri)][3]}:
 
HOLES:=HOLES union guA union guB minus {tri[nops(tri)][3]}:
 
tri:=Moves[i]:
guA:={tri[1][1]}:
guB:={seq(tri[i1][2],i1=1..nops(tri))}:
PICS:=[op(PICS),DrawPOSABg(PEGS,HOLES,guA,guB,A,B)]:
od:
PEGS:=PEGS minus (guA union guB) union {tri[nops(tri)][3]}:
HOLES:=HOLES union guA union guB minus {tri[nops(tri)][3]}:
[op(PICS),DrawPOS(PEGS,HOLES)]:
end:
 
 
#DemoPH(INI,hole,Moves,A,B,P,H): Given the initial postion of the
#locations of pegs (a set of points), the hole, and
#a sequence of Moves, and two strings A and B
#shows the sequence of partial positions, and which peg
#(denoted by A) to go over the peg marked with B
DemoPH:=proc(INI,hole,Moves,A,B,P,H)
local i,PEGS,HOLES,tri,PICS:
 
PEGS:=INI:
HOLES:={hole}:
tri:=Moves[1]:
PICS:=[DrawPOSABPH(PEGS,HOLES,tri[1],tri[2],A,B,P,H)]:
 
for i from 2 to nops(Moves) do
PEGS:=PEGS minus {tri[1],tri[2]} union {tri[3]}:
HOLES:=HOLES union {tri[1],tri[2]} minus {tri[3]}:
tri:=Moves[i]:
PICS:=[op(PICS),DrawPOSABPH(PEGS,HOLES,tri[1],tri[2],A,B,P,H)]:
od:
PEGS:=PEGS minus {tri[1],tri[2]} union {tri[3]}:
HOLES:=HOLES union {tri[1],tri[2]} minus {tri[3]}:
[op(PICS),DrawPOSPH(PEGS,HOLES,P,H)]:
end:
 
#DemoT(n,hole,Moves,A,B): Given a sequence of moves Moves
#for Peg-Solitaire on the equilateral triangular-board of
#side n, with the hole at hole, returns the sequence
#of plots that demonstrate the moves and the partial
#results, where A is denotes the peg to be lifted
#and B the neigboring peg over which it is to be lifted
DemoT:=proc(n,hole,Moves,A,B)
local INI:
INI:=IniTri(n,hole):
Demo(INI,hole,Moves,A,B):
end:
 
 
 
#DemoTg(n,hole,Moves,A,B): 
#Like DemoT(n,hole,Moves,A,B): but Moves is a sequence
#of compound moves
DemoTg:=proc(n,hole,Moves,A,B)
local INI:
INI:=IniTri(n,hole):
Demog(INI,hole,Moves,A,B):
end:
 
#Desc(POS,Board,Triples,x,T,N): All positions rechable, 
#plus how to get to them, using the variale T
#N steps, from position POS, in Peg-Solitaire with board Board
#and set of triples Triples, using the variable x
#and the variable T to actually
Desc:=proc(POS,Board,Triples,x,T,N)
local P,i,t,var,gu,i1:
 
var:={}:
 
for i from 1 to nops(Board) do
 var:=var union {x[Board[i]]}:
od:
 
gu:=1:
 
for i from 1 to nops(POS) do
 gu:=gu*x[POS[i]]:
od:
 
for i from 1 to N do
P:=0:
 
for i1 from 1 to nops(Triples) do
t:=Triples[i1]:
P:=P+x[t[3]]/x[t[1]]/x[t[2]]*T[i,t]:
od:
 
gu:=expand(gu*P):
gu:=ChopFvar(gu,var):
od:
gu:
end:
 
#DescS(POS,Board,Triples,x,N): All positions rechable, in
#N steps, from position POS, in Peg-Solitaire with board Board
#and set of triples Triples, using the variable x
DescS:=proc(POS,Board,Triples,x,N)
local P,i,t,var,gu:
P:=0:
 
for i from 1 to nops(Triples) do
t:=Triples[i]:
P:=P+x[t[3]]/x[t[1]]/x[t[2]]:
od:
 
var:={}:
 
for i from 1 to nops(Board) do
 var:=var union {x[Board[i]]}:
od:
 
gu:=1:
 
for i from 1 to nops(POS) do
 gu:=gu*x[POS[i]]:
od:
 
for i from 1 to N do
gu:=expand(gu*P):
gu:=ChopFvar(gu,var):
od:
gu:
end:
 
 
#DescST(loca,n,x,N): All positions rechable, in
#N steps, from initial position with loca removed
#, in Peg-Solitaire with 
#side-n trinagular board , using the variable x .
DescST:=proc(loca,n,x,N) local POS:
POS:=BoardTri(n) minus {loca}:
DescS(POS,BoardTri(n),TriTriples(n),x,N):
end:
 
#DescT(loca,n,x,T,N): All positions rechable, in
#N steps, from initial position with loca removed
#, in Peg-Solitaire with 
#side-n trinagular board , using the variable x .
#plus how to get to them
DescT:=proc(loca,n,x,T,N) local POS:
POS:=BoardTri(n) minus {loca}:
Desc(POS,BoardTri(n),TriTriples(n),x,T,N):
end:
 
 
#DemoTPH(n,hole,Moves,A,B,P,H): Given a sequence of moves Moves
#for Peg-Solitaire on the equilateral triangular-board of
#side n, with the hole at hole, returns the sequence
#of plots that demonstrate the moves and the partial
#results, where A is denotes the peg to be lifted
#and B the neigboring peg over which it is to be lifted
#P denotes a peg, and H denotes a hole
DemoTPH:=proc(n,hole,Moves,A,B,P,H)
local INI:
INI:=IniTri(n,hole):
DemoPH(INI,hole,Moves,A,B,P,H):
end:
 
#DrawPOS(Cr,Ci): Draws the position in Solitaire where
#the pegs are in the locations of the set Cr
#and the holes in the locations of the set Ci
DrawPOS:=proc(Cr,Ci)
local d1,d2:
with(plots):
d1:=plot(convert(Cr,list),style=point,axes=none,symbol=CROSS):
d2:=plot(convert(Ci,list),style=point,axes=none,symbol=CIRCLE):
[d1,d2]:
end:
 
#DrawPOSAB(Cr,Ci,loc1,loc2,A,B): Draws the position in Solitaire where
#the pegs are in the locations of the set Cr
#and the holes in the locations of the set Ci
#and the peg to be moved is in location loc1 denoted by A
#and it is to be moved over the peg at location loc2, denoted
#by B
DrawPOSAB:=proc(Cr,Ci,loc1,loc2,A,B)
local d1,d2,d3,d4:
if not (type(A,string) and type(B,string)) then
ERROR(`the fifth and sixth arguments must be strings`):
fi:
if not (member(loc1, Cr) and member(loc2,Cr)) then
ERROR(loc1, loc2, `should both be occupied by pegs`):
fi:
 
with(plots):
d1:=plot(convert(Cr ,list),style=point,axes=none,symbol=CROSS):
d2:=plot(convert(Ci,list),style=point,axes=none,symbol=CIRCLE):
d3:=textplot([loc1[1]+.2,loc1[2]+.2,A]):
d4:=textplot([loc2[1]+.2,loc2[2]+.2,B]):
#display(d1,d2,d3,d4):
[d1,d2,d3,d4]:
end:
 
 
#DrawPOSABg(Cr,Ci,Setloc1,Setloc2,A,B): Draws the position 
#in Solitaire where
#the pegs are in the locations of the set Cr
#and the holes in the locations of the set Ci
#and the peg to be moved are in locations Setloc1 denoted by A
#and it is to be moved over the pegs at location Setloc2, denoted
#by B
DrawPOSABg:=proc(Cr,Ci,Setloc1,Setloc2,A,B)
local d1,d2,d3,d4,i:
if not (type(A,string) and type(B,string)) then
ERROR(`the fifth and sixth arguments must be strings`):
fi:
 
with(plots):
d1:=plot(convert(Cr ,list),style=point,axes=none,symbol=CROSS):
d2:=plot(convert(Ci,list),style=point,axes=none,symbol=CIRCLE):
 
d3:=[]:
for i from 1 to nops(Setloc1) do
d3:=[op(d3),textplot([Setloc1[i][1]+.2,Setloc1[i][2]+.2,A])]:
od:
d4:=[]:
for i from 1 to nops(Setloc2) do
d4:=[op(d4),textplot([Setloc2[i][1]+.2,Setloc2[i][2]+.2,B])]:
od:
#display(d1,d2,d3,d4):
[d1,d2,op(d3),op(d4)]:
end:
 
 
#DrawPOSABPH(Cr,Ci,loc1,loc2,A,B,P,H): Draws the position in Solitaire where
#the pegs are in the locations of the set Cr denoted by P
#and the holes in the locations of the set Ci denoted by H
#and the peg to be moved is in location loc1 denoted by A
#and it is to be moved over the peg at location loc2, denoted
#by B
DrawPOSABPH:=proc(Cr,Ci,loc1,loc2,A,B,P,H)
local d,PEGS,i:
if not (type(A,string) and type(B,string)) then
ERROR(`the fifth and sixth arguments must be strings`):
fi:
if not (member(loc1, Cr) and member(loc2,Cr)) then
ERROR(loc1, loc2, `should both be occupied by pegs`):
fi:
 
with(plots):
 
d:=textplot([loc1[1],loc1[2],A],axes=none),
textplot([loc2[1],loc2[2],B],axes=none):
PEGS:=Cr minus {loc1,loc2}:
for i from 1 to nops(PEGS) do
 d:=d,textplot([PEGS[i][1],PEGS[i][2],P],axes=none):
od:
for i from 1 to nops(Ci) do
 d:=d,textplot([Ci[i][1],Ci[i][2],H],axes=none):
od:
 
[d]:
end:
 
 
#DrawPOSPH(Cr,Ci,P,H): Draws the position in Solitaire where
#the pegs are in the locations of the set Cr denoted by P
#and the holes in the locations of the set Ci denoted by H
DrawPOSPH:=proc(Cr,Ci,P,H)
local d,i:
 
with(plots):
d:=[]:
for i from 1 to nops(Cr) do
 d:=[op(d),textplot([Cr[i][1],Cr[i][2],P],axes=none)]:
od:
for i from 1 to nops(Ci) do
 d:=[op(d),textplot([Ci[i][1],Ci[i][2],H],axes=none)]:
od:
 
d:
end:
 
 
#IniCross(X,Y,x1,x2,y1,y2,loca): The initial POSITION in Peg-Solitaire
#whose board is Cross-shaped with a center part 
#that is [0,X-1]x[0,Y-1] and on the right side there is a rectangle
#[X,X+x2-1]x[0,Y-1], on the left there is the rectangle
#[-(x1-1),0]x[0,Y-1], on the top there is the rectangle
#[0,X-1]x[Y,Y+y2-1], and on the bottom there is the retangle
#[0,X-1]x[-y1,-1], and loca removed
IniCross:=proc(X,Y,x1,x2,y1,y2,loca)
if not member(loca,BoardCross(X,Y,x1,x2,y1,y2)) then 
ERROR(loca , `should be on the board `):
fi:
BoardCross(X,Y,x1,x2,y1,y2) minus {loca}:
end:
 
#IniRect(a,b,loca): The initial POSITION in Peg-Solitaire
#on an a by b rectangular board, with the peg at location loca
#removed
IniRect:=proc(a,b,loca): 
if not member(loca,BoardRect(a,b)) then 
ERROR(loca , `should be on the board `):
fi:
BoardRect(a,b) minus {loca}:
end:
 
#IniTri(n,loca): The initial POSITION in Peg-Solitaire
#on a triangular board, with the peg at location loca
#removed
IniTri:=proc(n,loca):
BoardTri(n) minus {loca}:
end:
 
 
#MinPath(POS1,POS2,TRIPLES): One Minimal path, expressed in terms of
#a sequence of compound moves (a list of lists of triples), 
#that join POS1 and POS2 or empty
MinPath:=proc(POS1,POS2,TRIPLES) 
local Neighs,i,muam,si,sakhen,aluf,Neighs1:
option remember:
if nops(POS2)>nops(POS1) then
 RETURN(0):
fi:
 
if nops(POS2)=nops(POS1) then
 if POS2=POS1 then
  RETURN([]):
 else
 RETURN(0):
 fi:
fi:
 
Neighs1:=CompoundMoves(POS1,TRIPLES):
 
if nops(Neighs1)=0 then
RETURN(0):
fi:
 
Neighs:={}:
 
for i from 1 to nops(Neighs1) do
if MinPath(Neighs1[i][2],POS2,TRIPLES)<>0 then
 Neighs:=Neighs union {Neighs1[i]}:
fi:
od:
 
if nops(Neighs)=0 then
 RETURN(0):
fi:
 
sakhen:=Neighs[1]:
muam:=MinPath(sakhen[2],POS2,TRIPLES):
si:=nops(muam):
aluf:=[sakhen[1],op(muam)]:
 
for i from 2 to nops(Neighs) do
sakhen:=Neighs[i]:
muam:=MinPath(sakhen[2],POS2,TRIPLES):
if nops(muam)<si then
si:=nops(muam):
aluf:=[sakhen[1],op(muam)]:
fi:
od:
aluf:
end:
 
 
#MinPathC(X,Y,x1,x2,y1,y2,loca):A Minimal path from the full Cross 
#board with loca removed to just loca
MinPathC:=proc(X,Y,x1,x2,y1,y2,loca) 
local POS1,POS2,TRIPLES:
POS1:=IniCross(X,Y,x1,x2,y1,y2,loca):
POS2:={loca}:
TRIPLES:=CrossTriples(X,Y,x1,x2,y1,y2,loca):
MinPath(POS1,POS2,TRIPLES):
end:
 
#MinPathE(X,Y,x1,x2,y1,y2,loca):A Minimal path from the full 
#English board with loca removed to just loca
MinPathE:=proc() :
MinPathC(3,3,2,2,2,2,[1,1]) 
end:
 
#MinPathT(n,loca):A Minimal path from the full triangular board
#with loca removed to just loca
MinPathT:=proc(n,loca) 
local POS1,POS2,TRIPLES:
POS1:=IniTri(n,loca):
POS2:={loca}:
TRIPLES:=TriTriples(n):
MinPath(POS1,POS2,TRIPLES):
end: 
 
#NextMoves(POS,TRIPLES): given a Solitaire position, given
#as the set of locations occupied by pegs, and the
#set of all triples of the game, lists all valid moves (triples)
#and the resulting position
#
NextMoves:=proc(POS,TRIPLES)
local gu,i,t:
gu:={}:
 
for i from 1 to nops(TRIPLES) do
t:=op(i,TRIPLES):
if member(t[1],POS) and member(t[2],POS) and not member(t[3],POS) then
 gu:={op(gu),[t,POS minus {t[1],t[2]} union {t[3]}]}:
fi:
od:
gu:
end:
 
#NextMovesRank(POS,TRIPLES): given a Solitaire position, given
#as the set of locations occupied by pegs, and the
#set of all triples of the game, lists all valid moves (triples)
#and the resulting position, in order of decreasing number 
#of children
#
NextMovesRank:=proc(POS,TRIPLES) local gu,B,mu,ka,ga,i,lu:
gu:=NextMoves(POS,TRIPLES):
if gu={} then
 RETURN([]):
fi:
mu:={}:
for i from 1 to nops(gu) do
mu:=mu union {NuSons(gu[i][2],TRIPLES)}:
od:
 
 
ka:=min(op(mu)):ga:=max(op(mu)):
 
for i from ka to ga do
B[i]:={}:
od:
 
for i from 1 to nops(gu) do
 B[NuSons(gu[i][2],TRIPLES)]:=B[NuSons(gu[i][2],TRIPLES)] union {gu[i]}:
od:
 
 
lu:=[]:
for i from ga by -1 to ka do
lu:=[op(lu),op(B[i])]:
od:
lu:
end:
 
#NextMovesSt(POS,TRIPLES,St): given a Solitaire position POS, given
#as the set of locations occupied by pegs, and the
#set of all triples of the game, 
#and the position St lists all valid moves (triples)
#and the resulting position that start at St
#
NextMovesSt:=proc(POS,TRIPLES,St)
local gu,i,t:
if not member(St,POS) then
 ERROR(`The last input should be a member of the first input`):
fi:
gu:={}:
 
for i from 1 to nops(TRIPLES) do
t:=op(i,TRIPLES):
if t[1]=St then
if member(t[1],POS) and member(t[2],POS) and not member(t[3],POS) then
 gu:={op(gu),[t,POS minus {t[1],t[2]} union {t[3]}]}:
fi:
fi:
od:
gu:
end:
 
#NuSons(POS,TRIPLES): the number of positions reachable from
#POS in one move
NuSons:=proc(POS,TRIPLES):
nops(NextMoves(POS,TRIPLES)):
end:
 
#Path(POS1,POS2,TRIPLES): One paths, expressed in terms of
#a sequence of triples, that join POS1 and POS2 or empty
Path:=proc(POS1,POS2,TRIPLES) 
local i,gu1,mu,tri:
option remember:
if nops(POS2)>nops(POS1) then
 RETURN(0):
fi:
 
if nops(POS2)=nops(POS1) then
 if POS2=POS1 then
  RETURN([]):
 else
 RETURN(0):
 fi:
fi:
 
mu:=NextMoves(POS1,TRIPLES):
for i from 1 to nops(mu) do
tri:=mu[i][1]:
 gu1:=Path(mu[i][2],POS2,TRIPLES):
  if gu1<>0 then
   RETURN([tri,op(gu1)]):
 fi:
od:
0:
end:
 
#Path1(POS1,POS2,TRIPLES): One paths, expressed in terms of
#a sequence of triples, that join POS1 and POS2 or empty
#but using PreviousMoves
Path1:=proc(POS1,POS2,TRIPLES) 
local i,gu1,mu,tri:
option remember:
if nops(POS2)>nops(POS1) then
 RETURN(0):
fi:
 
if nops(POS2)=nops(POS1) then
 if POS2=POS1 then
  RETURN([]):
 else
 RETURN(0):
 fi:
fi:
 
mu:=PreviousMoves(POS2,TRIPLES):
for i from 1 to nops(mu) do
tri:=mu[i][1]:
 gu1:=Path1(POS1,mu[i][2],TRIPLES):
  if gu1<>0 then
   RETURN([op(gu1),tri]):
 fi:
od:
0:
end:
 
#Paths(POS1,POS2,TRIPLES): all the paths, expressed in terms of
#a sequence of triples, that join POS1 and POS2
Paths:=proc(POS1,POS2,TRIPLES) 
local i,gu,mu,j,gu1,tri:
option remember:
if nops(POS2)>nops(POS1) then
 RETURN({}):
fi:
 
if nops(POS2)=nops(POS1) then
 if POS2=POS1 then
  RETURN({[]}):
 else
 RETURN({}):
 fi:
fi:
 
gu:={}:
mu:=NextMoves(POS1,TRIPLES):
for i from 1 to nops(mu) do
tri:=mu[i][1]:
 gu1:=Paths(mu[i][2],POS2,TRIPLES):
  
  for j from 1 to nops(gu1) do
   gu:=gu union {[tri,op(op(j,gu1))]}:
  od:
 
od:
gu:
end:
 
 
#PathT(n,loca):A path from the full triangular board
#with loca removed to just loca
PathT:=proc(n,loca) 
local POS1,POS2,TRIPLES:
POS1:=IniTri(n,loca):
POS2:={loca}:
TRIPLES:=TriTriples(n):
Path(POS1,POS2,TRIPLES):
end: 
 
#Path1T(n,loca):A path from the full triangular board
#with loca removed to just loca
Path1T:=proc(n,loca) 
local POS1,POS2,TRIPLES:
POS1:=IniTri(n,loca):
POS2:={loca}:
TRIPLES:=TriTriples(n):
Path1(POS1,POS2,TRIPLES):
end: 
 
#PlayGreedy(POS,TRIPLES): Starting at positions POS,
#with TRIPLES the set of triples, plays by
#taking the move that would yield the most prolific
#position
PlayGreedy:=proc(POS,TRIPLES)
local POS1,gu,mu,i,tri,aluf,rec:
gu:=[]:
 
mu:=NextMoves(POS,TRIPLES):
 
while mu<>{} do
 aluf:=mu[1]:
 rec:=nops(NextMoves(mu[1][2],TRIPLES)):
  for i from 2 to nops(mu) do
   if nops(NextMoves(mu[i][2],TRIPLES))>rec then
     rec:=nops(NextMoves(mu[i][2],TRIPLES)):
     aluf:=mu[i]:
   fi:
  od:
 
 POS1:=aluf[2]:
 tri:=aluf[1]:
 gu:=[op(gu),tri]:
 mu:=NextMoves(POS1,TRIPLES):
od:
gu,POS1:
end:
 
#PlayGreedyT(n): Plays a greedy Solitaire game
#on an equilateral-triangular board of side n
#where the top peg is removed
PlayGreedyT:=proc(n):
PlayGreedy(IniTri(n,[n-1,n-1]),TriTriples(n)):
end:
 
#PlayRand(POS,TRIPLES): Starting at positions POS,
#with TRIPLES the set of triples, plays by
#taking random moves amongst what's available
#until it gets stuck
PlayRand:=proc(POS,TRIPLES)
local POS1,gu,mu,ra,tri:
gu:=[]:
 
mu:=NextMoves(POS,TRIPLES):
 
while mu<>{} do
 ra:=rand(1..nops(mu))():
 tri:=mu[ra]:
 POS1:=tri[2]:
 tri:=tri[1]:
 gu:=[op(gu),tri]:
 mu:=NextMoves(POS1,TRIPLES):
od:
gu,POS1:
end:
 
 
#PlayRand1(POS,TRIPLES): Starting at positions POS,
#with TRIPLES the set of triples, plays, backwards by
#taking random moves amongst what's available
#until it gets stuck
PlayRand1:=proc(POS,TRIPLES)
local POS1,gu,mu,ra,tri:
gu:=[]:
 
mu:=PreviousMoves(POS,TRIPLES):
 
while mu<>{} do
 ra:=rand(1..nops(mu))():
 tri:=mu[ra]:
 POS1:=tri[2]:
 tri:=tri[1]:
 gu:=[tri,op(gu)]:
 mu:=PreviousMoves(POS1,TRIPLES):
od:
gu,POS1:
end:
 
#PlayRandT(n): Plays a randon Solitaire game
#on an equilateral-triangular board of side n
#where the top peg is removed
PlayRandT:=proc(n):
PlayRand(IniTri(n,[n-1,n-1]),TriTriples(n)):
end:
 
 
#PlayRandT1(n): Plays a randon Solitaire game
#on an equilateral-triangular board of side n
#where the top peg is removed
PlayRandT1:=proc(n):
PlayRand1({[n-1,n-1]},TriTriples(n)):
end:
 
 
#PreviousMoves(POS,TRIPLES): given a Solitaire position, given
#as the set of locations occupied by pegs, and the
#set of all triples of the game, lists all valid moves (triples)
#and the resulting position, going backwards
#
PreviousMoves:=proc(POS,TRIPLES)
local gu,i,t:
gu:={}:
 
for i from 1 to nops(TRIPLES) do
t:=op(i,TRIPLES):
if not member(t[1],POS) and not member(t[2],POS) and member(t[3],POS) then
 gu:={op(gu),[t,POS union{t[1],t[2]} minus {t[3]}]}:
fi:
od:
gu:
end:
 
 
#RecTriples(a,b): all the Triples in an a by b rectangular board
#where the locations are represented as [i,j], 0<=i<a, 0<=j<b
RecTriples:=proc(a,b)
local gu,i,j,t:
gu:={}:
 
for i from 0 to a-1 do
for j from 0 to b-3 do
t:=[[i,j],[i,j+1],[i,j+2]]:
gu:=gu union {t}:
t:=[[i,j+2],[i,j+1],[i,j]]:
gu:=gu union {t}:
od:
od:
 
for i from 0 to a-3 do
for j from 0 to b-1 do
t:=[[i,j],[i+1,j],[i+2,j]]:
gu:=gu union {t}:
t:=[[i+2,j],[i+1,j],[i,j]]:
gu:=gu union {t}:
od:
od:
gu:
end:
 
#TriTriples(n): all the TriTriplesples in an equilateral-triangle board
#of side n, where the locations are represented as [i,j]
TriTriples:=proc(n)
local gu,i,j,t:
gu:={}:
 
for j from 0 to n-1 do
for i from j by 2 to 2*n-6-j do
t:=[[i,j],[i+2,j],[i+4,j]]:
gu:=gu union {t}:
t:=[[i+4,j],[i+2,j],[i,j]]:
gu:=gu union {t}:
od:
od:
 
for j from 0 to n-3 do
for i from j by 2 to 2*n-6-j do
t:=[[i,j],[i+1,j+1],[i+2,j+2]]:
gu:=gu union {t}:
t:=[[i+2,j+2],[i+1,j+1],[i,j]]:
gu:=gu union {t}:
od:
od:
 
for j from 0 to n-3 do
for i from j+4 by 2 to 2*n-2-j do
t:=[[i,j],[i-1,j+1],[i-2,j+2]]:
gu:=gu union {t}:
t:=[[i-2,j+2],[i-1,j+1],[i,j]]:
gu:=gu union {t}:
od:
od:
 
gu:
end:
 
####Pre-Computed Data
Best5:=
[[[[2, 2], [3, 3], [4, 4]]], [[[4, 0], [3, 1], [2, 2]]],
 
 [[[0, 0], [2, 0], [4, 0]]], [[[6, 0], [4, 0], [2, 0]]],
 
 [[[6, 2], [5, 1], [4, 0]]], [[[4, 4], [5, 3], [6, 2]]],
 
 [[[2, 0], [4, 0], [6, 0]]], [[[1, 1], [2, 2], [3, 3]]],
 
 [[[7, 1], [6, 2], [5, 3]], [[5, 3], [4, 2], [3, 1]]],
 
 [[[8, 0], [6, 0], [4, 0]], [[4, 0], [3, 1], [2, 2]], [[2, 2], [3, 3], [4, 4]]]
 
 ]:
Best6:=
[[[[7, 3], [6, 4], [5, 5]]], [[[3, 3], [5, 3], [7, 3]]], [[[3, 1], [4, 2], [5,
3]]], [[[6, 0], [5, 1], [4, 2]]], [[[10, 0], [8, 0], [6, 0]]], [[[4, 0], [6, 0]
, [8, 0]]], [[[8, 2], [7, 1], [6, 0]], [[6, 0], [8, 0], [10, 0]], [[10, 0], [9,
1], [8, 2]], [[8, 2], [7, 3], [6, 4]]], [[[5, 5], [6, 4], [7, 3]], [[7, 3], [6,
2], [5, 1]]], [[[0, 0], [2, 0], [4, 0]], [[4, 0], [5, 1], [6, 2]]], [[[1, 1], [
2, 2], [3, 3]], [[3, 3], [4, 2], [5, 1]], [[5, 1], [6, 2], [7, 3]], [[7, 3], [5
, 3], [3, 3]], [[3, 3], [4, 4], [5, 5]]]]:
 
BestE:=
[[[3, 1], [2, 1], [1, 1]], [[0, 1], [1, 1
], [2, 1]], [[1, 3], [1, 2], [1, 1]], [[1, 1], [2, 1], [3, 1]], [[0, -1], [0, 0
], [0, 1]], [[2, 0], [1, 0], [0, 0]], [[4, 0], [3, 0], [2, 0]], [[4, 2], [4, 1]
, [4, 0]], [[0, 1], [0, 0], [0, -1]], [[0, -2], [0, -1], [0, 0]], [[-1, 2], [0,
2], [1, 2]], [[-2, 1], [-1, 1], [0, 1]], [[1, -2], [1, -1], [1, 0]], [[0, 1], [
0, 0], [0, -1]], [[1, 0], [2, 0], [3, 0]], [[0, 4], [0, 3], [0, 2]], [[-2, 0],
[-1, 0], [0, 0]], [[2, 4], [1, 4], [0, 4]], [[1, 2], [0, 2], [-1, 2]], [[-2, 2]
, [-1, 2], [0, 2]], [[2, -2], [2, -1], [2, 0]], [[3, 2], [2, 2], [1, 2]], [[0,
-1], [0, 0], [0, 1]], [[0, 1], [0, 2], [0, 3]], [[0, 4], [0, 3], [0, 2]], [[0,
2], [1, 2], [2, 2]], [[2, 3], [2, 2], [2, 1]], [[2, 1], [2, 0], [2, -1]], [[4,
0], [3, 0], [2, 0]], [[2, -1], [2, 0], [2, 1]], [[3, 1], [2, 1], [1, 1]]]:
 
##(it took         203633.750 secs. of CPU time to find)
 
####End Pre-Computed Data