""" 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[1]) 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[0]][hole[1]] = 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[0]][coord[1]] def set_cell(self, coord, value): """ Put a True or False value (i.e. peg or no peg) into a cell """ self.cells[coord[0]][coord[1]] = 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()