[comp.theory] Best n-Puzzle Algorithms?

chal@CS.CMU.EDU (Prasad Chalasani) (11/01/90)

I'm curious to know about the currently best known n-puzzle algorithms.
(n-puzzle = a generalization of 8-puzzle, 15-puzzle, etc.)
For example, are there algorithms which run in poly(n) time and 
also produce solutions which are poly(n) long ? Are there algorithms
which reformulate the problem in terms of more well-bahaved (e.g., 
permutation-like) operators, etc. ? 

Any info on this will be appreciated.