Java算法：解决传教士与野人渡河安全摆渡问题

import java.util.*; 
import java.io.*; 

/** 
* Missionaries And Cannibals Puzzle Solver. 
* 
* Solution to the puzzle must not violate any of the following 2 rules: 
* 1) Relative headcount: cannibals can't outnumber missionaries at any point. 
* 2) Boat's loading: mustn't exceed the max. 
*/ 
public class MACPS { 
public class SolutionNotFoundException extends RuntimeException { } 

static final Object MISSIONARY = "m", // Simple representation 
CANNIBAL = "c", // of objects 
BOAT = "v"; // in the puzzle. 
private int boat_max_load, 
boat_min_load = 1; // Shouldn't be any other value. 
private RiverScene firstScene, 
finalScene; 

// Recursively searches for a solution using Depth-First Search strategy. 
// Takes a Stack containing only the first scene (root of tree). 
// Returns a collection of scenes connecting the first scene to the final. 
// Throws SolutionNotFoundException for obvious reason. 
// Deploys the following optimization strategy: 
// Transfers as much as possible from source side, 
// as little as possible from target side. 
private Collection getSolutionSteps( Stack takenSteps ) { 
RiverScene lastScene = ( RiverScene ) takenSteps.peek( ); 

if( lastScene.equals( finalScene ) ) return takenSteps; 

RiverScene newStep = lastScene.deepCopy( ); 

// To allow transfer in both directions to share the same chunk of code. 
int start = boat_max_load, 
stop = boat_min_load - 1, 
step = -1; 
RiverSide from = newStep.lside, 
to = newStep.rside; 
if( to.hasBoat( ) ) { 
start = boat_min_load; 
stop = boat_max_load + 1; 
step = 1; 
from = newStep.rside; 
to = newStep.lside; 
} 

for( int nPassenger = start; nPassenger != stop; nPassenger += step ) { 
Collection menCombs = new HashSet( // HashSet eliminates duplicates. 
Combinatorics.combinations( from.getMenList( ), nPassenger ) ); 

nextComb: 
for( Iterator comb = menCombs.iterator( ); comb.hasNext( ); ) { 
Collection menList = ( Collection ) comb.next( ); 
try { 
from.transferMen( to, menList ); 

// If it's a taken step, undo and try next combination. 
for( Iterator i = takenSteps.iterator( ); i.hasNext( ); )