Computational Solution of an Old Tower of Hanoi Problem

详细信息    查看全文

• 作者：Andreas M. Hinz ^{hinz@math.lmu.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Tower of Hanoi ; graph distance ; integer sequences ; breadth-first search
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：53
• 期：Complete
• 页码：445-458
• 全文大小：297 K

文摘

This is the amazing story of an innocent looking mathematical puzzle turning into a serious research topic in graph theory, integer sequences, and algorithms. The Tower of Hanoi and The Reve's Puzzle of Lucas and Dudeney, respectively, induced a wealth of interesting mathematical and algorithmic challenges over more than a century. Although some part of the most intriguing question, the Frame-Stewart Conjecture, has recently been solved, several of the original tasks posed by Dudeney remained intractable. We present the history and theory of these questions and a computational approach which allowed us to solve a 104 years old problem of Dudeney, namely the proof of minimality of an algorithm producing paths between perfect states of the Tower of Hanoi with 5 pegs and 20 discs. Many questions about the metric properties of Hanoi graphs remain open, however, and have to be treated by analytical and computational methods in the future.