Draw the recursion trace for the execution of method PuzzleSolve(3,S,U), from Code Fragment 5.11, where S is empty and U = {a,b,c,d}.

Transcribed Image Text:

Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U {e is now being used} if k == 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output {a solution} else PuzzleSolve(k – 1, S, U) {a recursive call} Remove e from the end of S Add e back to U {e is now considered as unused}