""" 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. $ time python pegs.py -- triangular peg puzzle size=5 -- Done: 13 move solution found, 579 positions examined. . * * * * * * * * * * * * * * * . * . * * * * * * * * * * * * . * * . . * * * * * * * * * . . . * . * * * * * * * * * * . * . . . * . * * * * * * * * . * * . . . . * * . * * * * * . * * . * . . . * . * . * * * . * * . * . . . * . * * . . * . * * . * . . . * . . . * . * . * * . * * . . . . . . . . * . * . . * . . . . * . . . . * . * . . * * . . . . . . . . . . * . * . . . . . . . . . . . * . . . . . . . . . . . . . . real 0m0.061s user 0m0.047s sys 0m0.009s Jim Mahoney | Dec 2019 | cs.marlboro.college | MIT License """ class Board: """ a triangular peg solitaire board >>> b = Board() >>> b.size 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=5, 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): """ Print each position that led to this one. """ board = Board(self.size) print(board) for move in self.history: board.do_move(move) print() print(board) def solve(board): """ Search for a solution to the puzzle; return True once one is found. """ # ... 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 """ size = 7 print('-- triangular peg puzzle size={} --'.format(size)) board = Board(size) if solve(board): print('Done: {} move solution found, {} positions examined.\n'.format( len(board.history), board.n_positions)) board.print_playback() else: print('Oops: no solutions found, {} positions examined.\n'.format( board.n_positions)) print() if __name__ == "__main__": import doctest doctest.testmod() main()