Solutions w6

1 files changed, 31 insertions, 13 deletions

diff --git a/Week6/src/Solver.java b/Week6/src/Solver.java
index 137646c..9b78f27 100644
--- a/Week6/src/Solver.java
+++ b/Week6/src/Solver.java
@@ -1,37 +1,55 @@
+import java.util.HashSet;

+import java.util.PriorityQueue;

 import java.util.Queue;

 

-

 /**

  * A class that implements a breadth-first search algorithm

  * for finding the Configurations for which the isSolution predicate holds

+ * 

  * @author Pieter Koopman, Sjaak Smetsers

- * @version 1.3

- * @date 28-02-2013

+ * @author Camil Staps, s4498062

  */

+@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.

 public class Solver

 {

     // A queue for maintaining graphs that are not visited yet.

-    Queue<Configuration> toExamine;

+    private final Queue<Node<Configuration>> toExamine = new PriorityQueue<Node<Configuration>>();

+    private final HashSet<Configuration> examined = new HashSet<Configuration>();

+    

+    private Node winner = null;

 

     public Solver(Configuration g) {

-        throw new UnsupportedOperationException("Solver: not supported yet.");        

+        toExamine.add(new Node(null, g));

     }

     

     /* A skeleton implementation of the solver

      * @return a string representation of the solution

      */

-    public String solve () {

-        while (! toExamine.isEmpty() ) {

-            Configuration next = toExamine.remove();

-            if ( next.isSolution() ) {

-                return "Success!";

+    public boolean solve () {

+        while (!toExamine.isEmpty()) {

+            Node next = toExamine.remove();

+            Configuration nextConfiguration = (Configuration) next.getItem();

+            examined.add(nextConfiguration);

+            if (nextConfiguration.isSolution()) {

+                winner = next;

+                return true;

             } else {

-                for ( Configuration succ: next.successors() ) {

-                    toExamine.add  (succ);

+                for (Configuration succ: nextConfiguration.successors()) {

+                    if (!examined.contains(succ)) {

+                        toExamine.add(new Node(next, succ));

+                    }

                 }

             }

         }

-        return "Failure!";

+        return false;

+    }

+    

+    /**

+     * Return the winning Node (from which the path can be reconstructed)

+     * @return the node in which we found a solution

+     */

+    public Node getWinner() {

+        return winner;

     }

     

 }