Tim Korb's Home Page

/**
 * Implement a backtracking interface, based on example in Chapter 8 of Programming Challenges, by Skiena and Revilla.
 * 
 * This is an abstract class.  To use it, extend it and complete the three abstract methods below.  Create an instance of the class
 * and invoke the backtrack method to begin the search.
 * 
 * @author Tim Korb (jtk@purdue.edu)
 * @version October 2011
 * 
 * @todo Review this documentation in light of http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html.
 */

abstract public class Backtracker {
    int maxCandidates;
    
    /*
     * Constructor is used to create an instance of the backtracking class, giving the maximum number of candidates that
     * will be created at each step.
     * 
     * @param maxCandidates	maximum number of candidates to add to the solution vector at each step
     */
    Backtracker(int maxCandidates) {
	this.maxCandidates = maxCandidates;
    }
    
    /**
     * Process solution array a with k values filled in so far, recurse if no solution yet.
     * 
     * @param a the array to be filled with a solution to the problem
     * @param k the current step in the solution, moves from 0 to a.length-1
     * @return true, if done processing; false, to search for more solutions
     */
    boolean backtrack(int[] a, int k) {
	if (isSolution(a, k))
	    return processSolution(a, k);
	else {
            int[] candidates = new int[maxCandidates];
	    int nCandidates = constructCandidates(a, k, candidates);
	    for (int i = 0; i < nCandidates; i++) {
		a[k] = candidates[i];
		if (backtrack(a, k + 1))
		    return true;
	    }
	    return false;
	}
    }

    /**
     * Check to see if a[0..k-1] represents a solution to the problem.
     * 
     * @param a the array to be filled with a solution to the problem
     * @param k the current step in the solution, moves from 0 to a.length-1
     * @return true, if a contains a solution
     */
    abstract boolean isSolution(int a[], int k);

    /**
     * Process the solution given by a[0..k-1].  In most cases, k == a.length at this point.
     * 
     * @param a the array to be filled with a solution to the problem
     * @param k the current step in the solution, moves from 0 to a.length-1
     * @return true, if processing should continue, searching for more solutions
     */
    abstract boolean processSolution(int[] a, int k);

    /**
     * Construct a set of candidates solutions for step k in the problem.  The solution array, a, has
     * been filled a[0..k-1]. 

     * @param a the array to be filled with a solution to the problem
     * @param k the current step in the solution, moves from 0 to a.length-1
     * @return the number of candidate solutions to try (0 -> no candidates)
     */
    abstract int constructCandidates(int[] a, int k, int[] c);
}