Re: 15 puzzle minimum moves approximation question

Jaap wrote:
>
> Rick D. wrote:
> > I'm trying to create a computer algorithm to solve a 15 puzzle
> > I know this is NP problem, But i'd like to know if there is a method
> > to estimate (on average) how many moves it takes to solve a shuffled
> > puzzle. Or if there is data available from people who have solved the
> > (near) best path for some shuffled puzzles. Basically i am looking for
> > a number to compare my results with to see if my algorithm is any
> > good.
>
> I just did some web searching and found this:
> 1999: The parallel search bench zram and its applications
> by A. Brüngger, A. Marzetta, K. Fukuda, and J. Nievergelt
> Available here:
> http://www.ifor.math.ethz.ch/publications/oldpublications
>
> They proved that the worst cases are 80 moves from solved.
>
> Jaap

More references can be found at
http://www.research.att.com/projects/OEIS?Anum=A087725

Counting all possible paths is a hard task, because it seems impossible
to find shortcuts in the process of scanning which paths were already
visited. The n=80 result for the 15-puzzle is also a result of efficient
database technology.

To learn more about the complexity of the problem I tried to search
myself; the result is in
http://www.research.att.com/projects/OEIS?Anum=A089484

Hugo Pfoertner
.

Quantcast