An optimal algorithm for Reve's puzzle (Q1113675)

This paper starts by showing that some recently published algorithms for Reve's puzzle are not optimal. Reve's puzzle is a generalization of the standard Towers of Hanoi whereby the number of pegs is extended from 3 to \(k\geq 2\). A simple and elegant recursive algorithm for solving Reve's puzzle is presented. Its optimality is assured by an algorithm for optimally splitting a tower of n discs into two subtowers. The theoretical basis for doing so is also discussed.