论文研究RotateNPuzzle问题可解性分析及求解 .pdf

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