Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!rochester!pt.cs.cmu.edu!REDNECK.PC.CS.CMU.EDU!chal From: chal@CS.CMU.EDU (Prasad Chalasani) Newsgroups: comp.theory Subject: Best n-Puzzle Algorithms? Message-ID: Date: 31 Oct 90 23:39:32 GMT Sender: chal@REDNECK.PC.CS.CMU.EDU Distribution: comp Organization: School of Computer Science, Carnegie Mellon University Lines: 11 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.