DP approach for the n-puzzle problem

is there a DP approach for开发者_开发知识库 the n-puzzle problem

thanks all, appreciate that...

rajan

Dynamic Programming is a technique used to solve problems by reducing difficult cases to simpler cases, recursively, until you reach a case simple enough to solve "by inspection". Therefore, there can only be a sensible DP approach to the n-puzzle problem if, at each stage, you can consider a move which reduces the complexity of the problem.

For instance, if the first "move" in a n-puzzle always made it into an "(n-1)-puzzle" (for some concrete definition of "move", and assuming an (n-1)-puzzle made sense), then you could apply DP, eventually solving the "1-puzzle", and composing back upwards to solve the n-puzzle.

I don't know of any such simplification process for the n-puzzle; and I can't think of one at the moment. However, that doesn't mean one doesn't exist.