macps.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 {
	}

	public 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();)
						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.");
		}
	}
}