How can the n-puzzle problem be solved efficiently?

[Terilien]

Given n marbles arrayed in a square with n+1 slots(slot n+1 being empty(labelled with numbers from 1 to n+1) you have to bring them all from their orginal positions to a position in whcih bringing them back would take the most moves. The rule is to move each marble to the adjacent square.


I'm really not sure as to how to solve it. I'm really just doing this because I saw it and the fact that i don't know the solution is killing me.


\

 

[StatusX]

It's kind of hard to understand what you're saying, but it seems like what you're describing is essentially the http://en.wikipedia.org/wiki/Fifteen_puzzle" .

 

[Terilien]

Yes its just that and I'd like to know how to prove what combination requires the greatest number of moves.

 

[StatusX]

According to that page:

For larger versions of the n-puzzle, finding a solution is easy, but the problem of finding the shortest solution is NP-hard.

So I'm guessing there's no easy answer to your question.