From c492158417199a42314eb34fe6198e33e5b46db4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Mon, 25 Mar 2013 22:40:31 +0100 Subject: Algorithms-I : 4-Puzzle: implement Solver --- Algorithms/Part-I/4-Puzzle/Solver.java | 168 +++++++++++++++++++++++++++++++-- 1 file 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 pq0; + private final MinPQ pq1; + private final RedBlackBST gameTree0; + private final RedBlackBST gameTree1; + + private class SearchNode implements Comparable + { + 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 { + 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(); + pq1 = new MinPQ(); + gameTree0 = new RedBlackBST(); + gameTree1 = new RedBlackBST(); + + 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 solution() { - return null; + if (!isSolvable()) return null; + + Stack s = new Stack(); + 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()); } } -- cgit v1.1-2-g2b99