三对三有解。
我用 Python 写了搜寻答案的程序。
要知道其它组合有没有解,只要改一改 “mCOUNT, cCOUNT = 3, 3” 这一行然后运行就知道了。
有空的话我会译成 Java 贴上来。
'''
Solve the Missionaries And Cannibals Puzzle by trying all legal moves.
The puzzle imposes two constraints:
1) Relative headcount: missionaries must be >= cannibals at any point.
2) Boat capacity: max is two.
'''
def comb( items, r ):
'''Returns all combinations of elements in items taken r at a time.'''
if r == 0:
yield ( ) # Returns tuple to enable direct conversion to set.
else:
for i in xrange( len( items ) ):
for subComb in comb( items[ i + 1 : ], r - 1 ):
yield ( items[ i ], ) + subComb
# Simply represent the elements of the puzzle by characters.
MISSIONARY, CANNIBAL, BOAT = 'm', 'c', 'B'
mCOUNT, cCOUNT = 3, 3
# Constraint #2: boat capacity.
nMAXCROSSER = 2
nMINCROSSER = 1
class RiverSide:
'''Represents the state of a riverside.'''
def __init__( self, men = [ ], boat = [ ] ):
self.men = men
self.boat = boat
def __eq__( self, other ):
self.men.sort( ); other.men.sort( )
return self.men == other.men and self.boat == other.boat
def __repr__( self ):
return 'BOAT' + `self.boat`.ljust( 8 ) + 'MEN' + `self.men`
def _xferBoat( self, otherSide ):
'''To be called only by xferMen( ).'''
otherSide.boat.append( self.boat.pop( ) )
def xferMen( self, otherSide, menList ):
for man in menList:
otherSide.men.append( self.men.pop( self.men.index( man ) ) )
# Nice to automate boat xfer here.
self._xferBoat( otherSide )
# Constraint #1: relative headcount.
def fatal( self ):
'''Returns true iff the cannibals outnumbers missionaries.'''
mCount = self.men.count( MISSIONARY )
return mCount and mCount < self.men.count( CANNIBAL )
class RiverScene:
'''Represents the state of a riverscene.'''
def __init__( self, sourceSide = RiverSide( ), targetSide = RiverSide( ) ):
self.source = sourceSide
self.target = targetSide
def __eq__( self, other ):
return self.source == other.source and self.target == other.target
def __repr__( self ):
return `self.source` + '\n' + `self.target`
def fatal( self ):
return self.source.fatal( ) or self.target.fatal( )
def solve( firstScene, finalScene ):
'''Returns a list of solution steps if solution's found; else returns None.'''
def solutionSteps( takenSteps ):
'''
The solution searching recursive workhorse function.
Takes a list containing the first scene and returns a list of
solution steps leading to the final scene if solution was found.
Optimizations done:
1) elimination of equivalent combinations of men to be moved
2) maximization of headcount to move from source
(minimization for the reverse direction)
'''
lastStep = takenSteps[ - 1 ]
if lastStep == finalScene: return takenSteps
from copy import deepcopy
newStep = deepcopy( lastStep )
# To enable moving of both direction to share the same chunk of code.
start, stop, step = nMAXCROSSER, nMINCROSSER - 1, -1
src, dst = newStep.source, newStep.target
if dst.boat:
start, stop, step = nMINCROSSER, nMAXCROSSER + 1, 1
src, dst = dst, src
for nCrosser in range( start, stop, step ):
for men in set( comb( src.men, nCrosser ) ):
src.xferMen( dst, men )
if not newStep.fatal( ) and newStep not in takenSteps:
takenSteps.append( newStep )
sol = solutionSteps( takenSteps )
if sol:
return sol
else:
takenSteps.pop( )
# Rewind before trying next move.
dst.xferMen( src, men )
takenSteps = [ firstScene ]
return solutionSteps( takenSteps )
# Setup.
men = [ MISSIONARY ] * mCOUNT + [ CANNIBAL ] * cCOUNT
boat = [ BOAT ]
source = RiverSide( men, boat )
target = RiverSide( )
firstScene = RiverScene( source, target )
finalScene = RiverScene( target, source )
print '\nTrying to solve puzzle of', mCOUNT, 'missionaries and', cCOUNT, 'cannibals...\n'
solutionSteps = solve( firstScene, finalScene )
if solutionSteps:
print 'Solution found:\n\n'
for step in solutionSteps:
print step, '\n'
else:
print 'No solution found.'
温馨提示:答案为网友推荐,仅供参考