An iterative solution to the four-peg Tower of Hanoi problem

ABSTRACT

One of the variations of the Towers of Hanoi puzzle allows for p pegs, and for four pegs the solution to this variation is shown to have a simple structure which can be used to derive an iterative solution to the problem.

REFERENCES

• 1: P.J. Hayes, A Note on the Towers of Hanoi Problem. The Computer Journal 20 (3), 282-285 (1977).
• 2: T.R. Walsh, Iteration strikes back-At the Cyclic Towers of Hanoi, Information Processing Letters 16 (2), 91-93 (1983).
• 3: M.C. Er, An Iterative Solution to the Generalized Towers of Hanoi Problem, BIT 23, 295-302 (1983).
• 4: J.S. Rohl, Towers of Hanoi: The Derivation of Some Iterative Versions, The Computer Journal 30 (1), 70-76 (1987).
• 5: Edouard Lucas, Rdcrdations Mathdmatiques vol III, Gauthier-Villars et Fils, 1893.
• 6: E. Dudeney, The Canterbury Puzzles. (1907). A Fourth Edition was available from Dover Publications.
• 7: B.M. Stewart, Advanced Problems for Solution, 3918. American Mathematical Monthly 46, 363 (1939).
• 8: J'.S, Frame, Solution to problem 3918. American Mathematical Monthly 48, 216-217 (1941 ).
• 9: B.M. Stewart, Solution to problem 3918. American Mathematical Monthly 48, 217-219 (1941).
• 10: Br. A. Brousseau, Tower of Hanoi with more Pegs. Journal of Recreational Mathematics8 (3), 169-176 (1976).
• 11: D. Wood, The Towers of Hanoi or Brahma Revisited, Journal of Recreational Mathematics 14, 17-24 (1981).
• 12: R. Newman-Wolfe, Observations on Multi-Peg Towers of Hanoi, Technical Report TR 187, Department of Computer Science, University of Rochester, (1986).
• 13: A. Pettorossi, Towers of Hanoi Problems: Deriving Iterative Solutions by Program Transformations, BIT, 25, 327-334 (1985).
• 14: P. Buneman, and L. Levy, The Towers of Hanoi Problem, Information Processing Letters 10, 243-244 (1980).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs

General Terms:
Algorithms