/** * 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); }