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.