Solved

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

Posted on 2004-09-11
11,329 Views
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
Question by:dawnbowling
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 2

LVL 45

Expert Comment

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

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

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

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
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…
Come and listen to Percona CEO Peter Zaitsev discuss what’s new in Percona open source software, including Percona Server for MySQL (https://www.percona.com/software/mysql-database/percona-server) and MongoDB (https://www.percona.com/software/mongo-…
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…
Suggested Courses
Course of the Month7 days, 10 hours left to enroll