#!/usr/bin/env python
"""
Puzzle Pegs
* problem 12.1 #10 from Leviti'sn "Design & Analysis of Algorithms"
* part of hpomework due May 3
* initial puzzle position
* * * = peg
* * * . = hole
* * * *
* * . * *
Legal moves consist of jumping one peg over another to an empty square.
(a) Find a shortest sequence of moves that eliminates all but one,
leaving the last peg anywhere.
(b) Same but leave the last peg in the orginal empty hole.
For reasons that I don't understand, doing (a) finds
the (b) solution first anyway, though there are other solutions.
Also, sorting (by move number) the list of possible moves
gives a solution quicker. Again, I'm not sure why.
Having it search over all positions and count how many solutions
there are, and how many for each final peg position might answer
this, particularly if it turns out there are a many more solutions
with the final peg in the bottom center than other places.
Jim M
"""
# See the bottom of this file for program output.
__version__ = "$Id: pegs.py 13934 2007-06-03 18:50:36Z mahoney $"
class Board:
"""
Puzzle Peg board implementation
>>> b = Board(5)
>>> b.size
5
>>> b.n_pegs
14
>>> print b
*
* *
* * *
* * * *
* * . * *
>>> len(b.triples) # number of move locations
36
>>> len(Board(3).triples[0]) # each of which has 3 coordinates
3
>>> len(Board(3).triples[0][0]) # each of which is made up of 2 numbers
2
>>> good_move = ( (2,0),(3,1),(4,2) )
>>> bad_move = ( (2,0),(2,1),(2,2) )
>>> b.can_move(good_move)
True
>>> b.can_move(bad_move)
False
>>> b.do_move(good_move)
>>> print b
*
* *
. * *
* . * *
* * * * *
>>> b.n_pegs
13
>>> b.undo_move(good_move)
>>> print b
*
* *
* * *
* * * *
* * . * *
>>> b.n_pegs
14
"""
def __init__(self, size=5):
self.size = size
self.n_pegs = size*(size+1)/2 - 1 # e.g. 14 pegs (1 hole) for size=5
self.data = self.get_initial_data()
self.triples = self.get_triples() # legal move locations
self.solution_goal = False # last peg (row,col) ; False => any
self.n_positions = 0 # positions searched
self.moves = [] # moves made to reach this position
def get_initial_data(self):
"""
Create and return the data for the intial board position.
For a board of size 5 this is
[[True],
[True, True],
[True, True, True],
[True, True, True, True],
[True, True, False, True, True]]
"""
data = []
for i in range(1, self.size+1):
data.append([True]*i)
hole = self.get_bottom_center()
data[hole[0]][hole[1]] = False
return data
def get_bottom_center(self):
"""Return (row,col) of starting hole."""
return ((self.size-1), (self.size-1)/2)
def get_triples(self):
"""
Return the coordinate triples where moves may occur, e.g.
[ ((0,0),(1,0),(2,0)), ((2,0),(1,0),(0,0)), ... ]
Each triple consists of lega (start, skip, land) coordiates.
"""
triples = []
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
# move triples in triangle from below and right of (row,col)
# * <---(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 triple in (down, across, slant):
triples.append(triple)
triples.append(tuple(reversed(triple)))
return triples
def __str__(self):
result = ""
for row in range(0, self.size):
result += " "*(self.size - row)
for col in range(0, row+1):
if self.data[row][col]:
result += "* "
else:
result += ". "
result += "\n"
return result[0:-1] # omit last newline
def get_peg(self, coord):
"""Return True if there's a peg at the given coordinate. """
return self.data[coord[0]][coord[1]]
def set_peg(self, coord, value):
"""Put or remove (i.e. value=True or False) a peg on the board"""
self.data[coord[0]][coord[1]] = value
def can_move(self, move):
"""
Return True if the current board allows the given move,
which requires that the (start,skip,land) positions
be (True, True, False)
"""
(start, skip, land) = move
return self.get_peg(start) and self.get_peg(skip) \
and not self.get_peg(land)
def do_move(self, move):
(start, skip, land) = move
self.set_peg(start, False)
self.set_peg(skip, False)
self.set_peg(land, True)
self.moves.append(move)
self.n_pegs -= 1
def undo_move(self, move):
(start, skip, land) = move
self.set_peg(start, True)
self.set_peg(skip, True)
self.set_peg(land, False)
self.moves.pop(-1)
self.n_pegs += 1
def search(self):
"""Recursive backtrack search for a solution from current position."""
self.n_positions += 1
if self.n_pegs == 1:
if self.solution_goal:
if self.get_peg(self.solution_goal):
return True
else:
return False
else:
return True
else:
result = False
# for triple in self.triples # size=5 sol'n at 14812
# for triple in reversed(self.triples): # size=5 sol'n at 545
for triple in sorted(self.triples): # size=5 son'n at 380
if self.can_move(triple):
self.do_move(triple)
if self.search():
result = True
break
self.undo_move(triple)
return result
def print_playback(self):
"""Print each position that led to this position."""
board = Board(self.size)
print board
for move in self.moves:
board.do_move(move)
print
print board
def analyze(self, goal=False):
self.solution_goal = goal
if goal:
print "Searching for 1 peg at " + str(goal) + " ..."
else:
print "Searching for 1 peg anywhere ..."
result = self.search()
if result:
print "Solution found after " + str(self.n_positions) + \
" positions examined."
self.print_playback()
else:
print "No solution found."
def search_all_goals(size=5):
print "Searching for solutions with a peg in each position."
n_yes = 0
n_no = 0
for row in range(0, size):
for col in range(0, row+1):
board = Board(size)
board.solution_goal = (row,col)
print " " + str((row,col)) + " ... ",
if board.search():
n_yes += 1
print "yes",
else:
n_no += 1
print "no",
print " (" + str(board.n_positions) + " positions)"
print "Done. Possible=" + str(n_yes) + "; impossible=" + str(n_no)
def solve(size=5, goal=False):
"""Solve the peg puzzle with the given final position goal."""
print
board = Board(size)
if goal==True:
goal = board.get_bottom_center()
board.analyze(goal)
def run():
""" Run the program from the command line. """
import sys
from optparse import OptionParser
parser = OptionParser(
usage="usage: %prog [options]\n\n Solve the puzzle peg problem.")
parser.add_option("-s", "--size", type="int",
dest="size", help="size of board")
parser.add_option("-v", action="store_true", default=False, \
dest="verbose_tests", help="verbose tests only")
parser.add_option("-a", "--all", action="store_true", default=False,
dest="all_goals", help="all goals searched")
(options, args)=parser.parse_args()
if options.verbose_tests:
sys.exit(0) # The tests are always run; -v is caught by _test()
elif options.all_goals and options.size:
search_all_goals(options.size)
elif options.size:
solve(options.size, False)
solve(options.size, True)
solve(options.size, (0,0))
else:
parser.print_help()
sys.exit(2)
def _test():
"""
Run tests in comment strings.
If the command line arguments include "-v",
then verbose test output is printed;
otherwise, nothing is printed if the tests are all successful.
"""
import doctest
doctest.testmod()
if __name__ == "__main__":
_test()
run()
# -----------------------------------------------------------
"""
mahoney@cs homework$ ./pegs.py -h
usage: pegs.py [options]
Solve the puzzle peg problem.
options:
-h, --help show this help message and exit
--size=SIZE size of board (default 5)
-v verbose tests only
mahoney@cs homework$ ./pegs.py --size=3
Searching for 1 peg anywhere ...
No solution found.
Searching for 1 peg at (2, 1) ...
No solution found.
Searching for 1 peg at (0, 0) ...
No solution found.
mahoney@cs homework$ ./pegs.py --size=4
Searching for 1 peg anywhere ...
Solution found after 37 positions examined.
*
* *
* * *
* . * *
*
* *
* * *
* * . .
*
* *
* * *
. . * .
*
. *
. * *
* . * .
*
* *
. . *
* . . .
.
. *
* . *
* . . .
*
. .
* . .
* . . .
*
* .
. . .
. . . .
.
. .
* . .
. . . .
Searching for 1 peg at (3, 1) ...
No solution found.
Searching for 1 peg at (0, 0) ...
No solution found.
mahoney@cs homework$ ./pegs.py --size=5
Searching for 1 peg anywhere ...
Solution found after 380 positions examined.
*
* *
* * *
* * * *
* * . * *
*
* *
. * *
* . * *
* * * * *
.
. *
* * *
* . * *
* * * * *
.
. .
* . *
* * * *
* * * * *
.
* .
. . *
. * * *
* * * * *
.
* *
. . .
. * * .
* * * * *
.
* *
. * .
. . * .
* . * * *
.
* *
. * *
. . . .
* . . * *
.
. *
. . *
. . * .
* . . * *
.
. .
. . .
. . * *
* . . * *
.
. .
. . *
. . * .
* . . * .
.
. .
. . .
. . . .
* . * * .
.
. .
. . .
. . . .
* * . . .
.
. .
. . .
. . . .
. . * . .
Searching for 1 peg at (4, 2) ...
Solution found after 380 positions examined.
*
* *
* * *
* * * *
* * . * *
*
* *
. * *
* . * *
* * * * *
.
. *
* * *
* . * *
* * * * *
.
. .
* . *
* * * *
* * * * *
.
* .
. . *
. * * *
* * * * *
.
* *
. . .
. * * .
* * * * *
.
* *
. * .
. . * .
* . * * *
.
* *
. * *
. . . .
* . . * *
.
. *
. . *
. . * .
* . . * *
.
. .
. . .
. . * *
* . . * *
.
. .
. . *
. . * .
* . . * .
.
. .
. . .
. . . .
* . * * .
.
. .
. . .
. . . .
* * . . .
.
. .
. . .
. . . .
. . * . .
Searching for 1 peg at (0, 0) ...
Solution found after 579 positions examined.
*
* *
* * *
* * * *
* * . * *
*
* *
. * *
* . * *
* * * * *
.
. *
* * *
* . * *
* * * * *
.
. .
* . *
* * * *
* * * * *
.
* .
. . *
. * * *
* * * * *
.
* *
. . .
. * * .
* * * * *
.
* *
. * .
. . * .
* . * * *
.
* *
. * .
. . * .
* * . . *
.
* *
. * .
. . * .
. . * . *
.
* *
. * *
. . . .
. . . . *
.
* .
. * .
. . . *
. . . . *
.
* .
. * *
. . . .
. . . . .
.
* .
* . .
. . . .
. . . . .
*
. .
. . .
. . . .
. . . . .
mahoney@cs homework$ time (./pegs.py --size=5 --all)
Searching for solutions with a peg in each position.
(0, 0) ... yes (579 positions)
(1, 0) ... no (2592133 positions)
(1, 1) ... no (2592133 positions)
(2, 0) ... no (2592133 positions)
(2, 1) ... yes (1640691 positions)
(2, 2) ... no (2592133 positions)
(3, 0) ... yes (578 positions)
(3, 1) ... no (2592133 positions)
(3, 2) ... no (2592133 positions)
(3, 3) ... yes (609 positions)
(4, 0) ... no (2592133 positions)
(4, 1) ... no (2592133 positions)
(4, 2) ... yes (380 positions)
(4, 3) ... no (2592133 positions)
(4, 4) ... no (2592133 positions)
Done. Possible=5; impossible=10
real 47m45.111s
user 47m45.127s
sys 0m0.044s
i.e.
Y
n n
n Y n
Y n n Y
n n Y n n
"""
syntax highlighted by Code2HTML, v. 0.93pm6