Rotate-N-Puzzle:Solvable analysis and solving approach
Luo Ke-lu · Computer Engineering and Applications Journal · 2010
Rotate-N-Puzzle is a similar problem like N-Puzzle.The problem space of Rotate-N-Puzzle is also asymptotically exponential.It’s proved that any initial configuration of Rotate-N-Puzzle is solvable.This proof also gives out the upper bound of the solution length.A divide-and-conquer algorithm is implemented,which solves the problem greedily in each step.As the experiment result states,this algorithm can solve rather large scale Rotate-N-Puzzle problems in polynomial running time.