from __future__ import generators
''' Generic Puzzle Solving Framework
Designed for Python 2.2 or later
License: Public Domain
Author: Raymond Hettinger
Updates: http://users.rcn.com/python/download/python.htm
'''
# Revision In Use: 'File %n, Ver %v, Date %f'
version = 'File PUZZLE.PY, Ver 9, Date 27-Mar-2002,3:17:34'
''' Simple Instructions:
Create your puzzle as a subclass of Puzzle().
The first step is to choose a representation of the problem
state preferably stored as a string. Set 'pos' to the starting
position and 'goal' to the ending position. Create a genmoves()
method that computes all possible new puzzle states reachable from
the current state. Call the .solve() method to solve the puzzle.
Important Note:
The genmoves() method must return a list of puzzle instances, not
their representations. It should be written as a generator, returning
its results through yield.
Advanced Instructions:
1. .solve(depthFirst=1) will override the default breadth first search.
Use depth first when the puzzle known to be solved in a fixed number
of moves (for example, the eight queens problem is solved only when
the eighth queen is placed on the board; also, the triangle tee problem
removes one tee on each move until all tees are removed). Breadth first
is ideal when the shortest path solution needs to be found or when
some paths have a potential to wander around infinitely (i.e. you can
randomly twist a Rubik's cube all day and never come near a solution).
2. Define __repr__ for a pretty printed version of the current position.
The state for the Tee puzzle looks best when the full triangle is drawn.
3. If the goal state can't be defined as a string, override the isgoal()
method. For instance, the block puzzle is solved whenever block 1 is
in the lower left, it doesn't matter where the other pieces are; hence,
isgoal() is defined to check the lower left corner and return a boolean.
4. Some puzzle's can be simplified by treating symmetric positions as
equal. Override the .canonical() method to pick one of the equilavent
positions as a representative. This allows the solver to recognize paths
similar ones aleady explored. In tic-tac-toe an upper left corner on
the first move is symmetrically equivalent to a move on the upper right;
hence there are only three possible first moves (a corner, a midde side,
or in the center).
'''
class Puzzle:
pos = "" # default starting position
goal = "" # ending position used by isgoal()
def __init__( self, pos=None ):
if pos: self.pos = pos
def __repr__(self): # returns a string representation of the position for printing the object
return repr(self.pos)
def canonical(self): # returns a string representation after adjusting for symmetry
return repr(self)
def isgoal(self):
return self.pos == self.goal
def __iter__(self): # returns list of objects of this class
if 0: yield self
def solve( pos, depthFirst=0 ):
queue, trail, solution = [pos], {intern(pos.canonical()):None}, []
load = depthFirst and queue.append or (lambda m: queue.insert(0,m))
while not pos.isgoal():
for m in pos:
c = m.canonical()
if c in trail: continue
trail[intern(c)] = pos
load(m)
pos = queue.pop()
while pos:
solution.insert(0, pos)
pos = trail[pos.canonical()]
return solution
# Sample Puzzles start here
if __name__ == '__main__':
class JugFill( Puzzle ):
'''Given a two empty jugs with 3 and 5 liter capacities and a full
jug with 8 liters, find a sequence of pours leaving four liters
in the two largest jugs'''
pos = (0,0,8)
capacity = (3,5,8)
goal = (0,4,4)
def __iter__(self):
for i in range(len(self.pos)):
for j in range(len(self.pos)):
if i==j: continue
qty = min( self.pos[i], self.capacity[j] - self.pos[j] )
if not qty: continue
dup = list( self.pos )
dup[i] -= qty
dup[j] += qty
yield JugFill(tuple(dup))
class EightQueens( Puzzle ):
' Place 8 queens on chess board such that no two queens attack each other'
def isgoal(self):
return len(self.pos) == 8
def __iter__( self ):
x = len(str(self))
for y in range(8):
if str(y) in self.pos: continue
for xp in range(len(self.pos)):
yp = int(self.pos[xp])
if abs(x-xp) == abs(y-yp):
break
else:
yield EightQueens(self.pos + str(y))
class TriPuzzle( Puzzle ):
''' Triangle Tee Puzzle
Tees are arranged in holes on a 5x5 equalateral triangle except for the
top center which left open. A move consist of a checker style jump of
one tee over the next into an open hole and removed the jumped tee. Find
a sequence of jumps leaving the last tee in the top center position.
'''
pos = '011111111111111'
goal = '100000000000000'
triples = [[0,1,3], [1,3,6], [3,6,10], [2,4,7], [4,7,11], [5,8,12],
[10,11,12], [11,12,13], [12,13,14], [6,7,8], [7,8,9], [3,4,5],
[0,2,5], [2,5,9], [5,9,14], [1,4,8], [4,8,13], [3,7,12]]
def __iter__( self ):
for t in self.triples:
if self.pos[t[0]]=='1' and self.pos[t[1]]=='1' and self.pos[t[2]]=='0':
yield TriPuzzle(self.produce(t,'001'))
if self.pos[t[0]]=='0' and self.pos[t[1]]=='1' and self.pos[t[2]]=='1':
yield TriPuzzle(self.produce(t,'100'))
def produce( self, t, sub ):
return self.pos[:t[0]] + sub[0] + self.pos[t[0]+1:t[1]] + sub[1] + self.pos[t[1]+1:t[2]] + sub[2] + self.pos[t[2]+1:]
def canonical( self ):
return self.pos
def __repr__( self ):
return '\n %s\n %s %s\n %s %s %s\n %s %s %s %s\n%s %s %s %s %s\n' % tuple(self.pos)
class MarblePuzzle( Puzzle ):
''' Black/White Marble
Given eleven slots in a line with four white marbles in the leftmost
slots and four black marbles in the rightmost, make moves to put the
white ones on the right and the black on the left. A valid move for
a while marble isto shift right into an empty space or hop over a single
adjacent black marble into an adjacent empty space -- don't hop over
your own color, don't hop into an occupied space, don't hop over more
than one marble. The valid black moves are in the opposite direction.
Alternate moves between black and white marbles.
In the tuple representation below, zeros are open holes, ones are whites,
negative ones are blacks, and the outer tuple tracks whether it is
whites move or blacks.
'''
pos = (1,(1,1,1,1,0,0,0,-1,-1,-1,-1))
goal = (-1,-1,-1,-1,0,0,0,1,1,1,1)
def isgoal( self ):
return self.pos[1] == self.goal
def __iter__( self ):
(m,b) = self.pos
for i in range(len(b)):
if b[i] != m: continue
if 0<=i+m+m>1)&1 == (n>>3)&1) or ( (n>>2)&1 != (n>>1)&1 != (n&1) ):
yield RowboatPuzzle(n)
def __repr__( self ):
v = ','
if self.pos&8: v=v+'M'
else: v='M'+v
if self.pos&4: v=v+'D'
else: v='D'+v
if self.pos&2: v=v+'C'
else: v='C'+v
if self.pos&1: v=v+'S'
else: v='S'+v
return v
import re
import string
class PaPuzzle( Puzzle ):
''' PaPuzzle
This sliding block puzzle has 9 blocks of varying sizes:
one 2x2, four 1x2, two 2x1, and two 1x1. The blocks are
on a 5x4 grid with two empty 1x1 spaces. Starting from
the position shown, slide the blocks around until the
2x2 is in the lower left:
1122
1133
45
6788
6799
'''
pos = '11221133450067886799'
goal = re.compile( r'................1...' )
def isgoal(self):
return self.goal.search(self.pos) != None
def __repr__( self ):
ans = '\n'
pos = self.pos.replace( '0', '.' )
for i in [0,4,8,12,16]:
ans = ans + pos[i:i+4] + '\n'
return ans
xlat = string.maketrans('38975','22264')
def canonical( self ):
return self.pos.translate( self.xlat )
block = { (0,-4):None, (1,-4):None, (2,-4):None, (3,-4):None,
(16,4):None, (17,4):None, (18,4):None, (19,4):None,
(0,-1):None, (4,-1):None, (8,-1):None, (12,-1):None, (16,-1):None,
(3,1):None, (7,1):None, (11,1):None, (15,1):None, (19,1):None, }
def __iter__( self ):
dsone = self.pos.find('0')
dstwo = self.pos.find('0',dsone+1)
for dest in [dsone, dstwo]:
for adj in [-4,-1,1,4]:
if (dest,adj) in self.block: continue
piece = self.pos[dest+adj]
if piece == '0': continue
newmove = self.pos.replace(piece, '0')
for i in range(20):
if 0 <= i+adj < 20 and self.pos[i+adj]==piece:
newmove = newmove[:i] + piece + newmove[i+1:]
if newmove.count('0') != 2: continue
yield PaPuzzle(newmove)
print Puzzle().solve()
print JugFill().solve()
print EightQueens().solve( depthFirst=1 )
print TriPuzzle().solve()
print MarblePuzzle().solve(depthFirst=1)
print RowboatPuzzle().solve()
print PaPuzzle().solve()