Reset Undo

"Impossible?" you say. Of course you can remember and retrace your moves back to the solved state. But can you solve the puzzle after someone else has mixed it up to a random position? And do you know for sure that you used the least number of moves?

For years I've been attempting to develop a heuristic for this puzzle, an algorithm that tells you whether you're getting closer to or further away from the solved state. All I can say is that I've found 100 ways that it hasn't worked.

In the meantime I settled on a breadth-first search tree which searches all possible moves from the current state until it finds the solved state. This ensures that the least number of moves has been used. Unfortunately the number of possible states ends up in the millions before long, and that's not including duplicates.

In a previous implementation of this puzzle, I indexed a list in alphabetical order of all unique states and their solutions up to and including 15 moves away from the solved state. Since they're in alphabetical order it's quick to find the solution from the current state using a binary search (a bit like looking up a word in a dictionary). Since file operations are slow I read the indexed list into memory during initialisation, however this took up a lot of memory.

So all this brings me to one conclusion: a heuristic would absolutely be the best and most eloquent solution. I have yet to be able to develop one, but maybe you can.

Good luck!