001package algs13.xbacktrack.xframework; 002 003import algs13.Stack; 004import stdlib.StdOut; 005 006/** 007 * The driver for the backtracking framework. In order to run the driver, 008 * this class must be instantiated and the solve method on the instance of this 009 * class must be called. 010 * 011 * Find the TODOs in this file and implement them. There are also TODOs in 012 * xbacktrack.xsudoku.MySudoku (MySudoku.java) for you to complete. 013 * 014 * This framework is adapted from Timothy Budd: Classic Data Structures in C++, 015 * Addison-Wesley, 1994. The design is modernized to use object composition 016 * rather than inheritance. It can be used to model any kind of backtracking 017 * problem. 018 * 019 * @param <T> The type of the choices made in the backtracking problem. 020 */ 021public final class MyBacktrackDriver<T> { 022 023 // A reference to the problem instance 024 private final XBacktrackProblem<T> problem; 025 026 // The stack used to track the choices we attempt in solving 027 // the problem. If the framework solves the problem, the 028 // stack will contain the choices that were made in the search 029 // for a solution. 030 private final Stack<T> theStack = new Stack<>(); 031 032 // A counter to track how many times we backtrack. 033 private long backtrackCount; 034 035 // A boolean indicating whether the backtracking problem is solved. 036 // The setDone() method will set this flag to true. 037 private boolean done = false; 038 039 // Constructor for the driver, which orchestrates finding a solution 040 // for the problem given. 041 public MyBacktrackDriver(XBacktrackProblem<T> problem) { 042 if(problem == null) throw new IllegalArgumentException("Backtracking problem must not be null"); 043 backtrackCount = 0; 044 this.problem = problem; 045 } 046 047 // Set the done flag to true. This signals to the run method that it stop 048 // the backtracking loop. 049 public void setDone() { 050 this.done = true; 051 } 052 053 // Track a choice made representing a search area. 054 public void track(T choice) { 055 if(choice == null) throw new IllegalArgumentException("Cannot track a null choice"); 056 057 // TODO: Track the choice in the stack. 058 } 059 060 // Backtrack - throw away the most recent choice and back up to a previous choice to 061 // see if a different choice can be made in order to make progress. 062 private void backtrack() { 063 backtrackCount++; 064 065 // TODO: Backtrack: throw away the most recent choice and go back to the immediate 066 // previous choice we made to see if we can make a different choice. 067 } 068 069 // TODO: Implement this method. 070 private void run() { 071 // Run the main backtracking loop. You will need to create a loop. 072 073 // Until the done flag is flipped to true: 074 075 // If there is no way we can build on the most recent choice we made (i.e. the 076 // element that is at the top of the stack), stop and return. 077 078 // If there is a choice at the top of the stack, see if we can make progress after 079 // having made that choice. As we are checking, we need to look at it, not remove 080 // it from the stack, and pass it to the advance method on the backtracking problem. 081 082 // If we can advance, keep going, unless the problem implementation 083 // flipped the done flag to true. If we cannot advance, we must call driver.backtrack(); 084 } 085 086 /** 087 * A method to solve the problem. 088 * @return a result representing the solution 089 */ 090 public XBacktrackResult solve() { 091 problem.initialize(this); 092 run(); 093 094 StdOut.format("Backtracked %,d times\n", backtrackCount); 095 if(!done || theStack.isEmpty()) return new XBacktrackFailure(); 096 097 // Reverse the order of the choices from the stack. 098 Stack<T> s = new Stack<>(); 099 while(!theStack.isEmpty()) { 100 s.push(theStack.pop()); 101 } 102 103 return new XBacktrackSuccess<>(s); 104 } 105}