关键词: 搜索算法, Rotate-N-Puzzle, 可解性, 解上界, 分治算法, 贪心策略

Abstract: 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.

Key words: search algorithm, Rotate-N-Puzzle, solvable, upper bound, divide-and-conquer algorithm, greedy strategy