第19卷．第l2期计算机技术与发展VoI．19No．122009年12月C0MP1玎ERTECHN0L上】GYANDDEVELOPMENTDec．2009基于栈结构的孔明棋算法研究张桂芬，葛丽娜，黄银娟(广西民族大学数学与计算机科学学院，广西南宁530006)摘要：孔明棋是一种玩法简单，但其中变化无数的益智游戏。对孔明棋求解问题进行分析，提出了基于回溯思想的递归和非递归算法，运行结果表明了算法的有效性。文章还围绕栈在存储数据、消解递归等方面的应用对两个算法的优缺点进行了比较分析，递归算法结构清晰，但递归调用次数多；而非递归算法借助程序栈，将程序向循环转化，降低了时间复杂度，但算法难以分析和理解。因此在求解实际问题时可以采用递归思想来分析，然后借助栈用非递归来实现算法。关键词：孔明棋；栈结构；递归；非递归；回溯中囤分类号：1]P301．6文献标识码：A文章编号：1673—629x(2009)12—0051—04ResearchofKongmingChessAlgorithmBasedonStack‘_。StructureZHANGGui—fen，GELi—na，HUANGYin—juan(CollegeofMathematics&ComputerScience，GuangxiUniversityforNationalities，Nanning530006，China)Abstract：Kongmingchessisanintellectivegamewithsimplerulesbutchangeableplayingmeasu／'e．s．Backtrackingisanimportantandeffi—cientsolutionformanyissues．OntheanalysisofKongmingchess，proposesrecursionandnon—recursionalgorithmsbasedonbacktrackfl0rtheissue，whichworkseffectively．Atthe~an'letime，advantagesanddisadvantagesoftheI'WOalgorithms&re。omparedinthestack—basedapplicationsfordatastorage，backtrackingproblem，andrecursion．Recursionhasavividalgorithmstructure，butithastomakeuseofrecurringformanytimes；Whilenon—recursioncirculatestheprogramwiththehelpofaprogramstack．Thusitlowe~theCOITI-plexityoftimebutithasacomplicatedalgorithmwhichishardtoanMy~andunderstand．Itcomestoaconclusionthatrecursionissuit—ableforanalysis，whilenon—recursionisforalgorithminsolvingpracticalproblems．Keywords：Kongmingchess；stack——structure；recttrsion；non——recursion；backtrackingO引言中国跳棋游戏，将棋子跳过邻近的棋子，到达一个旁边栈是限定仅在表尾进行插入或删除操作的线性空着的位置，被跳过的棋子则从棋盘上取去，跳的路径表，具有“后进先出”的特性，广泛应用在各种软件系统可以是上、下、左、右，但不可斜跳，直到剩下最后一颗中，是算法设计重要的一种数据结构uJ。文中对孔明棋子在棋盘中央，游戏便胜利结束，否则游戏失败(剩棋求解问题提出了基于栈结构的递归和非递归算法，余多颗棋子或剩余一颗棋子但不在棋盘中央)。该游给出了算法的具体实现过程，分析栈的应用，实验结果戏玩法非常简单，但其中变化无数，成为风靡世界的智验证了方法的有效性。力游戏。求解一次取胜的移棋步骤成为人们期待解决的问题。ooo1提出问题ooO孔明棋，也叫单身贵族、独立钻石棋，传说是三国ooOooOOOoo．1ooo时代孑L明发明的益智棋。它与华容道、魔术方块同被ooooooo称为智力游戏界的三大不可思}义。孔明棋是单人就可ooOoOo以玩的游戏，由33颗棋子排成井字型盘面。取去中央图1孔明棋的初始棋局的那个棋子，开始展开游戏，如图1所示。游戏玩法似收稿日期：2009—03一l】；修回日期：2009—07—022分析问