Is it possible to check if the 15-puzzle is solvable with a different goal state?

Question

So I have a random 15-puzzle, or any N-puzzle with even width, and I also have a random goal-state. That is, the blank tile and other tiles are also randomly placed.

I am able to check if the 15 puzzle is solvable with the standard goal state of having the tiles in order and blank in the bottom right, but randomizing the goal state seems to be more tricky than the standard 8 puzzle.

Example:

Start State
8    4    1   6
11   2    3   10
15   12   0   9
14   5    7   13

Goal State:
11   4    1   0
8    2    3   10
5    15   6   9
12   9    7   13

The rules for the standard 15-puzzle solvabilty are:

If the width is odd, then every solvable state has an even number of inversions.

If the width is even, then every solvable state has

• An even number of inversions if the blank is on an odd numbered row counting from the bottom;

• An odd number of inversions if the blank is on an even numbered row counting from the bottom;

Answer 1

I don't think different goal have any effect on solvability.

The simplest solution I can think of is to map numbers in the custom goal state to the numbers in the standard goal state. E.g: For the first row you treat 11 as if it was 0, 4-> 1, 1->2, 0->3 and so on.

Answer 2

The algorithm is the same as for standard puzzle, but you need a little change.

In general, the algorithm for reachability from start position S to goal position G is:

1. Calculate number of inversions in G - I(G)
2. Calculate number of inversions in S - I(S)
3. If:
   • width is odd and I(G) and I(S) have the same parity, G is reachable from S (in other words, S is solvable)
   • width is even:
     1. Find the row number where blank is located in G - B(G)
     2. Find the row number where blank is located in S - B(S)
     3. If I(G)
        • is even and I(S) and abs(B(G) - B(S)) have the same parity, G is reachable from S
        • is odd and I(S) and abs(B(G) - B(S)) have different parity, G is reachable from S

In other cases G is unreachable from S.

---

Now let's see on your example. Represent a state as a list:

List<Integer> start = Arrays.asList(
        8, 4, 1, 6, 
        11, 2, 3, 10,
        15, 12, 0, 9,
        14, 5, 7, 13);
List<Integer> goal = Arrays.asList(
        11, 4, 1, 0,
        8, 2, 3, 10,
        5, 15, 6, 9,
        12, 14, 7, 13); // in your example there's a second 9 instead of 14

A function, which will count number of inversions:

int inversions(List<Integer> numbers) {
    int inversions = 0;
    for (int i = 0; i < numbers.size(); i++) {
        int n = numbers.get(i);
        if (n <= 1) {
            continue;
        }
        for (int j = i + 1; j < numbers.size(); j++) {
            int m = numbers.get(j);
            if (m > 0 && n > m) {
                inversions++;
            }
        }
    }
    return inversions;
}

Finally, check the solvability:

boolean isSolvable(List<Integer> start, List<Integer> goal) {
    int inversions = inversions(start);
    int goalInversions = inversions(goal);
    if (width % 2 == 0) {
        int goalZeroRowIndex = goal.indexOf(0) / width;
        int startZeroRowIndex = start.indexOf(0) / width;
        // a little optimization is possible since we're only interested in parity
        return (goalInversions % 2) == ((inversions + goalZeroRowIndex + startZeroRowIndex) % 2);
    } else {
        // for odd width just compare parity of inversions
        return (inversions % 2) == (goalInversions % 2);
    }
}

This function will work on both standard and random variations, regardless of 0 position.

For a given start and goal positions:

I(G) = 32
I(S) = 36
B(G) = 0
B(S) = 2
abs(B(G) - B(S)) = 2

I(G) is even and both I(S) and abs(B(G) - B(S)) have the same parity, so the puzzle is solvable. In fact, it is solvable in 31 moves:

12, 2, 11, 15, 2, 12, 9, 10, 6, 1, 4, 11, 15, 2, 12, 5, 14, 12, 5, 15, 2, 8, 11, 4, 3, 6, 10, 9, 6, 3, 1