【摘要】 Rotate-N-Puzzle问题与N-Puzzle问题类似,问题空间也具有组合爆炸性质。经证明,Rotate-N-Puzzle的任何一个初始布局都是可解的。在此结论的基础上,给出了解长度的上界。提出了一种分治算法,在算法中的每一步,采用贪心策略求解问题。实验结果表明,该算法能够在多项式时间内快速求解规模很大的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.更多还原