野人過河代碼

『壹』 用java實現野人傳教士過河問題

解題時可以把渡河的過程省略掉，也就是可以忽略河的存在。
為了用 Java 解這道題，我寫了 3 個類：
河邊（RiverSide）、河景（RiverScene）和解題者（MACPS，即 Missionaries And Cannibals Puzzle Solver）。

問題中的傳教士、野人和船都是非常簡單的物件，所以就簡單地用單字元字元串「m」、「c」 和 「v」來代表。

其實那三個類都很簡單；它們之間的關系也很簡單：
1）每個河邊都能有 0 或更多的 m 和 c，及最多 1 個 v。
2）每個河景里有兩個河邊。
3）解題者里有兩個河景：初始河景和終極河景。

解題者的任務就是要搜索出能把初始河景及終極河景連起來的河景系列。
解題者的 getSolutionSteps（ ）以遞歸的方式作深度優先搜索。

其它兩個「類」（Combinatorics 和 Copy）都是只提供一個方法的簡單類。

代碼里有文檔。 有不明白的地方可以問。
你可以用類似 Jacobe （http://www.tiobe.com/jacobe.htm）的程序恢復代碼原有的縮進。

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 plicates.
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( ); )
if( i.next( ).equals( newStep ) ) {
to.transferMen( from, menList );
continue nextComb;
}

takenSteps.push( newStep );
return getSolutionSteps( takenSteps );
}
catch( SecurityException e ) {
// Transfer didn't take place. Just try next combination.
}
catch( SolutionNotFoundException e ) {
// New step led to no solution in leaves. Undo, then next.
takenSteps.pop( );
to.transferMen( from, menList );
}
}
}
// All possible steps led to no solution, so
throw new SolutionNotFoundException( );
}

// Do setup, then kick-starts getSolutionSteps( Stack takenSteps ).
public Collection
getSolutionSteps( int nMissionary, int nCannibal, int boatCapacity ) {
if( nMissionary < 0 || nCannibal < 0 || boatCapacity < 0 )
throw new IllegalArgumentException( "Negative argument value." );

RiverSide sourceSide = new RiverSide( nMissionary, nCannibal, true ),
targetSide = new RiverSide( 0, 0, false );
boat_max_load = boatCapacity;
firstScene = new RiverScene( sourceSide, targetSide );
finalScene = new RiverScene( targetSide, sourceSide );

if( firstScene.lside.fatal( ) ) // First scene can be valid but fatal.
throw new SolutionNotFoundException( );

Stack steps = new Stack( );
steps.push( firstScene );
return getSolutionSteps( steps );
}

public static void main( String[ ] args ) {
int nMissionary = 3,
nCannibal = 3,
boatCapacity = 2;

System.out.println(
"\nSolving the puzzle of Missionaries And Cannibals with\n" +
nMissionary + " missionaries and " + nCannibal + " cannibals " +
"and a boat that can take up to " + boatCapacity + " creatures.." );

try {
Collection steps = new MACPS( ).
getSolutionSteps( nMissionary, nCannibal, boatCapacity );
System.out.println( "\nSolution found:\n" );
for( Iterator step = steps.iterator( ); step.hasNext( ); )
System.out.println( step.next( ) + "\n" );
}
catch( SolutionNotFoundException e ) {
System.out.println( "\nNo solution found." );
}
}
}

/**
* Represents a riverside in the puzzle.
*/
class RiverSide implements Serializable {
private ArrayList men = new ArrayList( ),
boat = new ArrayList( );

public RiverSide( int nMissionary, int nCannibal, boolean withBoat ) {
men.addAll( Collections.nCopies( nMissionary, MACPS.MISSIONARY ) );
men.addAll( Collections.nCopies( nCannibal, MACPS.CANNIBAL ) );
Collections.sort( men );
if( withBoat ) boat.add( MACPS.BOAT );
}

public RiverSide deepCopy( ) {
return ( RiverSide ) Copy.deepCopy( this );
}

public Collection getMenList( ) {
return ( Collection ) Copy.deepCopy( men );
}

public boolean equals( Object otherSide ) {
RiverSide other = ( RiverSide ) otherSide;
Collections.sort( men );
Collections.sort( other.men );
return this.men.equals( other.men ) && this.boat.equals( other.boat );
}

public String toString( ) {
return "BOAT" + boat + "\t" + "MEN" + men;
}

public boolean hasBoat( ) {
return ! boat.isEmpty( );
}

// Checks for violation of Rule #1.
public boolean fatal( ) {
int mCount = 0, cCount = 0;
for( Iterator i = men.iterator( ); i.hasNext( ); ) {
Object val = i.next( );
if( val.equals( MACPS.MISSIONARY ) ) ++mCount;
if( val.equals( MACPS.CANNIBAL ) ) ++cCount;
}
return mCount > 0 && mCount < cCount;
}

// Throws SecurityException if the transfer of all men in menList
// from this to destination *will* result in violation of Rule #1.
// Else, executes the transfer.
public void transferMen( RiverSide destination, Collection menList ) {
for( Iterator i = menList.iterator( ); i.hasNext( ); )
destination.men.add( men.remove( men.indexOf( i.next( ) ) ) );

// A nice place to automate boat transfer.
_transferBoat( destination );

// Undo the transfer if it led to violation of Rule #1.
if( fatal( ) || destination.fatal( ) ) {
destination.transferMen( this, menList );
throw new SecurityException( );
}
}

// Tansfers boat from this to destination. Called only by transferMen( ).
private void _transferBoat( RiverSide destination ) {
destination.boat.add( boat.remove( 0 ) );
}
}

/**
* Combines two riversides. Serves mainly as a data object.
*/
class RiverScene implements Serializable {
RiverSide lside, rside; // Package access.

public RiverScene( RiverSide lside, RiverSide rside ) {
this.lside = lside.deepCopy( );
this.rside = rside.deepCopy( );
}

public RiverScene deepCopy( ) {
return ( RiverScene ) Copy.deepCopy( this );
}

public boolean equals( Object otherScene ) {
RiverScene other = ( RiverScene ) otherScene;
return lside.equals( other.lside ) && rside.equals( other.rside );
}

public String toString( ) {
return "Left Side:\t" + lside + "\n" + "Right Side:\t" + rside;
}
}

/**
* Provides a static method to generate combinations of items taken r at a time.
*/
class Combinatorics {
public static Collection combinations( Collection items, int r ) {
if( r == 0 ) // Return [ [ ] ]. Note that [ ] denotes a List.
return Collections.nCopies( 1, new ArrayList( ) );

List = new ArrayList( items ), // To enable subListing of items.
result = new ArrayList( );
for( int i = 0; i < .size( ); ++i ) {
Collection subCombs =
combinations( .subList( i + 1, .size( ) ), r - 1 );
for( Iterator iter = subCombs.iterator( ); iter.hasNext( ); ) {
// Assign [ [ items.get( i ) ] ] to subComb.
List subComb = new ArrayList( .subList( i, i + 1 ) );

subComb.addAll( ( List ) iter.next( ) );
result.add( subComb );
}
}
return result;
}
}

/**
* Provides a static method to perform deep of object via serialization.
*/
class Copy {
public static Object deepCopy( Object o ) {
try {
ByteArrayOutputStream baos = new ByteArrayOutputStream( );
ObjectOutputStream oos = new ObjectOutputStream( baos );
oos.writeObject( o );
oos.close( );

ObjectInputStream ois =
new ObjectInputStream(
new ByteArrayInputStream( baos.toByteArray( ) ) );
return ois.readObject( );
}
catch ( Exception e ) {
throw new RuntimeException( e );
}
}
}