Hi, well I need to do a program in Java that shows the solution of the famous game 8 puzzle
(the object of the game is to place the tiles in their place with the less possible movements)
So using the class Astar Given by our teacher we are asked to implement 3 more classes
Astar contains abstract methods, estimate() and successor().
estimate() must use the heuristic Manhattan, this is for a given node in the search tree, estimate() shall return an estimate of how far there is to the search goal
and
successor must implement a way to put in a node the next possible moves for an specific tile, this is successor() shall return a list of all possible successors of a specific state.
So I am doing a class NODE (the class Node is now completed) , a Class STATE
(not completed) and the main class EightPuzzle (not completed).
the class Node is a general data structure which is used to represent the nodes in the search tree , and Each node contains an object of the class State, so this object contains the specific data structure for the A* algorithm.
So we have an initial array like
{1, 3, 2, 4, 0, 7, 8, 6, 5 };
and a goal array
{ 1, 2, 3, 4, 5, 6, 7, 8, 0 }; where the '0' is the blank in the game
So my question is how to implement the heuristic manhattan
I am a little lost, if you could help me complete the part of the code, cause I am having big troubles
so the code is the following
ASTAR:
import java.util.Vector;
public abstract class AStar {
public Node initialnode; // Start node
public Node goalnode; // Desired goal node
public Node n; // Node retrieved from OPEN
public Node tempNode; // Temporary node
public Vector<Node> OPEN; // Vector with Node elements
public Vector<Node> CLOSED; //
public Vector<Node> M; //
private long startTime; // Timing variables
private long endTime; //
private int low; // Used when selecting a node to retrive from OPEN
private int lowIndex; //
private int number; // Temporary integer storage
public void solve() {
startTime = System.currentTimeMillis();
// Initializing the initial node
initialnode.f = initialnode.h = initialnode.estimate(goalnode);
initialnode.g = 0;
// Instantiating OPEN, CLOSED and M
OPEN = new Vector<Node>();
CLOSED = new Vector<Node>();
M = new Vector<Node>();
// Placing initial node on OPEN
OPEN.add(0, initialnode);
// After finishing the initial phase, we enter the main loop
// of the A* algorithm
while (true) {
// Check if OPEN is empty, exit if this is the case
if (OPEN.size() == 0) {
System.out.println("Failure to solve problem:");
System.out.println(" OPEN is empty, exiting...");
return;
}
// Locate next node to retrieve from OPEN, based on lowest heuristic
lowIndex = 0;
low = OPEN.elementAt(0).f; //low = ((Node)OPEN.elementAt(0)).f;
for (int i = 0; i < OPEN.size(); i++) {
number = OPEN.elementAt(i).f; //number = ((Node)OPEN.elementAt(i)).f;
if (number < low) {
lowIndex = i;
low = number;
}
}
// Move selected node from OPEN to n
n = OPEN.elementAt(lowIndex); //n = (Node) OPEN.elementAt(lowIndex);
OPEN.removeElement(n);
// Successful exit if n proves to be the goal node
if (n.equals(goalnode)) {
endTime = System.currentTimeMillis();
printStatistics(n);
return;
}
// Retrieve all possible successors of n
M = n.successors();
// Compute f-, g- and h-value for every remaining successor
for (int i = 0; i < M.size(); i++) {
Node s = M.elementAt(i); //Node s = ((Node)M.elementAt(i));
s.g = n.g + s.cost;
s.h = s.estimate(goalnode);
s.f = s.g + s.h;
}
// Establishing arcs from n to each member of M
for (int i = 0; i < M.size(); i++) {
tempNode = (Node)M.elementAt(i);
tempNode.ancestor = n;
}
// Augmenting OPEN with suitable nodes from M
for (int i = 0; i < M.size(); i++) {
// Determine if current node on M can be found on CLOSED
boolean onCLOSED = isOnVector(M.elementAt(i), CLOSED); //boolean onCLOSED = isOnVector((Node)M.elementAt(i), CLOSED);
// Insert node into OPEN if it's not already on CLOSED
if (!(onCLOSED))
OPEN.add(0, M.elementAt(i)); //OPEN.insertElementAt(M.elementAt(i), 0);
}
// Insert n into CLOSED
CLOSED.add(0, n); //CLOSED.insertElementAt(n, 0);
}
}
// Determines whether or not node n can be found on vector v
//
public boolean isOnVector(Node n, Vector v) {
for (int i = 0; i < v.size(); i++) {
if (n.equals(v.elementAt(i))) { //if (n.equals((Node)v.elementAt(i))) {
return true;
}
}
return false;
}
// Dumps final statistics to stdout
//
public void printStatistics(Node n) {
System.out.println("Cost of solution: " + n.f);
System.out.println("Number of CLOSED nodes: " + CLOSED.size());
System.out.println("Number of still OPEN nodes: " + OPEN.size());
System.out.println("Time (ms): " + (endTime - startTime));
System.out.println("\nSolution path:\n");
printTrail(n);
}
public void printTrail(Node n) {
if (n.ancestor != null) {
printTrail(n.ancestor);
System.out.println(n.toString());
}
else System.out.println(n.toString());
}
} // END class AStarNODE:
// This class defines a general node for use within the A*-algorithm.
// It relies on the existence of a specialized State class which
// should provide details on the particular problem to be solved.
//
// Note that class variables are kept public, and should thus be
// accessed directly and not through class methods.
import java.util.Vector;
public class Node {
public State state; // Contains state information
public int f; // Value of heuristic evaluation function (f = g + h)
public int g; // Accumulated cost
public int h; // Estimate of remaining cost
public int cost; // Cost of this particular node
public Node ancestor; // Reference to the node's immediate parent
// Constructor
public Node(State s, int cost) {
this.state = s;
this.cost = cost;
}
// Equality check; uses the equality check of the State class
public boolean equals(Node n) {
if (state.equals(n.state)) {
return true;
} else {
return false;
}
}
// Convert node to string
public String toString() {
return "State=" + state.toString() + ", f=" + f + ", g=" + g + ", h=" + h;
}
// Check for ancestors
public boolean hasAncestor() {
if (ancestor != null) {
return true;
} else {
return false;
}
}
// Successors
public Vector<Node> successors () {
Vector<Node> nodes = new Vector<Node>();
Vector<State> states = state.successors();
for (int i = 0; i < states.size(); i++) {
// Note: for a more general implementation, the uniform costs
// should be replace by an operator specific cost
nodes.add(0, new Node(states.elementAt(i), 1));
}
return nodes;
}
public int estimate(Node goalnode) {
return state.estimate(goalnode.state);
}
} // End class NodeSTATE: (this one is the incomplete class):
// State Class for EightPuzzle; extends State
//
// public Vector successors()
// public int estimate(State goal)
//
// Doi need an unary constructor?
//
import java.util.Vector;
public class State {
public int[] value; // object data repr.; should be of length 9
// constructor
public State(int[] v) {
value = v;
}
// equality check
public boolean equals(State state) {
State s = (State)state;
boolean flag = true;
for (int i = 0; i < 9; i++) if (value[i] != s.value[i]) flag = false;
return flag;
}
// to String conversion; for printing
public String toString() {
String s = "(";
for (int i = 0; i < 9; i++)
s = s + value[i] + ",";
return s + "\b)";
}
// successor states
public Vector successors() {
Vector m = new Vector();
// ***** ////////How to do this??????*****
/*
//
int dx = ap.dimx; ?????the direction???
int dy = ap.dimy;
int blank = EightPuzzle.blank; ?????????? error how to define the blank???
int i = 0;
for(int y = 0; y < dy; y++){
for(int x = 0; x < dx; x++){
if((y > 0) && (value[i- dx] == blank)) m.addElement(flip(i, i-dx));
if((y < dy-1) && (value[i+ dx] == blank)) m.addElement(flip(i, i+dx));
if((x > 0) && (value[i- 1] == blank)) m.addElement(flip(i, i- 1));
if((x < dx-1) && (value[i+ 1] == blank)) m.addElement(flip(i, i+ 1));
i++;
}
}
//
*/
return m;
}
// interface to estimate h
public int estimate(State goal) {
// ***** Here the Manhattan heuristic is implemented but how*****
return 0;
}
} // End class EightPuzzleStateAnd the main class
import java.util.Vector;
public class EightPuzzle extends AStar{
// constructor
public EightPuzzle(Node i, Node g) {
//
initnode = i;
goalnode = g;
}
//
// here I will put the initial arrays but is this the right way???
/*
// ???????and
//
int initarray[] = { 1, 2, 3, 4, 0, 8, 7, 6, 5 };
int goalarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
int blank = 4;
*/
public static void main(String[] args) {
/* State initsta = new State(initarray);
State goalsta = new State(goalarray);
Nodo in = new Node(estadoinicial, 0);
Nodo go = new Node(esmeta, 0);
EightPuzzle a = new EightPuzzle(in, go);
a.solve(); //this function is in AStar
is this ok ??
*/
}
//
} // END EightPuzzle classOk , ¡ know that for a piece in the "8-puzzle", the Manhattan-distance will be the length from the current position to the target position. Beacuse the pieces can not nove along the dialgonals, the distances will therefor be the sum of the horizontal and vertical positions.
like, the Manhattan-distance for a piece in upper left corner with target position in lower right corner will be 4.
Please help me to complete this code, I haven´t slept for 2 days , haha, well more less trying to get this done,
Any help will be apreciated.
Greetings
