Algorithms-I : 4-Puzzle: implement Solver

1 files changed, 162 insertions, 6 deletions

diff --git a/Algorithms/Part-I/4-Puzzle/Solver.java b/Algorithms/Part-I/4-Puzzle/Solver.java
index 1f96098..8f14ac5 100644
--- a/Algorithms/Part-I/4-Puzzle/Solver.java
+++ b/Algorithms/Part-I/4-Puzzle/Solver.java
@@ -1,34 +1,189 @@
 /* vim: set expandtab tabstop=4 shiftwidth=4 : */
 
-public class Solver {
+import java.util.Iterator;
+// import java.util.Collection;
+// import java.util.ArrayDeque;
+
+public class Solver
+{
+    private SearchNode sol0;
+    private SearchNode sol1;
+    private final MinPQ<SearchNode> pq0;
+    private final MinPQ<SearchNode> pq1;
+    private final RedBlackBST<String, Board> gameTree0;
+    private final RedBlackBST<String, Board> gameTree1;
+
+    private class SearchNode implements Comparable<SearchNode>
+    {
+        private final int moves;
+        private final int fitness;
+        private final SearchNode parent;
+        private final Board board;
+        private final String key;
+
+        public SearchNode(Board b, SearchNode p, int n)
+        {
+            this.board = b;
+            this.parent = p;
+            this.moves = n;
+            // this.fitness = n + b.hamming();
+            this.fitness = n + b.manhattan();
+            this.key = b.toString().replace(" ", "").replace("\n", "");
+        }
+
+        public String getKey()   { return key; }
+        public int getFitness()   { return fitness; }
+        public int getMoves()   { return moves; }
+        public Board getBoard() { return board; }
+        public SearchNode getParent() { return parent; }
+
+        public int compareTo(SearchNode that)
+        {
+            if (this == that) return 0;
+            if (this.fitness > that.fitness) return 1;
+            else if (this.fitness < that.fitness) return -1;
+            else return 0;
+        }
+    }
+
+    private class SearchNodeIterator implements Iterator<SearchNode> {
+        private SearchNode current;
+        public SearchNodeIterator(SearchNode n) {
+            current = n;
+        }
+        public boolean hasNext()    { return current.getParent() != null; }
+        public void remove() { throw new UnsupportedOperationException();  }
+        public SearchNode next() {
+            if (!hasNext()) throw new java.util.NoSuchElementException();
+            return current.getParent();
+        }
+    }
 
     // find a solution to the initial board (using the A* algorithm)
     public Solver(Board initial)
     {
-        // use MinPQ
+        sol0 = null;
+        sol1 = null;
+        pq0 = new MinPQ<SearchNode>();
+        pq1 = new MinPQ<SearchNode>();
+        gameTree0 = new RedBlackBST<String, Board>();
+        gameTree1 = new RedBlackBST<String, Board>();
+
+        pq0.insert(new SearchNode(initial, null, 0));
+        pq1.insert(new SearchNode(initial.twin(), null, 0));
+
+        solve();
+    }
+
+    private boolean isKnown(SearchNode n, Board b)
+    {
+        SearchNode p = n.getParent();
+        while (p != null)
+        {
+            if (b.equals(p.getBoard())) return true;
+            p = p.getParent();
+        }
+        return false;
+    }
+
+    private void solve()
+    {
+        while ((sol0 == null) && (sol1 == null))
+        {
+            if (pq0.isEmpty() && pq1.isEmpty())
+            {
+                // StdOut.println("FAIL");
+                break;
+            }
+            if (!pq0.isEmpty())
+            {
+                SearchNode n = pq0.delMin();
+                Board b = n.getBoard();
+                if (b.isGoal())
+                {
+                    sol0 = n;
+                    break;
+                }
+                if (gameTree0.contains(n.getKey()))
+                    continue;
+                int m = n.getMoves() + 1;
+                SearchNode p = n.getParent();
+                if (p == null) {
+                    for (Board nb : b.neighbors())
+                        pq0.insert(new SearchNode(nb, n, m));
+                }
+                else {
+                    Board pb = p.getBoard();
+                    for (Board nb : b.neighbors())
+                    {
+                        if (!pb.equals(nb))
+                            pq0.insert(new SearchNode(nb, n, m));
+                    }
+                }
+                gameTree0.put(n.getKey(), b);
+            }
+            if (!pq1.isEmpty())
+            {
+                SearchNode n = pq1.delMin();
+                Board b = n.getBoard();
+                if (b.isGoal())
+                {
+                    sol1 = n;
+                    break;
+                }
+                if (gameTree1.contains(n.getKey()))
+                    continue;
+                int m = n.getMoves() + 1;
+                SearchNode p = n.getParent();
+                if (p == null) {
+                    for (Board nb : b.neighbors())
+                        pq1.insert(new SearchNode(nb, n, m));
+                }
+                else {
+                    Board pb = p.getBoard();
+                    for (Board nb : b.neighbors())
+                    {
+                        if (!pb.equals(nb))
+                            pq1.insert(new SearchNode(nb, n, m));
+                    }
+                }
+                gameTree1.put(n.getKey(), b);
+            }
+        }
     }
 
     // is the initial board solvable?
     public boolean isSolvable()
     {
-        return false;
+        return (sol0 != null);
     }
 
     // min number of moves to solve initial board; -1 if no solution
     public int moves()
     {
-        return 0;
+        if (!isSolvable()) return -1;
+        return sol0.getMoves();
     }
 
     // sequence of boards in a shortest solution; null if no solution
     public Iterable<Board> solution()
     {
-        return null;
+        if (!isSolvable()) return null;
+
+        Stack<Board> s = new Stack<Board>();
+        SearchNode n = sol0;
+        while (n != null)
+        {
+            s.push(n.getBoard());
+            n = n.getParent();
+        }
+        return s;
     }
 
     // solve a slider puzzle (given below)
     public static void main(String[] args)
     {
+        // Stopwatch w = new Stopwatch();
         // create initial board from file
         In in = new In(args[0]);
         int N = in.readInt();
@@ -45,9 +200,10 @@ public class Solver {
         if (!solver.isSolvable())
             StdOut.println("No solution possible");
         else {
-            StdOut.println("Minimum number of moves = " + solver.moves());
+            StdOut.println("Minimum number of moves = " + solver.moves()+"\n");
             for (Board board : solver.solution())
                 StdOut.println(board);
         }
+        // StdOut.printf("Time: %f\n\n", w.elapsedTime());
     }
 }