CODEWITHSUNDEEP
prologsliding-tile-puzzle
A. Saraiva
A. Saraiva

Reputation: 11

Puzzle 8 Compatible States

I need to know if is there any algorithm that allows to know beforehand, without searching for every possible solution to the the initial set, if we can reach a second given set.

For example:

[1,0,2,3,5,6,4,8,7] -> [2,3,4,5,8,0,7,1,6]

This algorithm would return True if the second set is reachable from the first one, and False otherwise.

I thought a bit about it and I can certainly say that if the initial set is solvable (it is possible to put all the squares in order) and so is the second one, then this algorithm would return True, because:

[1,2,3,4,5,6,7,0,8] <-> [1,2,3,4,5,6,7,8,0] <-> [1,2,3,4,5,0,7,8,6]

For any given puzzle that is solvable it can be reversed to obtain the original set.

On the other hand, if one of the sets is solvable and the second one is not solvable the algorithm would surely return False because, if you could reach the solvable set starting on the unsolvable set than we would have a contradiction.

Now, the real problem is when both sets are unsolvable. For some reason I'm positive that given an unsolvable set, it is possible to reach any other unsolvable set configuration, since that's what happens when the set is solvable. But I can't find proof or any documentation on it! Can someone enlighten me?

Upvotes: 1

Views: 194

Answers (1)

Kijewski
Kijewski

Reputation: 26043

Since there is a finite amount of board states (9! = 362,880), there is a finite amount of translations between a pair for board states (9!^2 = 131,681,894,400 = 17 GB of information). So brute force once, and be happy for ever.

Upvotes: 1

Related Questions