A linear space algorithm for solving the Towers of Hanoi problem by using a virtual disc (Q1116691)

A space efficient algorithm for solving the Towers of Hanoi problem is presented in this paper. The algorithm utilizes the concept of virtual disc, which is an artificial disc smaller than the smallest real disc. The purpose of introduing such a virtual disc is to enforce a unique disc move at each step. As peg information is not represented, the space complexity of the algorithm is reduced to \(\sim n\) bits, where n is the number of discs in the tower.