Distance Taxicab geometry

Question

So I have an initial state for an array that is an 8puzzle and a goal state

int[] myPuzzle   = {1,3,4,
                    0,2,5,
                    8,6,7}

int[] goalPuzzle = {2,1,0,
                    3,4,5,
                    8,7,6};

I am trying to figure out what the distance between the initial state and goal state is without going diagonally. Can anyone help me out? (Note: I don't mind turning this array into a 2d array if that makes things simpler I just want to know what the distance for everything is).

Everywhere that I look online expects a goalPuzzle state that is just in ascending order. This is not the case for my problem.

Answer 1

These arrays are representations of the state of a 8-puzzle. One way to implement a solver for such a puzzle boils down to a shortest path search (see How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm? for further information). And particularly for the A* algorithm, you will need an admissible heuristic, which in this case can be given by the sum of the Taxicab- or Manhattan distances between the positions of the tiles in the current array, and their positions in the goal state. This heuristic is used because it defines a lower bound on the actual number of moves that will be required. As mentioned in the comment: The actual number of moves must at least be as large as the pure geometric (manhattan) distance between the tiles.

Implementing this is not so difficult. The exact implementation will depend on the representation of the board state. One could also use 2D arrays for this. But using 1D arrays has a nice advantage: It's trivial to find the correspondences between the tile positions.

Generally, when you find a certain value v at the position (sx,sy) in the current state, then you have to search for the position (gx,gy) that this value has in the goal state, so that you may compute the distance between the two.

But since the arrays only contain numbers from 0 to array.length-1, you can compute the "inverse" of the goal state, and use this to directly look up the position (index) of a value in the array.

_{Example and details added, as per request in the comments:}

For example, consider the value 6 in the puzzle, which appears at position (1,2). Now you have to find the position that 6 has in the goal state. This is (2,2), or index 8, in your example. You could find this position by searching the value 6 in the goal state array. But when you do this for each value, this will be O(n*n) - i.e. it would be inefficient. The invert method will, for the given goal state, return [2,1,0,3,4,5,8,7,6]. Element i of this array is the position that the value i had in the original array. So for example, you can access this array at index 6 (the value that you are looking for), and there find the value 8. And the 8 is exactly the index that the value 6 had in the goal array. So finding the index of a certain value in the goal array can be done with a simple lookup (i.e. without searching through the whole array).

From an index in the 1D array, and the size of the board, you can compute the (x,y) coordinates, which are then used to compute the distance.

Here is an example:

public class TaxicabPuzzle
{
    public static void main(String[] args)
    {
        int[] myPuzzle = {
            1,3,4,
            0,2,5,
            8,6,7
        };

        int[] goalPuzzle = {
            2,1,0,
            3,4,5,
            8,7,6
        };

        int distanceBound = computeDistanceBound(myPuzzle, goalPuzzle, 3);
        System.out.println("Distance bound: "+distanceBound);
    }

    private static int computeDistanceBound(
        int state[], int goal[], int sizeX)
    {
        int inverseGoal[] = invert(goal);
        int distance = 0;
        for (int i=0; i<state.length; i++)
        {
            int goalIndex = inverseGoal[state[i]];
            distance += distance(i, goalIndex, sizeX);
        }
        return distance;
    }

    // For two indices in an array that represents a 2D array in row-major
    // order, compute the manhattan distance between the positions that are
    // defined by these indices
    private static int distance(int index0, int index1, int sizeX)
    {
        int x0 = index0 % sizeX;
        int y0 = index0 / sizeX;
        int x1 = index1 % sizeX;
        int y1 = index1 / sizeX;
        return Math.abs(x1 - x0) + Math.abs(y1 - y0);
    }

    // Given an array containing the values 0...array.length-1, this
    // method returns an array that contains at index 'i' the index
    // that 'i' had in the given array
    private static int[] invert(int array[])
    {
        int result[] = array.clone();
        for (int i=0; i<array.length; i++)
        {
            result[array[i]] = i;
        }
        return result;
    }
}