Calculating Manhattan Distance within a 2d array

user_6217319 0
Viewed 7478

I am writing a program to solve an nxn 8 puzzle problem. I'm having difficulty with my Manhattan calculation function being off by two from the puzzle I'm testing my program with. This will eventually be expanded to use the A* pathfinding algorithm, but I'm not there yet.

Here is my function(which is based on the initial state of the board and not taking into account the amount of moves taken so far): 

// sum of Manhattan distances between blocks and goal
public int Manhattan()  // i don't think this is right yet - check with vince/thomas
{
    int distance = 0;

    // generate goal board
    int[][] goal = GoalBoard(N);

    // iterate through the blocks and check to see how far they are from where they should be in the goal array
    for(int row=0; row<N; row++){
        for(int column=0; column<N; column++){
            if(blocks[row][column] == 0)
                continue;
            else
                distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]);
        }
    }

    distance = (int) Math.sqrt(distance);

    return distance; // temp
}

This is the example I'm working off of:

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

 initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0

My Hamming calculation is correct and returns 5, but my Manhattan returns 8 instead of 10. What am I doing wrong?

This is the output of my program:

Size: 3
Initial Puzzle: 
 8  1   3   
 4  0   2   
 7  6   5   

Is goal board: false

Goal Array: 
 1  2   3   
 4  5   6   
 7  8   0   
Hamming: 5
Manhatten distance: 8
Inversions: 12
Solvable: true
a-star distance java
1 Answers

The error lies in the update of the distance.

In writing distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]); you add all contents of the cells of initial and goal. Only one excluded in initial and goal is the cell with same coordinates as 0 in initial.

In your example this gives 2 times sum from 0 to 8 minus 5. 2 * 36 -8 = 64. Then you take the square which is 8.

Manhattan - as described by Wiktionary is calculated by distance in rows plus distance in columns.

Your algorithm must lock like (beware, pseudocode ahead!)

for (cell : cells) {
    goalCell = findGoalcell(cell.row, cell.col);
    distance += abs(cell.row - goalCell.row);
    distance += abs(cell.col - goalCell.col);
}

And don't take the square root.

user_15842630
Related