Using Algorithm A * to solve 8 puzzles (Board data type works fine)
import java.util.Comparator;
public class Solver {
private SearchNode result;
// Helper search node class.
private class SearchNode {
SearchNode prev;
Board value;
int moves = 0;
int priority;
public SearchNode(Board board, SearchNode previous) {
super();
this.value = board;
prev = previous;
if (null != previous) {
this.moves = previous.moves + 1;
} else {
this.moves = 0;
}
// priority = this.value.hamming() + moves;
priority = this.value.manhattan() + moves;
}
}
/**
* Finds a solution to the initial board (using the A* algorithm).
* @param initial initial board.
*/
public Solver(Board initial) {
SearchNode root = new SearchNode(initial, null);
HeapMinPQ<SearchNode> heap = new HeapMinPQ<SearchNode>(new ManhattanOrder());
heap.insert(root);
Board twin = initial.twin();
SearchNode twinRoot = new SearchNode(twin, null);
HeapMinPQ<SearchNode> twinHeap = new HeapMinPQ<SearchNode>(new ManhattanOrder());
twinHeap.insert(twinRoot);
solve(heap, twinHeap);
}
private void solve(HeapMinPQ<SearchNode> heap, HeapMinPQ<SearchNode> twinHeap) {
while (!heap.isEmpty() && !twinHeap.isEmpty()) {
if (null != perform(heap)) {
return;
}
if (null != perform(twinHeap)) {
result = null;
return;
}
}
}
private SearchNode perform(HeapMinPQ<SearchNode> heap) {
SearchNode n = heap.delMin();
if (n.value.isGoal()) {
result = n;
return result;
}
for (Board board : n.value.neighbors()) {
SearchNode x = new SearchNode(board, n);
if (null != n.prev && n.prev.value.equals(board)) {
// don't add neighbors that are same as previous board
continue;
}
heap.insert(x);
}
return null;
}
And this is my "double" method from the board data type.
public Board twin(){
int dim = this.length;
int[][] copy = this.tiles;
if (this.length <= 1)
return new Board(copy);
// Find zero so that we don't exchange with the blank
// This looks like a O(dim^2) algorithm, but on average it should finish
// in O(1).
int row = 0;
int col = 0;
int value = 0;
int lastValue = tiles[0][0];
zerosearch: for (row = 0; row < dim; row++) {
for (col = 0; col < dim; col++) {
value = tiles[row][col];
// Check col>0 because swap must occur on same row
if (value != 0 && lastValue != 0 && col > 0)
break zerosearch;
lastValue = value;
}
}
copy[row][col] = lastValue;
copy[row][col - 1] = value;
return new Board(copy);
}
There has to be a deep miscalculation I'm doing here and I'm sure it starts with a solution (heap, twinHeap); method in the public method Solver (Board initial). Any help would be greatly appreciated.
source to share
here are some tricks to solve the 8 puzzle problem:
For class advice :
-
when implementing the Board class, it is better to use two integer variables (e.g. rowIndex, colIndex) to keep track of where the space is (number 0). Using the self-defined Position class can lead to an error when passing the memory test if you do it as an assignment from coursera.
-
To create a double board, please note that not to change the number with an empty tile, the number of which is 0. To create a randomized double, it is better to first create two random values from [0, n * n), then translate them into the row and column index.
-
When creating board neighbors, remember to update the position index of the empty tile.
For the Solver class :
-
it is recommended to use a new private inner class describing the node game. In this class we can record board, moves and previous node. and update the Hamming and Manhattan methods to be used in the priority queue to break the expected node.
-
To avoid going into a long loop, check to see if it is already in the queue before inserting a node into the priority queue.
-
Here are some helpful explanations and suggestions from coursera: http://coursera.cs.princeton.edu/algs4/checklists/8puzzle.html
-
My code is here: My 8 Puzzle Code Not Time Optimized for Solver.
source to share