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

0
votes

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;

1
javasliding-tile-puzzle
maybe contribute some code? – LuckyLikey

1 Answers

1
votes

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.