   A-star AI 8-Puzzle
  Here is my source code in java.   I need to devise a AI for automatically solving any given state. Any help would be much appreciated. I am lost for this part of my project. The goal state is like this1 2 38 0 47 6 5 where 0 is the blankpackage puzzle;import framework.*;import java.util.*;/**This class is respnsible for representing the internal details of a bridge state, displaying bridge state to output, and checking for state equality.*/public class puzzleState implements State{  /***private String array for tile numbers.*/private int [] tileNums; /*** Creates a new puzzle state* @param tileNums is a string*/public puzzleState(int[] tileNumsIn){   tileNums = tileNumsIn;}/** *  This method displays the outputs.*/public void display(){}/**Tests for equality between this state and the argument stateTwo states are equals if all the same people are on the same sides.@param state the state to test against this state@return wheather the states are equal*/public boolean equals(State state){  puzzleState aState = (puzzleState) state;  if (getArray() == aState.getArray()) return true;  else return false;} public int[] getArray() {  return tileNums;   }   /**    *Accessor for array index of the blank position    *@return int blank    */   public int getBlank() {  int[] copy = getArray();  int blank=-1;  int i=0;  while (i <= 8) { if (copy == 0) { blank=i; }  i++;  }  return blank;   }}package puzzle;import framework.*;import java.util.*;/**This class is responsible for performing the legal moves that can bedone on states in the puzzle problem*/public class puzzleMove extends Move{/**@param BLOCKUP moves the blank block up@param BLOCKDOWN moves the blank block down@param BLOCKRIGHT moves the blank block right@param BLOCKLEFT moves the blank block left*/public static final String ML = "ml";public static final String MD = "md";public static final String MR = "mr";public static final String MU = "mu";   public static final String randM = "rand";   private static final int SECOND = 1;   private static final int Zero = 0;   //private String moveName;/**Creates a puzzle Move.@param moveName a user command@precondition moveName must be one of the listed commands*/public puzzleMove(String moveName){   super(moveName);}   /*Accessor for puzzle Move name@return the name of this movepublic String getMoveName(){   return moveName;}*/   /***   This method moves the zero up.*/public puzzleState moveUp(puzzleState stateIn){int blankPos = stateIn.getBlank(); //locate zero with incoming state  if (blankPos == 0 || blankPos == 1 || blankPos == 2) { //JOptionPane.showMessageDialog(null,"Invalid State"); return null;  }  else { int[] temp = stateIn.getArray(); //get the array int temp2 = temp[blankPos-3]; //store dest in temp temp[blankPos-3]=Zero; //move blank into dest temp[blankPos]=temp2; //move temp into blank puzzleState newState = new puzzleState(temp); return newState;  }  }/** *   This method moves the zero down.*/public puzzleState moveDown(puzzleState stateIn){int blankPos = stateIn.getBlank(); //locate zero with incoming state  if (blankPos == 6 || blankPos == 7 || blankPos == 8) { //JOptionPane.showMessageDialog(null,"Invalid State"); return null;  }  else { int[] temp = stateIn.getArray(); //get the array int temp2 = temp[blankPos+3]; //store dest in temp temp[blankPos+3]=Zero; //move blank into dest temp[blankPos]=temp2; //move temp into blank puzzleState newState = new puzzleState(temp); return newState;  }  }/** *  This method moves the zero left.*/public puzzleState moveLeft(puzzleState stateIn){int blankPos = stateIn.getBlank(); //locate zero with incoming state  if (blankPos == 0 || blankPos == 3 || blankPos == 6) { //JOptionPane.showMessageDialog(null,"Invalid State"); return null;  }  else { int[] temp = stateIn.getArray(); //get the array int temp2 = temp[blankPos-1]; //store dest in temp temp[blankPos-1]=Zero; //move blank into dest temp[blankPos]=temp2; //move temp into blank puzzleState newState = new puzzleState(temp); return newState;  }  } /**    *this method is responsible for randomizing the problem in any possible state    *    */  private int[] randomizeInitialState() {  puzzleState randState;  int[] victim = {1,2,3,4,5,6,7,8,0}; //the victim to be randomized  Random rand = new Random();  int max = 8;  int victim2=0;  for (int i=0; i<= max; i++) { victim2=rand.nextInt(max+1);  //System.out.println(victim2); if (i==0) victim=victim2; else if (contains(victim, i, victim2)==true) i--; else if (contains(victim, i, victim2)==false)victim=victim2;   }    return victim;   }   private boolean contains(int[] victim, int size, int element) {   int counter=0; boolean flag=false; while (counter <= size) {  if (victim[counter] == element) { flag = true; //System.out.println("collsion:"+element);  }  counter++;   }   return flag;    }   public puzzleState randomize() {   System.out.println("Randomize:");   int[] victim = randomizeInitialState();   puzzleState victim2 = new puzzleState(victim);   return victim2;    }   /** *  This method moves the zero right.*/public puzzleState moveRight(puzzleState stateIn){int blankPos = stateIn.getBlank(); //locate zero with incoming state  if (blankPos == 2 || blankPos == 5 || blankPos == 8) { //JOptionPane.showMessageDialog(null,"Invalid State"); return null;  }  else { int[] temp = stateIn.getArray(); //get the array int temp2 = temp[blankPos+1]; //store dest in temp temp[blankPos+1]=Zero; //move blank into dest temp[blankPos]=temp2; //move temp into blank puzzleState newState = new puzzleState(temp); return newState;  }  } /**Performs a puzzle move on the given puzzle state.@param state and exisiting puzzle state.@return a new state resulting from the move*/   public puzzleState doMove(State state) {  puzzleState finalState;puzzleState state1 = (puzzleState) state;state = (puzzleState) state;finalState = TestMove(state1);return finalState; }  private puzzleState TestMove(puzzleState testState){puzzleState newState = testState;   char ch = getMoveName().charAt(SECOND);   switch(ch) {case 'l':  newState = moveLeft(testState);  break;case 'r':  newState = moveRight(testState);   break;case 'u':    newState = moveUp(testState);    break;case 'd':   newState = moveDown(testState);    break;case 'a':  newState = randomize();  break;default:    System.out.println("Error in Switch Statement.");    newState = null;    // ****** MAYBE NOT newState = NULL }//end switch   return newState;    }//end TestMove}package puzzle;import framework.*;import java.util.*;/**   This class keeps track of the current state of the puzzle problem,   collects the legal bridge moves, attempts to transform the current state   given a user command, and checks for problem success.*/public class puzzleProblem extends Problem{/**   begin holds the intial puzzleState*/   private static puzzleState begin; private int heur;/**   moves holds the list of moves availbile*/   private static ArrayList moves;/**   Creates a new puzzle problem   @param init The initial puzzle State   @param moves The list of legal puzzle Moves*/   public puzzleProblem (/*puzzleState init, ArrayList moveList, String intro*/){  super(init, new ArrayList(Arrays.asList(moveList)), intro);  begin = (puzzleState) init;}/**    Tests for whether the current state of the problem represent success    @return true if the user gets 1 through 8 around the edge of the grid*/public boolean success(State state){begin = (puzzleState) state; //super.getCurState();int[] temp = begin.getArray();    if(temp[0]==1 && temp[1]==2 && temp[2]==3 && temp[3]==8 && temp[4]==0 && temp[5]==4 && temp[6]==7 && temp[7]==6 && temp[8]==5 ){return true;    }//end if    else{ return false;    }//end else   }/**    *Accessor for the current state    *@return puzzleState*/    public puzzleState getCurState() {begin = (puzzleState)super.getCurState();return begin;}    /*** Computes the heuristic value for a given state.* This is using A* search.* @param state a state to compute the heuristic for* @return the heuristic value*/    public int computeHeuristic(State state)    { int md = 0;   begin = (puzzleState) state;   int[] temp = begin.getArray();   /**    *Calculating the number of moves the corresponding    *number is away from the goal state.    *Checking the first position.    **/   if (temp[0] == 1)  md += 0;   else if (temp[0] == 2) md += 1;   else if (temp[0] == 3) md += 2;   else if (temp[0] == 4) md += 3;   else if (temp[0] == 5) md += 4;   else if (temp[0] == 6) md += 3;   else if (temp[0] == 7) md += 2;   else if (temp[0] == 8) md += 1;   /**    *Checking the second position    */   if(temp[1] == 1)  md += 1;   else if(temp[1] == 2)  md += 0;   else if(temp[1] == 3)  md += 1;   else if(temp[1] == 4)  md += 2;   else if(temp[1] == 5)  md += 3;   else if(temp[1] == 6)  md += 2;   else if(temp[1] == 7)  md += 3;   else if(temp[1] == 8)  md += 2;   /**    *Checking the third position.    */   if(temp[2] == 1)  md += 2;   else if(temp[2] == 2)  md += 1;   else if(temp[2] == 3)  md += 0;   else if(temp[2] == 4)  md += 1;   else if(temp[2] == 5)  md += 2;   else if(temp[2] == 6)  md += 3;   else if(temp[2] == 7)  md += 4;   else if(temp[2] == 8)  md += 3;   /**    *Checking the third position    */   if(temp[3] == 1)  md += 1;   else if(temp[3] == 2)  md += 2;   else if(temp[3] == 3)  md += 3;   else if(temp[3] == 4)  md += 2;   else if(temp[3] == 5)  md += 3;   else if(temp[3] == 6)  md += 2;   else if(temp[3] == 7)  md += 1;   else if(temp[3] == 8)  md += 0;   /**    *Checking the fourth position.    */   if(temp[4] == 1)  md += 2;   else if(temp[4] == 2)  md += 1;   else if(temp[4] == 3)  md += 2;   else if(temp[4] == 4)  md += 1;   else if(temp[4] == 5)  md += 2;   else if(temp[4] == 6)  md += 1;   else if(temp[4] == 7)  md += 2;   else if(temp[4] == 8)  md += 1;   /**    *Checking the fifth position.    */   if (temp[5] == 1) md += 3;   else if (temp[5] == 2) md += 2;   else if (temp[5] == 3) md += 1;   else if (temp[5] == 4)  md += 0;   else if (temp[5] == 5) md += 1;   else if (temp[5] == 6) md += 2;   else if (temp[5] == 7) md += 3;   else if (temp[5] == 8) md += 2;   /**    *Checking the sixth position.    */   if (temp[6] == 1) md += 2;   else if (temp[6] == 2) md += 3;   else if (temp[6] == 3) md += 4;   else if (temp[6] == 4) md += 3;   else if (temp[6] == 5) md += 2;   else if (temp[6] == 6) md += 1;   else if (temp[6] == 7) md += 0;   else if (temp[6] == 8) md += 1;   /**    *Checking the seventh position.    */   if (temp[7] == 1) md += 3;   else if (temp[7] == 2) md += 2;   else if (temp[7] == 3) md += 3;   else if (temp[7] == 4) md += 2;   else if (temp[7] == 5) md += 1;   else if (temp[7] == 6) md += 0;   else if (temp[7] == 7) md += 1;   else if (temp[7] == 8) md += 2;   /**    *Checking the eighth position.    */   if (temp[8] == 1) md += 4;   else if (temp[8] == 2) md += 3;   else if (temp[8] == 3) md += 2;   else if (temp[8] == 4) md += 1;   else if (temp[8] == 5) md += 0;   else if (temp[8] == 6) md += 1;   else if (temp[8] == 7) md += 2;   else if (temp[8] == 8)   {  md += 3; }   heur = md;   return md;    }    public String getIntroduction() {  return intro; }    public int getHeur() {   return heur;    }   /**    *array for list of legal moves    */   private static puzzleMove[] moveList =  {new puzzleMove(puzzleMove.ML),new puzzleMove(puzzleMove.MR),new puzzleMove(puzzleMove.MU),new puzzleMove(puzzleMove.MD), new puzzleMove(puzzleMove.randM)};   /**    *a basic initial state to start the game with    */   private static int[] puzzleInit = {2,4,5,1,3,7,6,8,0};//==randomizeState   //private static int[] puzzleInit = randomizeInitialState();   /**    *private var State init is the initial state and will be provided by either the basic example or the randomize function    */   private static State init = new puzzleState(puzzleInit); private static String intro = "Welcome to the 8 Puzzle!\n\nMove the blank tile to get the following configuration:\n\n1\t2\t3\n8\t \t4\n7\t6\t5\n";   }//end classpackage puzzle;import framework.*;import javax.swing.*;import java.awt.*;import java.awt.geom.*;import java.awt.event.*;import java.util.*;/**This class is responsible for displaying the puzzle GUI.*/public class puzzleGUI implements UI{/**The problem.*/private puzzleProblem problems;/**The number of moves user has taken in solving the problem.*/private int moveCount;   /**    *The internal frame.    */   public final JInternalFrame frame;   /**Button Height*/private final int BUTTON_HIDTH = 10;   /**Button Width*/private final int BUTTON_WIDTH = 30;/**Frame Width*/private final int FRAME_WIDTH = 600;/**Frame Height*/private final int FRAME_HIDTH = 500;   /**    * Strings for image filenames    */ private final String Ione = "images/one.jpg";   private final String Itwo = "images/two.jpg";   private final String Ithree = "images/three.jpg";   private final String Ifour = "images/four.jpg";   private final String Ifive = "images/five.jpg";   private final String Isix = "images/six.jpg";   private final String Iseven = "images/seven.jpg";   private final String Ieight = "images/eight.jpg";   private final String Iblank = "images/blank.jpg";public  ImageIcon one = new ImageIcon(Ione);  public   JLabel Jone = new JLabel(one);  public ImageIcon two = new ImageIcon(Itwo);  public JLabel Jtwo = new JLabel(two);  public ImageIcon three = new ImageIcon(Ithree);  public JLabel Jthree = new JLabel(three);  public ImageIcon four = new ImageIcon(Ifour);  public JLabel Jfour = new JLabel(four);  public ImageIcon five = new ImageIcon(Ifive);  public JLabel Jfive = new JLabel(five);  public ImageIcon six = new ImageIcon(Isix);  public JLabel Jsix = new JLabel(six);  public ImageIcon seven = new ImageIcon(Iseven);  public JLabel Jseven = new JLabel(seven);  public ImageIcon eight = new ImageIcon(Ieight);  public JLabel Jeight = new JLabel(eight);  public ImageIcon blank = new ImageIcon(Iblank);  public JLabel Jblank = new JLabel(blank);public  JPanel puzzlePanel = new JPanel();  public JPanel framePanel = new JPanel();  public JPanel buttonPanel = new JPanel();  public Container contentPane;  public GridLayout myGrid = new GridLayout(3,3,0,0);  public JTextArea intro, ePanel;  public String menu = "\n\nml=move blank left\nmr=move blank right\nmu=move blank up\nmd=move blank down";   /**    *constructor sets up a new GUI for the puzzle game    *@param puzzleProblem problem    */   public puzzleGUI(puzzleProblem problem){    JButton moveL, moveR, moveU, moveD, random, solve, quit; problems = problem;problems.setUI(this);moveCount = 1;frame = new JInternalFrame();contentPane = frame.getContentPane();frame.setSize(FRAME_WIDTH, FRAME_HIDTH); frame.setTitle("Puzzle Problem");// JPanel framePanel = new JPanel();framePanel.setLayout(new BorderLayout());intro = new JTextArea();intro.setText(problems.getIntroduction());intro.setEditable(false);intro.setBounds(25, 10, 400, 200);framePanel.add(intro,BorderLayout.NORTH);  ePanel = new JTextArea();ePanel.setText("InfoPanel:\nmoveCount:0"+menu);ePanel.setEditable(false);//ePanel.setBounds(25, 10, 400, 200);framePanel.add(ePanel,BorderLayout.CENTER);  //JPanel buttonPanel = new JPanel();buttonPanel.setLayout(new FlowLayout()); //GridLayout myGrid = new GridLayout(3,3,0,0); puzzlePanel.setLayout(myGrid);   puzzlePanel.setBackground(Color.WHITE); String buttonLabels = "ml mr mu md rand solve";StringTokenizer parser = new StringTokenizer(buttonLabels);while(parser.hasMoreTokens()){final String label = parser.nextToken();JButton keyButton = new JButton(label);buttonPanel.add(keyButton);keyButton.addActionListener(new ActionListener(){public void actionPerformed(ActionEvent event){problems.processCommand(label);  }});}//end while quit = new JButton("Quit");quit.setBounds(175, 350, BUTTON_WIDTH, BUTTON_HIDTH);quit.addActionListener(new ActionListener(){public void actionPerformed(ActionEvent event){System.exit(0);}});buttonPanel.add(quit); int[] tiles = problems.getCurState().getArray(); int i=0; while (i<=8) {puzzlePanel.add(getLabel(tiles));    i++; }  framePanel.add(buttonPanel, BorderLayout.SOUTH);   framePanel.add(puzzlePanel, BorderLayout.WEST);contentPane.add(framePanel);frame.setDefaultCloseOperation(JInternalFrame.EXIT_ON_CLOSE);frame.pack(); frame.show();}//end constructor    /**Accessor for the problem.@return the problem.*/public puzzleProblem getProblem() {return problems;}/**Accessor for the move count@return the move count.*/public int getMoveCount(){return moveCount;}   /**    *this method increments movecount and checks for success    */public void getCommand() {   moveCount++;  puzzleState current = problems.getCurState();  if(problems.success(current)){JOptionPane.showMessageDialog(null, "Congratulations.  You solved the problem in  " + moveCount +  " moves");//" and in " + time + " minutes.");  }}   /**Displays Message to the user    *@param String*/public void displayMessage(String message){   JOptionPane.showMessageDialog(null,message);   } /**   Gets the current state from the problem and displays it to the    user.  */    public void update() { problems.computeHeuristic(problems.getCurState()); int heur = problems.getHeur();  int[] tiles = problems.getCurState().getArray(); int i=0; while (i<=8) {puzzlePanel.add(getLabel(tiles));    i++; } ePanel.setText("InfoPanel:\nmoveCount:"+moveCount+"\nheuristic:"+heur+menu); ePanel.updateUI(); puzzlePanel.updateUI();  }/**GetIcon gets the icon on the Jframe*/   public JLabel getLabel(int label){  if (label == 0) {return Jblank;}  else if (label == 1) {return Jone;}  else if (label == 2) {return Jtwo;}  else if (label == 3) {return Jthree;}  else if (label == 4) {return Jfour;}  else if (label == 5) {return Jfive;}  else if (label == 6) {return Jsix;}  else if (label == 7) {return Jseven;}  else if (label == 8) {return Jeight;}  else return null;   }   /**    *Accessor for the internal frame    */ public JInternalFrame getFrame() {  return frame;   }   }//end classedit: added source tags -SiCrane[Edited by - SiCrane on December 14, 2005 8:10:54 AM]
  And you problem is...   ;  I need to have the COMputer solve the puzzle auto. using A* search. Dont have a clue Please help   ;  A good explanation of A* can be found hereIt's about 10 lines of code given the framework you posted above.   ;  It looks like it's an homework... but I might be wrong.C-Pizzle, if you have any SPECIFIC question, ask it, but we can't/won't do the work for you.Eric   ;  Can I someone tell me an really good algorithm for A* that is simular to this??   ;  Can I someone tell me an really good algorithm for A* that is simular to this??   ;  What do you mean "a really good algorithm for A*"? A* is the algorithm.   ;  This looks very much like a homework problem. The source code posted is documented in a style typically used in teaching (I should know ;) ) and the fact that the OP joined today is a dead-giveaway. C-Pizzle, we don't do peoples homework for them. The members of this forum would be happy to help by answering specific questions that would enable you to understand the A* algorithm better. However, we won't write your code for you. I suggest you follow the link at the top of the page to the Articles & Resources section of this website and read the articles under AI:Pathfinding. If you have trouble understanding any of that material, feel free to post here. Otherwise, please don't try and solicit answers to your homework.Regards,Timkin   ;  FOr everyones information I wrote this myself, I have a framework package that i also wrote. I just want to have AI to solve for it and i dontknow how to begin.   