Solved

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

Posted on 2004-09-11
4
10,536 Views
Last Modified: 2013-12-26
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
Comment
Question by:dawnbowling
  • 2
4 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 12041531
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
 

Author Comment

by:dawnbowling
ID: 12042453
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 12042517
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
 
LVL 11

Accepted Solution

by:
bcladd earned 500 total points
ID: 12047541
(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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now