In 8-puzzle finding nr of steps moving a tile to the right place

Question

In 8-puzzle I want to count the number of moves it would take to move a specific tile to it's goal place. The problem is my method for this is >100 lines long which is obviously way too much. I'll only include part of that method that counts steps to move the piece to the right row if the goal row is higher. It gives the idea, it is probably hard to read even with that piece of it only, I did comment profusely though.

To further illustrate what the code does - for state {{0,2,3},{4,1,6},{7,8,5}} the count of steps for moving the 1 tile to first spot would be 5:

    2  3       2     3        2  1  3        2  1  3          1  3       1     3       
 4  1  6   =>  4  1  6   =>   4     6   =>      4  6   =>  2  4  6   =>  2  4  6
 7  8  5       7  8  5        7  8  5        7  8  5       7  8  5       7  8  5

And for the code ( or bits and pieces of it):

    // Finding the nr of steps it would take to move tile to it's goal place
public int countSteps(int tileNr) {
    int steps = 0;
    int[] goal = findGoal(tileNr);
    int[] current = findTile(tileNr);
    int[] empty = findTile(0);
    GameState copy = new GameState(this);
    while (goal[0] != current[0] && goal[1] != current[1]) {
        // If the tile needs to be moved upwards (row coord is smaller in
        // goal)
        if (goal[0] < current[0]) {
            if (empty[0] == current[0] - 1 && empty[1] == current[1]) {
                // If empty above current tile, switch them
                steps++;
                current = empty;
                empty[0]++;
            } // Else have to move the empty tile to above current
            else if (empty[1] == current[1]) {
                if (empty[0] < current[0] - 1) {
                    // If empty too high in the right column, move empty
                    // tile down
                    steps++;
                    empty[0]++;
                }
                if (empty[0] > current[0]) {
                    // If empty below current, move out from that that
                    // column
                    steps++;
                    if (empty[1] < 2)
                        empty[1]++;

                    else
                        empty[1]--;
                }
            } else if (empty[0] == current[0]) {
                if (empty[1] < current[1]) {
                    // If empty to the right in right row
                    // move to the left
                    steps++;
                    empty[1]++;
                }
                if (empty[1] > current[1]) {
                    // If empty to the left in right row move to the right
                    // column
                    steps++;
                    empty[1]--;
                }

            }
        }
    }
    return steps;
}

// Finding coords for the tile in goal state
public int[] findGoal(int tileNr) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (goalState[i][j] == tileNr)
                return new int[] { i, j };
        }
    }
    return new int[] { -1, -1 };
}

// Finding coords for the tile in current state
public int[] findTile(int tileNr) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (state[i][j] == tileNr)
                return new int[] { i, j };
        }
    }
    return new int[] { -1, -1 };
}

Answer 1

Concerns

This logic is complicated and long winded... so much so, that you cut a huge portion of it, or otherwise there is a big bug... You have the condition inside the while-loop:

   // If the tile needs to be moved upwards (row coord is smaller in
   // goal)
   if (goal[0] < current[0]) {

But there is no 'else' condition for that. Did you 'trim' that out?

What if the row is in the other direction? What if it is already in the correct row?

Incremental Suggestion

Generally, when presented with problems like this it often helps to generalize the problem....

For example, if you create a concept called a 'direction', which is a two-value pair, say an int[2] (keeping it consistent with your code). If the target is at coordinate [0,0] and the current position of the tile is at [2,2] then the direction is [-1,-1] (you need to be reducing the row/column coordinates by 1 to get to your target.

Then, your while loop can become:

int[] goal = findGoal(tileNr);
int[] current = findTile(tileNr);
int[] empty = findTile(0);
for (int[] direction = getDirection(current, goal);
           direction[0] != 0 || direction[1] != 0;
           direction = getDirection(current, goal)) {

    if (direction[0] != 0) {
        // find a way to move things in the row axis
        // do this by getting the empty space where we need to move to....
        ......
        // swap our tile with the empty space.
        empty[0] -= direction[0];
        current[0] += direction[0]; // update the current position.
    } else { // direction[1] must be != 0
        // find a way to move things in the column axis
        // do this by getting the empty space where we need to move to....
        ......
        // swap our tile with the empty space.
        empty[1] -= direction[1];
        current[1] += direction[1]; // update the current position.
    }
}
// to exit the loop, direction == [0, 0] ... i.e. we are at our target.

Bigger suggestion

In this case I would consider a significantly different data structure.... :

1. Create a Tile Object for each Tile.
2. The GameState instance will then just become a loose collection of Tiles.
3. Keep the tile location embedded in the Tile instance.
4. Treat the empty space as a tile, and the 'rule' is that the Empty tile is the only tile that can swap positions with it's neighbour.
5. You can embed the logic in to methods on the Tile to identify the tile position and directions.

Doing the above can reverse a lot of your game logic, but the benefit will be that you move the logic out of the main methods in to the object orientation....