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 AStar

NODE:

// 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 Node

STATE: (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 EightPuzzleState

And 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 class

Ok , ¡ 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

Well now I´m trying to do the estimate and successors classes with all possible cases, this is
for the successors we have


123 when the blank is in the position where the 1 OR 3 OR 7 OR 0 are in the example
456 the blank can be moved in 2 ways
780

I mean the first case is when the 6 is switched by 0

123
450
786

other case is this

123
456
708 when the blank is in the place of the seven etc...

there are 8 moves in total when the blank is in one of these cases 2 per case

Then exists the cases:

123 when the blank is in the position where the 2 OR 4 OR 6 OR 8 are in the example
456 the blank can be moved in 3 ways
780

for example

rst case is when the 0 is in the place of the 6

123 120 123
405 453 450
786 786 786

These means there are 12 cases , 3 per numeber case

And finally there are 4 cases for the unique middle tile

123 123 123 123 102 123
456 405 045 450 425 485
780 786 786 786 786 706

so we have 24 cases, so I think i will put them all.

Hi,

Do you have a specific question on how to code these algorithms in Java, or is this a game theory question where you have some algorithms but aren't sure how to use them to solve your puzzle/problem? In other words, in order to offer you help, do we need to research the Manhattan heuristic first and learn it or could someone who knows Java but not the Manhattan heuristic help you? You'll probably get more help if it is the latter case rather than the former.

Why not refer to http://8-puzzle.blogspot.com/

Implementation include various concepts in search techniques.

Sample program available for download and test at: AI 8-puzzle (8 Puzzle) solver

Quote from site:
The methods explored and implemented are: Blind Breath-First Search, h=Sum(step tiles from origin), h=Num. of Title not in place, Manhattan Distance Heuristic and A* Searching Algo (A Star Algorithm). Blind search is actually the worse algoritm in this scenario while the A* algorithm is the best. You may test it using this system by observing the time unit that the computer use, the exposed solutions and the solution steps obtained by different algo.

Hope this help :)

please i want the full code project solving 8 buzzle using depth and breadth first search ind if you can analyses and comparison between both algorithms
i hope as fast as you can

i dont find analyses and the main method for testing the code
and also no comparison

please forward me to any site that help if you can

Edited 7 Years Ago by peter_budo: n/a

please i want the full code project solving 8 buzzle using depth and breadth first search ind if you can analyses and comparison between both algorithms
i hope as fast as you can

Any other homework you need us to provide ASAP on your demand? Perhaps just post your instructor's email address so we can send it in directly?

Any other homework you need us to provide ASAP on your demand? Perhaps just post your instructor's email address so we can send it in directly?

Don't give him ideas. Once I saw someone here who actually did posted his teacher e-mail and asked us to send the code there!

@jehad golden rule of the forum is We only give homework help to those who show effort so you better to start showing something here

@javaAddict 2 or 3 times I was able to link up post with school assignments due to person directly copy & paste assignment and also because school had bad security measurements so google was able to index their supposedly private network

Edited 7 Years Ago by peter_budo: n/a

thank you very much but if you please i want to now how to write documntation for this project

hi
the follwoing errors appears after compilation
cannot find sympol variable ap
and in the main class
cannot find variable initnode
cannot find variable nodo .......etc

hi
the follwoing errors appears after compilation
cannot find sympol variable ap
and in the main class
cannot find variable initnode
cannot find variable nodo .......etc

Without code we cannot say much. But it is probably because you haven't declared those variables, or you declared them in a place where they cannot be seen by where you call them. Use the above suggestion first, see if the problem is solved and then post again.

Hi, did you finish the solution of this problem. I am wondering how to do the STATE part.Can you show the final solution if you finish it. Thank you.

This article has been dead for over six months. Start a new discussion instead.