```"""
pegs.py

triangular peg solitaire
See for example https://en.wikipedia.org/wiki/Peg_solitaire

.              initial puzzle position
* *             * = peg
* * *            . = hole
* * * *
* * * * *

Legal moves consist of jumping one peg over another to an empty square.
The goal is to find a sequence of moves that elimates all but one peg,
leaving that one in the initial hole.

Invoke it with the size on the command line.

\$ time python pegs.py 5
Solving a size 5 triangular peg puzzle ...
found a 13 move solution after looking at 579 positions:

.
* *
* * *
* * * *
* * * * *

*
. *
. * *
* * * *
* * * * *

*
. *
* . .
* * * *
* * * * *

.
. .
* . *
* * * *
* * * * *

.
* .
. . *
. * * *
* * * * *

.
* *
. . .
. * * .
* * * * *

.
* *
. * .
. . * .
* . * * *

.
* *
. * .
. . * .
* * . . *

.
* *
. * .
. . * .
. . * . *

.
* *
. * *
. . . .
. . . . *

.
* .
. * .
. . . *
. . . . *

.
* .
. * *
. . . .
. . . . .

.
* .
* . .
. . . .
. . . . .

*
. .
. . .
. . . .
. . . . .

real	0m0.061s
user	0m0.047s
sys	0m0.009s

Jim Mahoney | Dec 2019 | cs.marlboro.college | MIT License
"""
import sys

def get_size():
""" Return puzzle size from command line or default """
try:
return int(sys.argv)
except:
return 5   # default size

class Board:
""" a triangular peg solitaire board
>>> b = Board(5)
>>> print(b)
.
* *
* * *
* * * *
* * * * *
>>> len(b.moves)              # number of conceivable moves
36
>>> legal_move    = ( (2,0),(1,0),(0,0) )
>>> illegal_move  = ( (2,0),(2,1),(2,2) )
>>> b.can_move(legal_move)
True
>>> b.can_move(illegal_move)
False
>>> b.do_move(legal_move)
>>> print(b)
*
. *
. * *
* * * *
* * * * *
>>> b.n_pegs
13
>>> b.undo_move(legal_move)
>>> print(b)
.
* *
* * *
* * * *
* * * * *
>>> b.n_pegs
14
"""

def __init__(self, size, hole=(0,0)):
self.size = size
self.n_pegs = size*(size+1)//2 - 1 # e.g. 14 pegs (1 hole) for size=5
self.hole = hole                   # position of inititial hole
self.cells = self.get_cells(hole)  # array of initial cells
self.moves = self.get_moves()      # possible move locations
self.history = []                  # moves made to reach this position
self.n_positions = 0               # counting searched positions

def get_cells(self, hole):
""" Create and return the cells for the intial board position. """
#
# The board cells is stored as a list of lists, top to bottom,
# with True,False values for filled,empty cells.
#
# For a board of size 5, the initial position would be
#
#  [[True],
#   [True, True],
#   [True, True, True],
#   [True, True, True, True],
#   [True, True, False, True, True]]
#
# This means that the coordinate positions on the board are
#               (0,0)
#            (1,0)  (1,1)
#        (2,0)  (2,1)  (2,2)
#    (3,0)  (3,1)  (3,2)  (3,2)
# and so on.
#
cells = []
for i in range(1, self.size+1):
cells.append([True]*i)
cells[hole][hole] = False
return cells

def get_moves(self):
""" Return the coordinate triples where moves might occur, e.g.
[ ((0,0),(1,0),(2,0)),  ((2,0),(1,0),(0,0)),  ... ]
Each move consists of (start, skip, land) coordinates
and each coordinate is a (row, column) pair.
"""
moves = []
for row in range(0, self.size-2):      # from top to 2 up from bottom
for col in range(0, row+1):        # full width of each row
# The idea here is to loop over all 3x3 triangles on the board,
# with (row,col) at the top of this little. Then there are
# six possible moves in this triangle: down, across, slant,
# and the reverse of each. Here's the picture :
#    *   <---(row,col)    * down                  *  slant
#    * *                  *                         *
#    * * *                *         * * * across      *
down   = ((row,col),   (row+1,col),   (row+2,col))
across = ((row+2,col), (row+2,col+1), (row+2,col+2))
slant  = ((row,col),   (row+1,col+1), (row+2,col+2))
for move in (down, across, slant):
moves.append(move)
moves.append(tuple(reversed(move)))
return sorted(moves)

def __str__(self):
result = ""
for row in range(0, self.size):
result += " "*(self.size - row)
for col in range(0, row+1):
if self.cells[row][col]:
result += "* "
else:
result += ". "
result += "\n"
return result[0:-1]      # omit last newline

def is_peg(self, coord):
""" Return True if there's a peg at the given coordinate. """
return self.cells[coord][coord]

def set_cell(self, coord, value):
""" Put a True or False value (i.e. peg or no peg) into a cell """
self.cells[coord][coord] = value

def can_move(self, move):
""" Return True if the current board allows the given move """
# i.e. if the (start,skip,land) positions are (True,True,False)
(start, skip, land) = move
return     self.is_peg(start) and \
self.is_peg(skip) and \
not self.is_peg(land)

def do_move(self, move):
""" Apply a move to the board. """
(start, skip, land) = move
self.set_cell(start, False)
self.set_cell(skip,  False)
self.set_cell(land,  True)
self.history.append(move)
self.n_pegs -= 1

def undo_move(self, move):
""" Undo a move on the board. """
(start, skip, land) = move
self.set_cell(start, True)
self.set_cell(skip,  True)
self.set_cell(land,  False)
self.history.pop(-1)
self.n_pegs += 1

def is_solved(self):
""" Return True if this position is in the solved state """
# i.e. one peg in the initial hole position
return self.n_pegs == 1 and self.is_peg(self.hole)

def print_playback(self, moves=None):
""" Print each position that led to this one. """
board = Board(self.size)
print()
print(board)
if not moves:
moves = self.history
for move in moves:
board.do_move(move)
print()
print(board)
print()

def solve(board):
""" Search for a solution. Return True if found,
leaving board in a solved state. """
# ... using a recursive backtracking search.
board.n_positions += 1                 # number of positions examined.
if board.is_solved():
return True
else:
for move in board.moves:
if board.can_move(move):
board.do_move(move)
if solve(board):
return True
board.undo_move(move)
return False

def main():
"""Solve the peg puzzle """
board = Board(get_size())
print('Solving a size {} triangular peg puzzle ...'.format(board.size))
if solve(board):
print('found a {} move solution after looking at {} positions:'.format(
len(board.history), board.n_positions))
board.print_playback()
else:
print('no solution found after looking at {} positions.'.format(
board.n_positions))

if __name__ == "__main__":
import doctest
doctest.testmod()
main()
```