Chapter 5, Problem 6R

Recursion trace for execution of “PuzzleSolve(3, S, U)” method:

The PuzzleSolve() method is,

• This method takes the input parameters of integer “k”, Sequence “S”, and set “U”.
• The for loop executes until the “U” set.
  • Add the element from Set “U” to end of sequence “S”.
  • Delete the element from the set “U”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and check “S” solves the puzzle. If yes, display the output as “S”.
  • Otherwise, call the PuzzleSolve() method recursively by passing the parameters of “k-1”, “S”, and “U”.
• Delete the element from the end of sequence “S”.
• Add the element to Set “U”.

Explanation:

Let us consider the input for integer “k = 3”, Sequence “S = ()”, and set “U ={a, b, c, d}”.

Call the PuzzleSolve(3, (), {a, b, c, d}) method is,

The representation of recursion call for PuzzleSolve(3, (), {a, b, c, d})   is shown below:

• This method takes the input parameters of integer “3”, Sequence “()”, and set “{a, b, c, d}”.
• The for loop executes until the “{a, b, c, d}” set.
  • Add the “a” element from Set “{a, b, c, d}” to end of sequence “S”.
  • Delete the “a” element from the set “{b, c, d}”.
  • Check whether the integer “k” is equal to “1”. If no, so executes the else statement.
  • Call the PuzzleSolve() method by passing the parameters of “3-1=2”, “a”, and “{b, c, d}”.

Call the PuzzleSolve(2, a, {b, c, d}) method is,

The representation of recursion call for PuzzleSolve(2, a, {b, c, d})   is shown below:

• This method takes the input parameters of integer “2”, Sequence “a”, and set “{b, c, d}”.
• The for loop executes until the “{b, c, d}” set.
  • Add the “b” element from Set “{b, c, d}” to end of sequence “a”.
  • Delete the “b” element from the set “{c, d}”.
  • Check whether the integer “k” is equal to “1”. If no, so executes the else statement.
  • Call the PuzzleSolve() method by passing the parameters of “2-1=1”, “ab”, and “{c, d}”.
• Call the PuzzleSolve(1, ab, {c, d}) method is,

The representation of recursion call for PuzzleSolve(1, ab, {c, d})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “ab”, and set “{c, d}”.
• The for loop executes until the “{c, d}” set.
  • Add the “c” element from Set “{c, d}” to end of sequence “ab”.
  • Delete the “c” element from the set “{d}”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and display the output as “S” as “abcd”.
• Call the PuzzleSolve(1, ac, {b, d}) method is,

The representation of recursion call for PuzzleSolve(1, ac, {b, d})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “ac”, and set “{b, d}”.
• The for loop executes until the “{b, d}” set.
  • Add the “b” element from Set “{b, d}” to end of sequence “ac”.
  • Delete the “b” element from the set “{d}”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and display the output as “S” as “acbd”.
• Call the PuzzleSolve(1, ad, {b, c}) method is,

The representation of recursion call for PuzzleSolve(1, ad, {b, c})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “ad”, and set “{b, c}”.
• The for loop executes until the “{b, c}” set.
  • Add the “b” element from Set “{b, c}” to end of sequence “ad”.
  • Delete the “b” element from the set “{c}”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and display the output as “S” as “adbc”.
• Delete the “b” element from the end of sequence “S”.
• Add the “b” element to Set “{b, c, d}”.

Call the PuzzleSolve(3, (), {a, b, c, d}) method is,

• This method takes the input parameters of integer “3”, Sequence “()”, and set “{a, b, c, d}”.
• The for loop executes until the “{a, b, c, d}” set.
  • Add the “b” element from Set “{a, b, c, d}” to end of sequence “S”.
  • Delete the “b” element from the set “{a, c, d}”.
  • Check whether the integer “k” is equal to “1”. If no, so executes the else statement.
  • Call the PuzzleSolve() method by passing the parameters of “3-1=2”, “b”, and “{a, c, d}”.

Call the PuzzleSolve(2, b, {a, c, d}) method is,

The representation of recursion call for PuzzleSolve(2, b, {a, c, d})   is shown below:

• This method takes the input parameters of integer “2”, Sequence “b”, and set “{a, c, d}”.
• The for loop executes until the “{a, c, d}” set.
  • Add the “a” element from Set “{a, c, d}” to end of sequence “b”.
  • Delete the “a” element from the set “{c, d}”.
  • Check whether the integer “k” is equal to “1”. If no, so executes the else statement.
  • Call the PuzzleSolve() method by passing the parameters of “2-1=1”, “ba”, and “{c, d}”.
• Call the PuzzleSolve(1, ba, {c, d}) method is,

The representation of recursion call for PuzzleSolve(1, ba, {c, d})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “ba”, and set “{c, d}”.
• The for loop executes until the “{c, d}” set.
  • Add the “c” element from Set “{c, d}” to end of sequence “ba”.
  • Delete the “c” element from the set “{d}”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and display the output as “S” as “bacd”.
• Call the PuzzleSolve(1, bc, {a, d}) method is,

The representation of recursion call for PuzzleSolve(1, bc, {a, d})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “bc”, and set “{a, d}”.
• The for loop executes until the “{a, d}” set.
  • Add the “a” element from Set “{a, d}” to end of sequence “ac”.
  • Delete the “a” element from the set “{d}”.
  • Check whether the integer “k” is equal to “1”. If yes,
    • Test the puzzle and display the output as “S” as “bcad”.
• Call the PuzzleSolve(1, bd, {a, c}) method is,

The representation of recursion call for PuzzleSolve(1, bd, {a, c})   is shown below:

• This method takes the input parameters of integer “1”, Sequence “bd”, and set “{a, c}”.
• The for loop executes until the “{a, c}” set...