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