Algorithms for Backtracking ~~~~~~~~~~~~~~~~~~~~~~~~~~~ A PARTIAL SOLUTION is a possibly empty sequence of moves (e.g., knight's moves in the Knight's Path Problem or assignments of items to bins in the Bin-Packing Problem). A COMPLETE SOLUTION is a partial solution that satisfies some additional property (e.g., visits every square exactly once or assigns every item to some bin). Backtracking to Find Some Solution ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Try to extend the partial solution S to a complete solution. If successful, // return with STATUS = SUCCESS and COMPLETE = the complete solution found; // otherwise return with STATUS = FAILURE and COMPLETE = S. On the initial // call, S is the EMPTY sequence of moves and the values of STATUS and COMPLETE // returned include a complete solution or an indication that there is none. [status, complete] = backtrack (S) if S is a complete solution return [SUCCESS, S] Generate a list L of possible next moves Apply heuristics to prune L by eliminating moves that cannot lead to a complete solution Apply heuristics to sort L to increase the likelihood of early success For each possible next move M in L (in sorted order) Add M to S giving the augmented partial solution S' [status, complete] = backtrack (S') If status == SUCCESS Return [SUCCESS, complete] Return [FAILURE, S] Backtracking to Find a Minimal Solution ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Find a minimal complete solution assuming the VALUATION FUNCTION VALUE() // does not decrease when a move is added to a partial solution. S is a // partial solution; SBESTSOFAR is the best complete solution found earlier; // VBESTSOFAR = VALUE(SBESTSOFAR); and LOWERBOUND is some lower bound on the // minimum value. Returns with SBEST = SBESTSOFAR or a best complete solution // that extends S, whichever has a smaller valuation; and VBEST = VALUE(SBEST). // On the initial call, S is the EMPTY sequence of moves; VBESTSOFAR is some // UPPER BOUND on the minimum value; and SBESTSOFAR is anything. [vBest, sBest] = backtrack (S, vBestSoFar, sBestSoFar, lowerBound) if S is a complete solution if value(S) < vBestSoFar return [value(S), S] else return [vBestSoFar, sBestSoFar] Generate a list L of possible next moves Apply heuristics to prune L by eliminating moves that cannot lead to a better solution than sBestSoFar Apply heuristics to sort L to increase the likelihood of early success For each possible next move M in L (in sorted order) Add M to S giving the augmented partial solution S' if value(S') < vBestSoFar [vBestSoFar, sBestSoFar] = backtrack (S', vBestSoFar, sBestSoFar) if vBestSoFar == lowerBound return [vBestSoFar, sBestSoFar] Return [vBestSoFar, sBestSoFar] CS-223-01/23/20