Draw the recursion trace for the execution of the method PuzzleSolve(3, S, U)

Question:

Draw the recursion trace for the execution of the method PuzzleSolve(3, S, U) (Code Fragment 5.11), where S is empty and U = {a,b,c,d}. (Page 221 of the book mentioned below – R-5.6) Here is code Fragment 5.11 (page 213) from Goodrich, Michael T., Roberto Tamassia, Michael Goldwasser. Data Structures and Algorithms in Java, 6th Edition 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 if k == 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output else PuzzleSolve(k ? 1, S, U ) Remove e from the end of S Add e back to U

Answer:

PuzzleSolver.java


import java.util.Iterator;
import java.util.LinkedHashSet;

public class PuzzleSolver {
    private static class QueueSet<T> extends LinkedHashSet<T> {
        private static final long serialVersionUID = 7965261432562813003L;

        public boolean offer(T element) {
            return super.add(element);
        }
      
        public T poll() {
            Iterator<T> it = iterator();
            if (it.hasNext()) {
                T first = it.next();
                it.remove();
                return first;
            } else {
                return null;
            }
        }
    }

    public static void main(String[] args) {
        QueueSet<Character> qs = new QueueSet<>();
        qs.offer('a');
        qs.offer('b');
        qs.offer('c');
        qs.offer('e');
      
        puzzleSolve(3, "", qs);
    }


    private static void puzzleSolve(int k, String s, QueueSet<Character> u) {
        for (int i = 0; i < u.size(); i++) {
            // Remove e from u
            Character element = u.poll();
          
            // Add e to the end of s
            s = s + element;
          
            if (k == 1) {
                // Test whether s is a configuration that solves the puzzle
                // if s solves the puzzle then add s to output
                System.out.println(s);
            } else {
                puzzleSolve(k - 1, s, u);
            }
          
            // Remove e from the end of s
            s = s.substring(0, s.length() - 1);
          
            // Add e back to U
            u.offer(element);
        }
    }
  
}

Leave a Comment

Your email address will not be published. Required fields are marked *