A New Lower Bound for the Towers of Hanoi Problem

  • Codruƫ Grosu
Keywords: Towers of Hanoi, Shortest paths

Abstract

More than a century after its proposal, the Towers of Hanoi puzzle with 4 pegs was solved by Thierry Bousch in a breakthrough paper in 2014. The general problem with $p$ pegs is still open, with the best lower bound on the minimum number of moves due to Chen and Shen. We use some of Bousch's new ideas to obtain an asymptotic improvement on this bound for all $p \geq 5$.

Published
2016-02-05
Article Number
P1.22