Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (15): 37-40.DOI: 10.3778/j.issn.1002-8331.2010.15.012

• 研究、探讨 • Previous Articles     Next Articles

Rotate-N-Puzzle:Solvable analysis and solving approach

CHEN Yun-chuan,XU Zheng,LUO Ke-lu   

  1. Department of Computer Science & Engineering,University of Electronic Science & Technology of China,Chengdu 610054,China
  • Received:2008-11-21 Revised:2009-02-23 Online:2010-05-21 Published:2010-05-21
  • Contact: CHEN Yun-chuan

Rotate-N-Puzzle问题可解性分析及求解

陈云川,徐 峥,罗克露   

  1. 电子科技大学 计算机科学与工程学院,成都 610054
  • 通讯作者: 陈云川

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

摘要:

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

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

CLC Number: