Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 12760
  • Last Modified:

A* Heuristic algorithm for the 8-tile puzzle using java.

I am looking for code in java that implement A* algorithm for the 8-puzzle game by given initial state :

1 3 2
4 5 6    
8 7

and Goal state

1 2 3
8   4
7 6 5

I want to print out the running steps which solve this puzzle from initial to goal state

This is the code I have so far.  I am a student so I may be completely off base here.




class tiles
{
      public static int newTable [] =            {1,8,3,6,0,7,4,2,5};
      public static int table [] =            {1,8,3,6,0,7,4,2,5};              //Hard coded init values for now
      public static int goalTable[] =            {1,2,3,8,0,4,7,6,5};             //Goal values to use for comparison purposes
      public static int blankSpot;                                                      //Variable used to store the location of the "blank spot"
      public static int a=0, b=0, c=0, x;
      public static int numCorrect=0;
      public static int origNum, leftNum,rightNum,upNum,downNum;

         public static void main(String args[])
               {
                        puzzSolver();
            }



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Solves puzzle
      static void puzzSolver()
      {
            int a;
            printinitvalues();        //Prints the puzzle

            for (a=0; a<5; ++a)
                  {
                        countTiles();
                        branch();
                        System.out.println(numCorrect);
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Solves puzzle


      static void branch()
      {
            if (numCorrect<9)
                  {
                        countTiles();
                        locateSpace();                  //Locates the position of the blank space
                        //System.out.println(numCorrect);
                        checkNum();
                        getLarge();
                        //System.out.println(x);

                        if(x==leftNum)
                              changeTableLeft();
                                    else if(x==rightNum)
                                          changeTableRight();
                                                else if(x==upNum)
                                                      changeTableUp();
                                                            else
                                                                  changeTableDown();
                        printinitvalues();
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Counts tiles in correct placement
      static void countTiles()
      {
            int i;
            numCorrect =0;
            for (i=0; i<9; ++i)
                  {
                        if (newTable[i]==goalTable[i])
                        {
                              numCorrect = numCorrect + 1;
                        }
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++





//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Check correct placement after each possible move

      static void checkNum()
      {
            makeMoveLeft();
            //printNewValues();              //Prints the puzzle
            locateSpace();                  //Locates the position of the blank space
            countTiles();
            leftNum = numCorrect;
            //System.out.println(leftNum);
            resetTable();

            makeMoveUp();
            //printNewValues();              //Prints the puzzle
            locateSpace();                  //Locates the position of the blank space
            countTiles();
            upNum = numCorrect;
            //System.out.println(upNum);
            resetTable();

            makeMoveRight();
            //printNewValues();              //Prints the puzzle
            locateSpace();                  //Locates the position of the blank space
            countTiles();
            rightNum = numCorrect;
            //System.out.println(rightNum);
            resetTable();

            makeMoveDown();
            //printNewValues();              //Prints the puzzle
            locateSpace();                  //Locates the position of the blank space
            countTiles();
            downNum = numCorrect;
            //System.out.println(downNum);
            resetTable();
      }

//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Checks which move made greatest impact

      static void getLarge()
      {
            x=leftNum;

            if (x<rightNum)
                  {
                        x=rightNum;
                  }

            if (x<upNum)
                  {
                        x=upNum;
                  }

            if (x<downNum)
                  {
                        x=downNum;
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//
      static void changeTableLeft()
      {
            makeMoveLeft();
            int a;
            for (a=0; a<9; ++a)
            {
                  table[a] = newTable[a];
            }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//
      static void changeTableRight()
      {
            makeMoveRight();
            int a;
            for (a=0; a<9; ++a)
                  {
                        table[a] = newTable[a];
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//
      static void changeTableDown()
      {
            makeMoveDown();
            int a;
            for (a=0; a<9; ++a)
                  {
                        table[a] = newTable[a];
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//
      static void changeTableUp()
      {
            makeMoveUp();
            int a;
            for (a=0; a<9; ++a)
                  {
                        table[a] = newTable[a];
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Makes moves of blank tiles to the left--does error checking to ensure move is allowed
      static void makeMoveLeft()
      {
            if(blankSpot!=0)
            {
                  if (blankSpot !=3)
                  {
                        if (blankSpot !=6)
                        {
                              int temp;
                              temp = table[blankSpot-1];
                                    if (temp != goalTable[blankSpot-1])
                                          {
                                                newTable[blankSpot-1]=table[blankSpot];
                                                newTable[blankSpot] = temp;
                                                countTiles();
                                          }
                        }
                  }
            }
            //else makeMoveUp();
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Makes moves of blank tiles to right
      static void makeMoveRight()
      {
            if(blankSpot!=2)
                  {
                        if (blankSpot !=5)
                              {
                                    if (blankSpot !=8)
                                          {
                                                int temp;
                                                temp = table[blankSpot+1];
                                                if (temp != goalTable[blankSpot+1])
                                                      {
                                                            newTable[blankSpot+1]=table[blankSpot];
                                                            newTable[blankSpot] = temp;
                                                            return;
                                                      }
                                          }
                              }
                  }

      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Makes moves of blank tiles up

      static void makeMoveUp()
      {
            if(blankSpot!=0)
                  {
                        if (blankSpot !=1)
                              {
                                    if (blankSpot !=2)
                                          {
                                                int temp;
                                                temp = table[blankSpot-3];
                                                if (temp != goalTable[blankSpot-3])
                                                      {
                                                            newTable[blankSpot-3]=table[blankSpot];
                                                            newTable[blankSpot] = temp;
                                                      }
                                          }
                              }
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Makes moves of blank tiles down
      static void makeMoveDown()
      {
            if(blankSpot!=6)
                  {
                        if (blankSpot !=7)
                              {
                                    if (blankSpot !=8)
                                          {
                                                int temp;
                                                temp = table[blankSpot+3];
                                                if (temp != goalTable[blankSpot+3])
                                                      {
                                                            newTable[blankSpot+3]=table[blankSpot];
                                                            newTable[blankSpot] = temp;
                                                      }
                                          }
                              }
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/*I used this method to print the values that are stored for the puzzle*/
      static void printinitvalues()
            {
                  int t, i=1;
                  for (t=0; t<9; ++t)
                        {
                              System.out.print(table [t] + "  ");
                                    if (i == 3)                                          //I use this loop to create a new row
                                          {
                                                System.out.println();
                                                i = i - 3;
                                          }
                              i = i + 1;
                        }
                              System.out.println();
                              System.out.println();
            }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Printing the Goal State
      static void printGoalvalues()
      {
                  int t, i=1;
                  for (t=0; t<9; ++t)
                        {
                              System.out.print(goalTable [t] + "  ");
                                    if (i == 3)                                          //I use this loop to create a new row
                                          {
                                                System.out.println();
                                                i = i - 3;
                                          }
                              i = i + 1;
                        }
                              System.out.println();
                              System.out.println();
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Prints the modified table
      static void printNewValues()
            {
                  int t, i=1;
                  for (t=0; t<9; ++t)
                        {
                              System.out.print(newTable [t] + "  ");
                                    if (i == 3)                                          //I use this loop to create a new row
                                          {
                                                System.out.println();
                                                i = i - 3;
                                          }
                              i = i + 1;
                        }
                              System.out.println();
                              System.out.println();
            }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//I used this method to locate the blank space in the puzzle
      static void locateSpace()
      {
            int t;
            for (t=0; t<9; ++t)
                  {
                        if (table[t]==0)
                              {
                                    blankSpot = t;
                                    return;
                              }
                  }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Resets the testing table
      static void resetTable()
      {
            int i;
            for (i=0; i<9; ++i)
            {
                  newTable[i]=table[i];
            }
      }
//End of method
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
}



0
dawnbowling
Asked:
dawnbowling
  • 2
1 Solution
 
sunnycoderCommented:
Hi dawnbowling,

Since this is a homework question, Experts here will not provide you with code as it will be a voilation of membership agreement.
http://www.experts-exchange.com/memberAgreement.jsp

If you need some help with the algorithm or logic, post here. Else I would suggest that you try to write the A* on your own and if you face any difficulties, post in Java TA
http://www.experts-exchange.com/Programming/Programming_Languages/Java/

But unless you have some code for the algorithm, you may not get much help there either.

If you do not help with the algorithm and need Java advise only, then please post in community support and get this question deleted.
http://www.experts-exchange.com/Community_Support/

sunnycoder
0
 
dawnbowlingAuthor Commented:
I wasn't asking for the code, just wanted someone to look at my code (whichI posted) and see if I was on the right track.  
0
 
sunnycoderCommented:
I am sorry in that case, I was mislead by the first line of your question "I am looking for code" :)

You will find some good Java experts in the Java TA. I would suggest that you ask community support to delete this question so that you can post it again in Java. It is possible to move it to Java but that will not bring it to the top of the pile and lot of Experts will miss it.

Posting in community support is free.
0
 
bcladdCommented:
(1) Your code in branch() has some problems. Remember that A* is _heuristic_. That is, there is no assurance that making the "best" move will actually lead to a solution. If it doesn't, your code will fail to find any solution. If making a given move leads to a dead end, you will want to backtrack to a decision point and find the best alternative to expand. In fact, I am thinking that you aren't keeping track of enough information for A*. You want to know the "total" cost of every position you have reached. You then expand the best available.

Your search is purely heuristic (that is, the number of right tiles is all that matters, not how many moves it took to get to the given position). It would also be nice to know what positions you have seen so that you don't expand the same position more than once. In particular, if no tiles are right, you will always select move left (even when there is no legal move that way...this is a problem as I glance through your code).

Remember that in A* you are actually interested in the TOTAL cost of a node: The cost of getting there + the (heuristic) cost of solving from there. That is where the f(node) = g(node) + h(node) formula comes from. You sort nodes based on the f value.

If what I have said is not clear, ask questions. Happy to help.

-bcl
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now