Optimizing Manhattan-distance method for N-by-N puzzles

By N-by-N puzzles I mean f.e. a 3x3 sliding puzzle with one blank space (so a 8-puzzle) or a 4x4 sliding puzzle (so a 15-puzzle). When I try to solve certain puzzles some take no time but others take to much time to the point that I run out of memory. I think it's due to how I calculate the manhattan distance.

Below you see the Board class, an instance of this class holds a puzzle in the variable tiles.

The methods getRow and getCol is used to get the the row and column of a certain value. Then I can calculate the Manhattan distance with the method manhattan.

Could someone tell me how I can optimize this code so that my A*-search algorithm works faster?

```
public class Board {

private int[][] tiles;
private int N;

// construct a board from an N-by-N array of tiles
public Board(int[][] tiles) {
this.tiles = tiles;
N = tiles.length;
}

// return sum of Manhattan distances between blocks and goal
public int manhattan() {
int count = 0;
int expected = 0;

for (int row = 0; row < tiles.length; row++) {

for (int col = 0; col < tiles[row].length; col++) {

int value = tiles[row][col];
expected++;

if (value != 0 && value != expected) {
// Manhattan distance is the sum of the absolute values of
// the horizontal and the vertical distance
count += Math.abs(row
- getRow(getFinalState().tiles, value))
+ Math.abs(col
- getCol(getFinalState().tiles, value));
}
}
}

return count;
}

// helper to get a board in final state
public Board getFinalState() {
int[][] finalArray = new int[N][N];
int value = 0;

for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
value

There are two important speed improvements I see at first glance.

First of all, call getFinalState() only once. That method does a bit of work, and there's no need to call that twice for each tile you loop through.

This leads us to the following:

public int manhattan() {
        int count = 0;
        int expected = 0;
        Board finalState = getFinalState();

        for (int row = 0; row < tiles.length; row++) {
            for (int col = 0; col < tiles[row].length; col++) {
                int value = tiles[row][col];
                expected++;
                if (value != 0 && value != expected) {
                    count += Math.abs(row
                            - getRow(finalState.tiles, value))
                            + Math.abs(col
                                    - getCol(finalState.tiles, value));
                }
            }
        }
        return count;
    }

This already should provide quite a bit of speed-up.

Secondly, your getRow and getCol methods are a bit slow as well. Especially considering that they are only used on the getFinalState() board. One way to speed such methods up generally is to store a Map where Position is a pair of x and y values. The key in this map is the value of a position, so for example the value 12 is at row 1 and column 2 can be:

Map valueMap = new HashMap<>();
valueMap.put(12, new Position(1, 2));

As they are only called for the final state board though, you can calculate the rows and columns mathematically:

public int getCol(int value) {
    return (value - 1) % N;
}

public int getRow(int value) {
    return (value - 1) / N;
}

This should result in a big speed improvement.

neighbors() method:

This method is slow because a) You're using a loop to find the gap b) You are storing the results in a Collection.

Solutions:

• Let a Board store the empty position in a variable or two, such as int freeRow, int freeColumn

• Create your own Iterator implementation that is able to iterate through the possible boards without storing a reference to all of them.

StackExchange Code Review Q#86597, answer score: 5