0

i am writing an A* algorithm which can solve the 8-puzzle in Java, so far i have implemented DFS, BFS, A* using the number of tiles out of place and i just need to implement it using the heuristic for the Manhattan distance.

As you are probably aware the Manhattan distance is the sum of each tiles displacement in relation to its current position and its index in the goal state.

I have googled around and found these stack over flow topics:

Calculating Manhattan Distance Manhattan distance in A*

Which returned the following code:

  int manhattanDistanceSum = 0;
for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
    for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
        int value = tiles[x][y]; // tiles array contains board elements
        if (value != 0) { // we don't compute MD for element 0
            int targetX = (value - 1) / N; // expected x-coordinate (row)
            int targetY = (value - 1) % N; // expected y-coordinate (col)
            int dx = x - targetX; // x-distance to expected coordinate
            int dy = y - targetY; // y-distance to expected coordinate
            manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
        } 
    }

This is what i don't understand, given this board and this goal state:

initial board:

 1,2,5
 3,0,4
 6,7,8

goal state:

0,1,2
3,4,5
6,7,8

if i key in the values for board[0][0], which has the value 1, which happens to be 1 move away from its correct position i get these results:

 x = 0;
 y = 0;
 value = 1;
 targetX = (value -1)/3; // 0/3 = 0
 targetY = (value -1)%3 //0%3 = 0

 int dx = x - targetX; // 0 - 0
 int dy = y - targetY; // 0 - 0
 manhattanDistanceSum += Math.abs(dx) + Math.abs(dy);

Which produces ultimately 0 + 0, which is obviously incorrect as it should return the value of 1.

Is there another way to it for example:

  for(int i = 0; i < 3 i ++){
     for(int j =0; j < 3; j ++){
        int value = currentBoard[i][j];
        int goalValue = getLocationOfValueInGoalState(value);

       /* caluclate the value's X distance away from the returned goal state location   for said value, then do the same for the Y */





      }
   }

Hope someone understands my question, im a bit confused at the moment in all honesty.

Community
  • 1
  • 1
chris edwards
  • 1,332
  • 4
  • 13
  • 31
  • Your goal state is not the same as the goal state that the first code-block is expecting. – tucuxi Nov 04 '13 at 15:02
  • If you use a debugger (or print out intermediate values) you will spot the problem. Try a loop like this, and you will see what's going on: for (int value = 0; value < 9; value++) { int targetX = (value - 1) / 3; int targetY = (value - 1) % 3; System.out.println("Value= " + value + ", target =(" + targetX + ", " + targetY + ") "); } – Darius X. Nov 04 '13 at 15:08

2 Answers2

3

There is a fine point of difference in what the goal state looks like for you, and what the goal state looks like for the reference implementation you are viewing.

For the reference implementation, it works if the goal state looks like:

1 2 3
4 5 6
7 8 0

In your case, you want Manhattan distance for:

0 1 2
3 4 5 
6 7 8

A quick fix is to simply redefine your goal state as the former.

However, if the latter is what you really want, then change the targetX/Y to not have a subtraction of 1 from value.

Juser1167589
  • 415
  • 7
  • 16
  • Thanks @Juser1167589 is could you clarify why the -1 was used in the first place, i understand it is used when having the "space" in the opposite corner, but what is the actual English description of what it does? – chris edwards Nov 04 '13 at 19:08
  • @chris edwards It's just a matter of state space definition really. The - 1 was present in the Manhattan distance implementation you were looking at because the top of those two board configurations was considered the "goal state". Your implementation defines the bottom as the "goal state", so the - 1 wasn't needed. Remember that the state space, and in particular the goal state, is what you define your heuristics around. – Juser1167589 Nov 04 '13 at 22:00
-1

The manhattan distance is the distance defined as the increase in the distance when moving pieces diagonally. If the movable tile is in the upper right hand corner, to move the piece to the bottom left hand corner, you can't move it directly along the diagonal. You have to make sequential left then down move. The increase is the manhattan distance. The fun part of this is the shuffling algorithm. The manhattan distance is also know in mathematics as the taxi-cab distance, http://en.wikipedia.org/wiki/Taxicab_geometry .

kslote1
  • 720
  • 6
  • 15