Tower of Hanoi Algorithm
The Tower of Hanoi algorithm is a classic problem-solving technique that involves moving a stack of disks from one peg to another, using a third peg for temporary storage. The algorithm follows a recursive approach, where smaller subproblems are solved to tackle the larger problem. It is often used to illustrate the concept of recursion and is a fundamental example in computer science.
6 Key excerpts on "Tower of Hanoi Algorithm"
eBook - ePubAdvanced 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...
eBook - ePub- Ronald T. Kellogg(Author)
- 2015(Publication Date)
- SAGE Publications, Inc(Publisher)
...It is called the Tower of Hanoi problem. The initial state, at the top of the figures, stacks three disks of different sizes on the first of three pegs, as shown. The problem is to move the disks to the third peg so that they are stacked as shown in the goal state in the lower-right corner of the figure. The only operator here is to move the top disk from one peg onto another peg, with the restriction that it not cover a smaller disk. Each drawing in Figure 9.1 represents a state of the problem space, a legally possible state that might be reached by applying the operator. From State 1, one can move the smallest disk either to Peg 2 or to Peg 3, as shown. Moving it to Peg 2 allows only one possible next move—namely, putting the middle-sized disk on Peg 3. From there, as you can see, two possible moves can be made. To solve the Tower of Hanoi problem, one must find a path through the problem space to progress from the initial state to the goal state. The paths on the left of the figure lead to states removed from the goal. Directed thinking, when applied flawlessly to the problem, would result in the path on the far right, a stepwise progression through seven moves. Figure 9.1 Problem space for the Tower of Hanoi. The goal state is shown in the lower-right corner. SOURCE: Klahr, D., & Kotovsky, K., Complex Information Processing: The Impact of Herbert A. Simon...
eBook - ePub- John R. Anderson(Author)
- 2014(Publication Date)
- Psychology Press(Publisher)
...Simon discussed a number of other ways of solving the problem, some of which do not involve goal stacking. With appropriate instructions, however, one can more or less guarantee that subjects will use goal structures to solve the Tower of Hanoi problem. A number of other researchers (e.g., Egan & Greeno, 1974; Karat, 1982) have found evidence for spontaneous use of hierarchical goal structures in the Tower of Hanoi task. FIG. 6.1. The Tower of Hanoi problem. There are three pegs—A, B, and C—and five disks of different sizes—1, 2, 3, 4, and 5—with holes in their centers so that they can be stacked on the pegs. Initially, the disks are all on Peg A, stacked in a pyramid. The goal is to move all the disks to Peg C. Only the top disk on a peg can be moved, and no disk can ever be placed on top of a smaller disk. 6.2 THE EXPERIMENTAL TASK Twenty-eight subjects were recruited from the Carnegie-Mellon undergraduate population to participate in the experiment. Figure 6.2 illustrates the configurations presented to subjects in the experiment. There were 8 five-disk problems and 8 four-disk problems. All the four-disk problems required a minimum of 2 4 − 1 = 15 moves, and all of the five-disk problems involved 25 -1 = 31 moves. Problems began with either towers or rather flat configurations of disks. There were also two possible types of goal states. Crossing start state with goal state yielded four possible combinations. Two instances were created of each combination for four-disk and five-disk problems. Each subject saw one of the instances of each combination in each difficulty set. Half of the 28 subjects saw four of each set, and the other half saw the other four. The problems were presented in random order...
eBook - ePub- John R. Anderson(Author)
- 2013(Publication Date)
- Psychology Press(Publisher)
...By what sequence of transfers could the monsters have solved this problem? There has been a fair amount of research on the Tower of Hanoi problem (Anzai & Simon, 1979; Cohen & Corkin, 1981; Hayes & Simon, 1974,1977; Karat, 1982; Kotovsky & Fallside, 1988; Kotovsky, Hayes, & Simon, 1985; Newell & Simon, 1972; Simon & Hayes, 1976), although relatively little of it has been focused on predicting the actual sequences of steps that novices make when solving the problem for the first time. Much of this research is concerned with situations where subjects are transferring solutions from earlier problems to later problems, and much of this research is concerned with isomorphs of the Tower of Hanoi problem, such as one presented in Table 5-4. Although interesting, such transfer data are beyond the scope of this chapter. Probably the best systematic investigation of novice steps in Tower of Hanoi is one reported by Kotovsky, Hayes, & Simon (1985) in which they looked at student solutions of problems like the one in Table 5-4 and other isomorphs, including the original Tower of Hanoi problem. They found an interesting characteristic to subjects’ first attempts to solve such problems. Subjects appeared to wander around in the problem space almost randomly at first and were often as far away from a solution as they were at the beginning. Then, suddenly, subjects would execute a sequence of steps that brought them to the goal. This could be characterized as discovering means-ends analysis in the middle of the solution of the first problem. It is possible to map the preceding general discussion of means-ends analysis to a model for Tower of Hanoi. Thus, suppose there is a standard three-peg configuration with disks 1, 2, and 3 on peg A (see Fig. 5-11). There are the direct moves of moving disk 1 to peg B or C. There are also the possibilities of subgoaling moving disks 2 or 3 to pegs B or C. Consider the subgoal of moving disk 3 to peg C...
eBook - ePub- Wayne A. Wickelgren(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
...You can, in fact, state a solution to the general Tower of Hanoi problem in which n disks must be transferred from one spike to another. Thus, any particular Tower of Hanoi problem (a problem involving the transfer of some particular number of disks from one spike to another) is a special case of the general Tower of Hanoi problem. Any two special cases of the general Tower of Hanoi problem are similar problems, though I would hesitate to call them equivalent problems. Similarly, in the nim problem, involving one to five pennies that can be removed at each turn, you can construct a large variety of problems that differ in the maximum number of pennies that may be removed on each turn or the number of pennies originally placed on the table. Each of these problems can be solved by essentially the same problem-solving method, though the specific number of pennies that the player should take on each turn will differ from problem to problem. Again, all of these problems are extremely similar, but not completely equivalent. The preceding two examples of extremely similar problems were examples in which the problems differed only in the quantities of certain elements of the problem. In each case, all of the qualitative or structural characteristics of the problems were identical. Equivalent Difficulty There are other partly analogous problems in which the structure is somewhat different in the two problems being compared but still highly similar. For example, consider the following problem called the fox, goose, corn problem: A man (M), a fox (F), a goose, (G), and some corn (C) are together on one side of the river (straight line) with a boat (B), as illustrated in the given state of Fig. 9-1. The goal is to transfer all of these entities to the other side of the river by means of the boat, which will carry the man and one other entity...
eBook - ePubCognitive Development
Neo-Piagetian Perspectives
- Sergio Morra, Camilla Gobbo, Zopito Marini, Ronald Sheese(Authors)
- 2012(Publication Date)
- Psychology Press(Publisher)
...As the number of disks to be moved increases; thus, the number of subgoals to establish and keep in mind also increases; and, thus, the problem becomes more difficult. The Use of Heuristics in Children’s Problem Solving Klahr and Robinson (1981) studied the development of problem-solving ability focusing on the Tower of Hanoi problem. Earlier studies (Byrnes & Spitz, 1977; Piaget, 1974) showed that only a portion of 6-year-olds succeed in correctly performing even the simplest version of the task involving only two disks and a minimum of three moves. Piaget found that children proceed by trial and error, showing no logical capacity for understanding the task or for planning what moves to make in order to achieve the desired goal. Klahr and Robinson reconsidered this problem not so much to verify the previous results as to learn about the development of strategic behavior in 4- to 6-year-olds, including, for example, planning sequences of moves in advance and formulating subgoals for the purpose of moving toward the goal state. To make the situation more interesting, the problem was presented in the context of a story, and, in addition, some modifications were introduced in the materials and in the display of initial and final states. In place of the disks of decreasing size, cans of increasing height were used, and the children were told that each can represented a different-sized monkey (daddy, mommy, and baby). A series of cans was placed in front of each child (see Fig. 4.2) in the desired final order, and the child was asked to give instructions such that a second series of cans in front of the experimenter would end up in the same arrangement. The described moves were not actually carried out. The restrictions on the moves were identical to those for the standard problem with the exception that to make it more meaningful and simpler for the child it was smaller cans that were not to be placed on larger ones...
