Tower of Hanoi Algorithm

8 Key excerpts on "Tower of Hanoi Algorithm"

• 

  eBook - ePub

  Advanced Logo

  A Language for Learning

  • Michael Friendly(Author)
  • 2014(Publication Date)
  • Psychology Press

    (Publisher)

  7 The Tower of Hanoi: A Case Study

  DOI: 10.4324/9781315801858-7

  Learning the vocabulary and rules of a language such as Logo or English is important, but it is most important to use the language for some purpose. In this chapter we apply what we have covered so far in a programming project of some complexity, and in doing so, we illustrate some useful programming and problem-solving techniques. The major focus is on the process of solving this problem and on developing strategies for solving others.

  Good puzzles have high “surprise value”: the rules are usually surprisingly simple; the solution, usually surprisingly difficult. The best puzzles make rich contact with ideas or principles that go far beyond the puzzle itself. The Tower of Hanoi is such a puzzle.

  In this puzzle there are a number of disks of increasing size piled initially on one of three pegs, with the smallest disk at the top (see Figure 7–1 ). The problem is to move all the disks, one at a time, onto a different peg. Only the currently top disk on any peg may be moved, and you may never place a larger disk on top of a smaller one. In Figure 7–1 , the five disks start on peg A and are to be moved to peg B.

  Fig. 7–1 The Tower of Hanoi problem with 6 disks

  Having solved a good problem gives a sense of accomplishment, but don’t stop there—your solution can also be the starting point for new problems or discoveries. The secondary aim of this chapter is to suggest ways this may be done. The Tower of Hanoi has close connections with other problems that look very different on the surface. The broader goal is to explore the idea that beneath the surface, problems in different domains can often show remarkable similarity.

  You can buy or make a Tower of Hanoi puzzle, but you can get the idea by using stacks of coins of different size—say, dime, penny, and nickel, arranged on spots marked A, B, and C. STOP—Take some time to try to solve the puzzle with three or four coins before reading further.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithmic Problem Solving

  • Roland Backhouse(Author)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  One reason for doing so is to make clear where we are headed; the Tower of Hanoi problem is one that is not solved in one go – several steps are needed before a satisfactory solution is found. Another reason is to illustrate how difficult it can be to understand why a correct solution has been found if no information about the solution method is provided. 8.1 S P E C I F I C AT I O N A N D S O L U T I O N 8.1.1 The End of the World! The Tower of Hanoi problem comes from a puzzle marketed in 1883 by the French mathematician ´ Edouard Lucas, under the pseudonym M. Claus. The puzzle is based on a legend according to which there is a temple in Brahma where there are three giant poles fixed in the ground. On the first of these poles, at the time of the world’s creation, God placed 64 golden discs, each of different size, in decreasing order of size (see Figure 8.1). The monks were given the task of moving the discs, one per day, from one pole to another according to the rule that no disc may ever be above a smaller disc. 148 ALGORITHMIC PROBLEM SOLVING The monks’ task would be complete when they succeeded in moving all the discs from the first of the poles to the second and, on the day that they completed their task, the world would come to an end! Figure 8.1: Tower of Hanoi problem. 8.1.2 Iterative Solution There is a very easy solution to the Tower of Hanoi problem that is easy to remember and easy to execute. To formulate the solution, we assume that the poles are arranged at the three corners of a triangle. Movements of the discs can then be succinctly described as either clockwise or anticlockwise movements. We assume that the problem is to move all the discs from one pole to the next in a clockwise direction. We also assume that days are numbered from 0 onwards. On day 0, the discs are placed in their initial position and the monks begin moving the discs on day 1. With these assumptions, the solution is the following.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Algorithms and Data Structures in C++

  • Alan Parker(Author)
  • 2018(Publication Date)
  • Routledge

    (Publisher)

  B, may be used to store discs during the transfer. The discs have to be moved under the following condition: at no time may a disc on a peg have a wider disc above it on the same peg. As long as the condition is met all three pegs may be used to complete the transfer. For example the problem may be solved for the case of three by the following move sequence:

  ( A , C )   ,   ( A , B )   , ( C , B )   ,   ( A , C )   ,   ( B , A )   ,   ( B , C )   ,   ( A , C )

  (2.24)

  where the ordered pair, (x, y), indicates to take a disk from peg x and place it on peg y.

  FIGURE 2.1

  Tower of Hanoi Problem

  The problem admits a nice recursive solution. The problem is solved in terms of n by noting that to move n discs from A to C one can move n − 1 discs from A to B move the remaining disc from A to C and then move the n − 1 discs from B to C. This results in the relation for the number of steps, S (n), required for size n as

  S ( n ) = 2 S ( n − 1 ) + 1

  (2.25)

  with the boundary conditions

  S ( 1 ) = 1 S ( 2 ) = 3

  (2.26)

  Eq. 2.25 admits a solution of the form

  S ( n ) = A 2 n + B

  (2.27)

  and matching the boundary conditions in Eq. 2.26 one obtains

  S ( n ) = 2 n − 1

  (2.28)

  A growing field of interest is the visualization of algorithms. For instance, one might want to animate the solution to the Tower of Hanoi problem. Each disc move results in a new picture in the animation. If one is to incorporate the pictures into a document then a suitable language for its representation is PostScript1 . This format is supported by almost all word processors and as a result is encountered frequently. A program to create the PostScript® description of the Tower of Hanoi is shown in Code List 2.6 The program creates an encapsulated postscript file shown in Code List 2.7 . The word processor used to generate this book took the output of the program in Code List 2.7 and imported it to yield Figure 2.1

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Algorithms

  A Practical Approach to Computer Algorithms Using Python and C#

  • Rod Stephens(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  Trying to solve the puzzle with a grand plan can be confusing, but there is a simple recursive solution. Instead of trying to think of solving the problem as a whole, you can reduce the problem size and then recursively solve the rest of the problem. The following pseudocode uses this approach to provide a simple recursive solution:

  // Move the top n disks from peg from_peg to peg to_peg // using other_peg to hold disks temporarily as needed. TowerOfHanoi(Peg: from_peg, Peg: to_peg, Peg: other_peg, Integer: n) // Recursively move the top n - 1 disks from from_peg to other_peg. If (n > 1) Then TowerOfHanoi(from_peg, other_peg, to_peg, n - 1) // Move the last disk from from_peg to to_peg. <Move the top disk from from_peg to to_peg.> // Recursively move the top n - 1 disks back // from other_peg to to_peg. If (n > 1) Then TowerOfHanoi(other_peg, to_peg, from_peg, n - 1) End TowerOfHanoi

  The first step requires faith in the algorithm that seems to beg the question of how the algorithm works. That step moves the top disks from the original peg to the peg that isn't the destination peg. It does this by recursively calling the TowerOfHanoi algorithm. At this point, how can you know that the algorithm works and can handle the smaller problem?

  The answer is that the method recursively calls itself repeatedly if needed to move smaller and smaller stacks of disks. At some point in the sequence of recursive calls, the algorithm is called to move only a single disk. Then the algorithm doesn't call itself recursively. It simply moves the disk and returns.

  The key is that each recursive call is used to solve a smaller problem. Eventually, the problem size is so small that the algorithm can solve it without calling itself recursively. As each recursive call returns, the algorithm's calling instance moves a single disk and then calls itself recursively again to move the smaller stack of disks to its final destination peg. Figure 9.4

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Foundations of Combinatorics with Applications

  • Edward A. Bender, S. Gill Williamson(Authors)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  ] .

  People have studied the Tower of Hanoi puzzle with the same rules but with more than one extra pole for a total of k > 3 poles. The optimal strategy is not known; however, it is known that if H n (k ) is the least number of moves required, then log2 H n (k ) ~ (n (k - 2 )!)1

  /(k -

  2 ) [ 1 ] .

  Divide and conquer methods are discussed in books that teach algorithm design ; however, little has been written on general design strategies. Some of our discussion is based on the article by Smith [ 5 ] .

  1

  Xiao Chen and Jian Shen, On the Frame-Stewart conjecture about the Towers of Hanoi, SIAM J. Compute. 33 (2004) 584-589.

  2

  Daniel I.A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley (1978).

  3

  Ronald L. Graham, Bruce L. Rothschild and Joel H. Spencer, Ramsey Theory, 2nded., John Wiley (1990).

  4

  Eric Roberts, Thinking Recursively, John Wiley (1986).

  5

  Douglas R. Smith, Applications of a strategy for designing divide-and-conquer algorithms, Science of Computer Programming 8 (1987), 213-229.

  6

  S. Gill Williamson, Combinatorics for Computer Science, Dover (2002).

  Passage contains an image

  CHAPTER 8

  Sorting Theory

  Introduction

  The problem of developing and implementing good sorting algorithms has been extensively studied. If you’ve taken a programming course, you have probably seen code for specific sorting algorithms. You may have programmed various sorting algorithms. Our focus will be different, emphasizing the general framework over the specific implementations. We’ll also look at “sorting networks” which are a type of hardware implementation of certain sorting algorithms.

  In the last section, we’ll explore the “divide and conquer” technique. The major aspect of this technique is the recursive approach to problems.  

  Before discussing sorting methods, we’ll need a general framework for thinking about the subject. Thus we’ll look briefly at how sorting algorithms can be classified. All of them involve making comparisons, require some sort of storage medium for the list and must be physically implemented in some fashion. We can partially classify algorithms according to how these things are handled.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Programming Fundamentals Using JAVA

  A Game Application Approach

  • William McAllister, S. Jane Fritz(Authors)
  • 2021(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  fromTower . This effectively swaps roles of the extra tower and the starting tower during this invocation of the method.

  When the method hanoi is invoked, and line 12 detects the base case (the value passed to nRings is 1), the output produced by lines 14–15 includes the names of the towers passed to the method’s first and second parameters fromTower and toTower . This ensures that when the invocations on lines 20 and 23 degenerate to the base case, the values of the first and second arguments passed to the method will be included in the base case’s output (lines 14–15).

  Figure 9.11The application TowersOfHanoi .

  Figure 9.12The output produced by the application TowersOfHanoi .

  9.5 PROBLEMS WITH RECURSION

  Because only a small percentage of the population has an innate ability to think recursively, most of us need to be trained in how to discover and implement recursive algorithms. To a certain extent, the discovery and implementation process can be methodized, but a good deal of effort is necessary to become a good recursive programmer.

  Another problem with recursion is that applications that use recursive algorithms tend to run more slowly. If two versions of the same application were developed, one that used a recursive algorithm and one that used a non-recursive algorithm, the non-recursive version would typically run faster. The difference in speed is due to the manner in which modern computer systems transfer execution to, and return from, an invoked method and the larger number of method invocations that recursive algorithms typically perform by repeatedly invoking themselves.

  Every time a method is invoked, whether or not it is recursive, the runtime environment has to suspend the execution of the program to perform tasks associated with the invocation. Typically, these tasks include allocating the memory for the invoked method’s parameters and local variables and transferring the value of the arguments into these parameters. Not only does this take time, but each method invocation requires additional RAM memory for the storage of the method’s parameters and local variables.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Programming Essentials Using Java

  A Game Application Approach

  • William McAllister, S. Jane Fritz(Authors)
  • 2017(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  fromTower . This effectively swaps roles of the extra tower and the starting tower during this invocation of the method.

  When the method hanoi is invoked, and line 12 detects the base case (the value passed to nRings is 1), the output produced by lines 14–15 includes the names of the towers passed to the method’s first and second parameters fromTower and toTower . This ensures that when the invocations on lines 20 and 23 degenerate to the base case, the values of the first and second arguments passed to the method will be included in the base case’s output (lines 14–15).

  9.5   PROBLEMS WITH RECURSION

  Because only a small percentage of the population has an innate ability to think recursively, most of us need to be trained in how to discover and implement recursive algorithms. To a certain extent, the discovery and implementation process can be methodized, but a good deal of effort is necessary to become a good recursive programmer.

  Another problem with recursion is that applications that use recursive algorithms tend to run more slowly. If two versions of the same application were developed, one that used a recursive algorithm and one that used a non-recursive algorithm, the non-recursive version would typically run faster. The difference in speed is due to the manner in which modern computer systems transfer execution to, and return from, an invoked method and the larger number of method invocations that recursive algorithms typically perform by repeatedly invoking themselves.

  Every time a method is invoked, whether or not it is recursive, the runtime environment has to suspend the execution of the program to perform tasks associated with the invocation. Typically, these tasks include allocating the memory for the invoked method’s parameters and local variables and transferring the value of the arguments into these parameters. Not only does this take time, but each method invocation requires additional RAM memory for the storage of the method’s parameters and local variables.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Psychology of Thinking

  Reasoning, Decision-Making and Problem-Solving

  • John Paul Minda(Author)
  • 2020(Publication Date)
  • SAGE Publications Ltd

    (Publisher)

  In cases where the solution to the problem requires first working towards a goal and then working away from the goal, this heuristic will fail to find a good solution. As an example, consider the well-known puzzle problem called the “Tower of Hanoi” (also known as the “tower problem”). In the simplest version of this puzzle, the problem-solver is presented with three discs of three different sizes stacked on one peg. The goal is to re-create the tower on another peg. Figure 10.4 shows an example. In this case, the initial state is as shown, with the tower built on one peg. The goal state is shown on the lower right, with the tower built on the rightmost peg. There are two given constraints in solving this problem. The first is that you can only move one disc at a time. The second is that you can never place a larger disc on top of a smaller disc. Figure 10.4 shows a series of intermediate steps. One of the intermediate steps shows either the smallest or the medium disc on the rightmost peg. This is the peg that will eventually contain the goal state tower. In order to continue with solving this problem, the smaller discs are first moved onto the goal peg and then moved off the goal peg in a subsequent stage in order to obey the constraints of the task and make room for the largest peg, which is the base of the tower. The step seems to move away from the goal state. A strictly defined hill-climbing heuristic would have difficulty with this move because it requires moving away from the goal state. As such, hill climbing must be supplemented or replaced with another strategy. Figure 10.4 The classic “Tower of Hanoi” problem is a simple example of a problem that benefits from means end analysis, or the propensity to form subgoals. Means end analysis The simple example with the Tower of Hanoi suggests the need for an alternative way to reduce the problem space

  Sign up to read

  Learn more about book