The linear twin Towers of Hanoi problem

✍ Scribed by Minsker, Steven

• Book ID: 118153191
• Publisher: Association for Computing Machinery
• Year: 2007
• Weight: 543 KB
• Volume: 39
• Category: Article
• ISSN: 0097-8418
• DOI: 10.1145/1345375.1345410

✦ Synopsis

We propose a simple new variation of the Towers of Hanoi problem, in which there are three pegs arranged in a row and there are two stacks (black, white) of n rings each, initially located on the end pegs. The object is to exchange the stacks in accordance with the usual Hanoi rules, and with the additional restriction that rings cannot move directly from end to end. An optimal algorithm is presented, and its performance is analyzed. The problem and its solution are
not
difficult; the purpose of this paper is to present a simple yet interesting exercise in discrete mathematics and recursive algorithms.