SpiceTrader SpiceTrader - 24 days ago 15
C++ Question

Finding target coordinates for Manhattan Distance in 8 Puzzle | C++

I'm trying to find a way to calculate the manhattan distance between two 2D array's containing numbers between 0 and 8. Assuming one of the arrays (the goal for the 8 puzzle) is:

1 2 3
4 5 6
7 8 0


I understand that between (x1 , y1) & (x2, y2), the
Manhattan Distance = |x1 - x2| + |y1 - y2|

My code looks something like:

for(x = 0; x < 3; x++){
for(y = 0; y < 3; y++){
int value = matrix[x][y];
int targX; //Target X coordinate
int targY; //Target Y coordinate
int distX = abs(x - targX);
int distY = abs(y - targY);
mDist = mDist + distX + distY;
}
}


I'm having trouble finding a way to get the target coordinates for any particular value.

Answer

Target coordinates for a value n are ((n-1) div 3, (n-1) mod 3)

The above values will be defined assuming the origin (0,0) to be at the top left corner, i.e. the square where 1 will be placed. X coordinates increase in the right direction, and Y coordinates in the downward direction.

Comments