tower of hanoi problem solving psychology

Tower of Hanoi: Surprising Lessons From a Classic Puzzle

A cognitive analysis demonstrates its power..

Posted February 22, 2021

The Tower of Hanoi puzzle is exactly the type of artificial, laboratory-based task that my Naturalistic Decision Making (NDM) community has avoided. There is no expertise. No context, no uncertainty.

And yet, several decades ago, I did a small study of how people actually try to solve the Tower of Hanoi puzzle. This essay is the first time I am telling that story.

Why did I do that study? Greed.

I had been included as a sub-contractor on a larger effort to develop a cognitive test battery for railroad engineers and others to detect signs of impairment, such as alcohol or drug use or lack of sleep (O’Donnell et al., 2004). Once the project was underway, the program manager steered it in a different direction than I was expecting, and there was little need for my company's involvement. However, the program manager was still obligated to fulfill the financial commitment to bring us on board. But what could we add?

The manager had decided to use the Tower of Hanoi puzzle as part of this cognitive test battery and hit upon the idea that I could do a cognitive task analysis of how people did the task. He rejected all of my alternative suggestions. So it was either study the Tower of Hanoi puzzle or wave goodbye to $25,000.

With severe misgivings, I decided to give it a shot.

However, after agreeing, I ran into a big problem. I had no intention of doing these interviews on such an artificial task, and I couldn’t find anyone on my technical staff who would do it either. So I turned my attention to other efforts.

Then, as the cognitive test battery project was ending, the program manager reminded me of this Tower of Hanoi deliverable that I had never even started to work on. Fortunately, my company had very recently hired a new research assistant, Andrew Mills. I called Andy into my office and told him that I had the perfect training project to help him come up to speed at doing cognitive interviews: He could do cognitive interviews with the Tower of Hanoi puzzle under my supervision.

Andy enthusiastically agreed.

Of course, after our meeting, Andy told other people in the company about this arrangement, and they told him that "Gary has finally found his sucker." So Andy’s excitement was considerably reduced when he started on this project.

For those unfamiliar with the Tower of Hanoi puzzle, the diagram below shows three pegs. Your task is to move all the doughnut-shaped disks from the peg on the left, we’ll call it Peg A, to the peg on the right, Peg C. You move the disks one at a time. You can never put a larger disk on a smaller one. The task is difficult, and it gets harder the more disks you start with on Peg A.

Here I suggest that before you read further in this essay, you go online and attempt the puzzle yourself, so you can see how it works. Try the MathIsFun site. And see if you can get up to five or six disks.

Andy and I agreed that he would interview seven people in my company, one at a time. He’d watch them doing the task and ask them to talk out loud, so he knew what they were trying to do. He could inject questions if he was unsure how they were making decisions.

Andy expected that everyone would solve the puzzle in the same way—the way he solved it. To his surprise, no two people used the same strategy. And some were better than others. Some could only do four or five rings, while others could manage seven or eight or nine rings.

With the seven interviews completed, it was time to review our findings—from Andy’s notes.

Our first discovery: The primary decision people wrestled with was where to move the top disk in a stack. Once you moved that disk, the rest of the sequence followed pretty naturally, and you built what we called an "interim tower." And then you had the same decision—where to move the top disk of that interim tower.

Our second discovery was that to solve the puzzle, you had to build interim towers—partial towers on other pegs. Also, the people in our sample relied on mental simulation: "If I move this disk there, then the next disk goes there…" and so on. This mental simulation tactic wasn’t a real discovery because we assumed as much from our own experience with the game. Simon (1975) refers to these interim towers as pyramids, and describes the approach as a goal recursion strategy.

The third discovery, not really a discovery because it was already well-known in the literature, was that the strategy created a major difficulty—keeping track of the disks as you did the mental simulation. That tactic chewed up working memory and differentiated the people who could handle a lot of disks versus those who could only do a few. See Kotovsky, Hayes & Simon (1985) for a masterful analysis of the memory requirements for different versions of the Tower of Hanoi problem.

Our fourth discovery was that even when people were solving the puzzle successfully, they often felt they were doing it wrong! The only way to solve the puzzle was to build interim towers on the different pegs, but people would say, “This can’t be right. I’m building this tower on the wrong peg, not the peg I want all the rings to wind up on.” Therefore, we could see that people didn’t have a good mental model of how these interim towers played out. We also noted that even when performance is successful, it doesn't mean that the person really understands what s/he is doing.

Our fifth discovery was that there was a simple strategy that pretty much eliminated the memory struggles. You start at the bottom, not the top! Here’s how it works. If all the disks are on Peg A at the left, and you need to move them all to Peg C on the right, then you need to move the bottom disk, the largest one, to Peg C. Obviously.

To do that, you need to build an interim tower on Peg B with the next largest disk at the bottom. And to do that, you need to build an interim tower on Peg C with the next largest disk. And so forth. You still need to do some analysis, but the memory burden is greatly reduced, and so are the errors.

You might want to go back to the Tower of Hanoi website and try the puzzle using this bottom-up strategy.

Our takeaway from this project was that by studying the cognitive challenges of the task, we could make a series of discoveries about what were the key decisions people faced, what made the task difficult, and what were the weaknesses in their mental models. Plus, a bonus discovery of the bottom-up strategy.

As far as we can tell, no one has previously reported any of these five discoveries.

If a cognitive perspective can yield so many discoveries for a puzzle that has been around for over a century, imagine the payoff for new tasks and requirements.

O’Donnell, R.D., Moise, M., & Schmidt, R. (2004). Comprehensive Computerized Cognitive Assessment Battery. Final Report for the Office of Naval Research under contract N00140-01-M-0064.

Simon, H.A. (1975). The functional equivalence of problem solving skills. Cognitive Psychology, 7, 268-288.

Kotovsky, K., Hayes, J.R., & Simon, H.A. (1985). Why are some problems hard? Evidence from Tower of Hanoi. Cognitive Psychology, 17, 248-294.

Gary Klein, Ph.D., is a senior scientist at MacroCognition LLC. His most recent book is Seeing What Others Don't: The remarkable ways we gain insights.

• Find a Therapist
• Find a Treatment Center
• Find a Psychiatrist
• Find a Support Group
• Find Online Therapy
• United States
• Brooklyn, NY
• Chicago, IL
• Houston, TX
• Los Angeles, CA
• New York, NY
• Portland, OR
• San Diego, CA
• San Francisco, CA
• Seattle, WA
• Washington, DC
• Asperger's
• Bipolar Disorder
• Chronic Pain
• Eating Disorders
• Passive Aggression
• Personality
• Goal Setting
• Positive Psychology
• Stopping Smoking
• Low Sexual Desire
• Relationships
• Child Development
• Therapy Center NEW
• Diagnosis Dictionary
• Types of Therapy

Understanding what emotional intelligence looks like and the steps needed to improve it could light a path to a more emotionally adept world.

• Emotional Intelligence
• Gaslighting
• Affective Forecasting
• Neuroscience

Tower of Hanoi

• Configuration

The Tower of Hanoi is a popular mathematical puzzle which requires players to find a strategy to move a pile o disks from one tower to another one while following certain constraints: Only the upper disk can be moved and no disk may be placed on top of a smaller disk.

The game is frequently used in psychological research on problem solving, for example to study developmental progression in children and adolescents (Byrnes & Spitz, 1979). Since problem solving falls into the class of executive functions, the Tower of Hanoi task is also used in neuropsychology to assess cognitive deficits correlated with frontal lobe activity or impairment (Yochim et al., 2009). The task is considered to be a non-insight problem that follows a means-end analysis approach (Gilhooly & Murphy, 2007). Learning effects seem to include a procedural memory component (Davis & Klebe, 2001).

Publications

Byrnes, M. M. & Spitz, H.H. (1979). Developmental progression of performance on the Tower of Hanoi problem. Bulletin of the Psychonomic Society, Vol 14 (5), 379-381.

Davis, HP, Klebe, KJ (2001). A longitudinal study of the performance of the elderly and the young on the Tower of Hanoi Puzzle and Rey Recall. Brain and Cognition, Vol 46, 95–99.

Gilhooly, K.J & Murphy, P. (2007). Differentiating insight from non-insight problems, Thinking & Reasoning, 11:3, 279-302, DOI: 10.1080/13546780442000187.

Yochim, B.P., Baldo, J.V., Kane, K.D., Delis, D.C. (2009). D-KEFS Tower Test performance in patients with lateral prefrontal cortex lesions: the importance of error monitoring. J Clin Exp Neuropsychol, 31(6), 658-63.

https://en.wikipedia.org/wiki/Tower_of_Hanoi https://en.wikipedia.org/wiki/Planning_(cognitive) https://en.wikibooks.org/wiki/Cognitive_Psychology_and_Cognitive_Neuroscience/Problem_Solving_from_an_Evolutionary_Perspective

Experiment Design

Task characteristics.

• Number of Disks 2-7
• Max Time (optional)
• Feedback Error, Rule Violation, Timeout
• Status Display # moves, Elapsed Time

Configuration Options

7.3 Problem-Solving

Learning objectives.

By the end of this section, you will be able to:

• Describe problem solving strategies
• Define algorithm and heuristic
• Explain some common roadblocks to effective problem solving

   People face problems every day—usually, multiple problems throughout the day. Sometimes these problems are straightforward: To double a recipe for pizza dough, for example, all that is required is that each ingredient in the recipe be doubled. Sometimes, however, the problems we encounter are more complex. For example, say you have a work deadline, and you must mail a printed copy of a report to your supervisor by the end of the business day. The report is time-sensitive and must be sent overnight. You finished the report last night, but your printer will not work today. What should you do? First, you need to identify the problem and then apply a strategy for solving the problem.

The study of human and animal problem solving processes has provided much insight toward the understanding of our conscious experience and led to advancements in computer science and artificial intelligence. Essentially much of cognitive science today represents studies of how we consciously and unconsciously make decisions and solve problems. For instance, when encountered with a large amount of information, how do we go about making decisions about the most efficient way of sorting and analyzing all the information in order to find what you are looking for as in visual search paradigms in cognitive psychology. Or in a situation where a piece of machinery is not working properly, how do we go about organizing how to address the issue and understand what the cause of the problem might be. How do we sort the procedures that will be needed and focus attention on what is important in order to solve problems efficiently. Within this section we will discuss some of these issues and examine processes related to human, animal and computer problem solving.

PROBLEM-SOLVING STRATEGIES

   When people are presented with a problem—whether it is a complex mathematical problem or a broken printer, how do you solve it? Before finding a solution to the problem, the problem must first be clearly identified. After that, one of many problem solving strategies can be applied, hopefully resulting in a solution.

Problems themselves can be classified into two different categories known as ill-defined and well-defined problems (Schacter, 2009). Ill-defined problems represent issues that do not have clear goals, solution paths, or expected solutions whereas well-defined problems have specific goals, clearly defined solutions, and clear expected solutions. Problem solving often incorporates pragmatics (logical reasoning) and semantics (interpretation of meanings behind the problem), and also in many cases require abstract thinking and creativity in order to find novel solutions. Within psychology, problem solving refers to a motivational drive for reading a definite “goal” from a present situation or condition that is either not moving toward that goal, is distant from it, or requires more complex logical analysis for finding a missing description of conditions or steps toward that goal. Processes relating to problem solving include problem finding also known as problem analysis, problem shaping where the organization of the problem occurs, generating alternative strategies, implementation of attempted solutions, and verification of the selected solution. Various methods of studying problem solving exist within the field of psychology including introspection, behavior analysis and behaviorism, simulation, computer modeling, and experimentation.

A problem-solving strategy is a plan of action used to find a solution. Different strategies have different action plans associated with them (table below). For example, a well-known strategy is trial and error. The old adage, “If at first you don’t succeed, try, try again” describes trial and error. In terms of your broken printer, you could try checking the ink levels, and if that doesn’t work, you could check to make sure the paper tray isn’t jammed. Or maybe the printer isn’t actually connected to your laptop. When using trial and error, you would continue to try different solutions until you solved your problem. Although trial and error is not typically one of the most time-efficient strategies, it is a commonly used one.

   Another type of strategy is an algorithm. An algorithm is a problem-solving formula that provides you with step-by-step instructions used to achieve a desired outcome (Kahneman, 2011). You can think of an algorithm as a recipe with highly detailed instructions that produce the same result every time they are performed. Algorithms are used frequently in our everyday lives, especially in computer science. When you run a search on the Internet, search engines like Google use algorithms to decide which entries will appear first in your list of results. Facebook also uses algorithms to decide which posts to display on your newsfeed. Can you identify other situations in which algorithms are used?

A heuristic is another type of problem solving strategy. While an algorithm must be followed exactly to produce a correct result, a heuristic is a general problem-solving framework (Tversky & Kahneman, 1974). You can think of these as mental shortcuts that are used to solve problems. A “rule of thumb” is an example of a heuristic. Such a rule saves the person time and energy when making a decision, but despite its time-saving characteristics, it is not always the best method for making a rational decision. Different types of heuristics are used in different types of situations, but the impulse to use a heuristic occurs when one of five conditions is met (Pratkanis, 1989):

• When one is faced with too much information
• When the time to make a decision is limited
• When the decision to be made is unimportant
• When there is access to very little information to use in making the decision
• When an appropriate heuristic happens to come to mind in the same moment

Working backwards is a useful heuristic in which you begin solving the problem by focusing on the end result. Consider this example: You live in Washington, D.C. and have been invited to a wedding at 4 PM on Saturday in Philadelphia. Knowing that Interstate 95 tends to back up any day of the week, you need to plan your route and time your departure accordingly. If you want to be at the wedding service by 3:30 PM, and it takes 2.5 hours to get to Philadelphia without traffic, what time should you leave your house? You use the working backwards heuristic to plan the events of your day on a regular basis, probably without even thinking about it.

Another useful heuristic is the practice of accomplishing a large goal or task by breaking it into a series of smaller steps. Students often use this common method to complete a large research project or long essay for school. For example, students typically brainstorm, develop a thesis or main topic, research the chosen topic, organize their information into an outline, write a rough draft, revise and edit the rough draft, develop a final draft, organize the references list, and proofread their work before turning in the project. The large task becomes less overwhelming when it is broken down into a series of small steps.

Further problem solving strategies have been identified (listed below) that incorporate flexible and creative thinking in order to reach solutions efficiently.

Additional Problem Solving Strategies :

• Abstraction – refers to solving the problem within a model of the situation before applying it to reality.
• Analogy – is using a solution that solves a similar problem.
• Brainstorming – refers to collecting an analyzing a large amount of solutions, especially within a group of people, to combine the solutions and developing them until an optimal solution is reached.
• Divide and conquer – breaking down large complex problems into smaller more manageable problems.
• Hypothesis testing – method used in experimentation where an assumption about what would happen in response to manipulating an independent variable is made, and analysis of the affects of the manipulation are made and compared to the original hypothesis.
• Lateral thinking – approaching problems indirectly and creatively by viewing the problem in a new and unusual light.
• Means-ends analysis – choosing and analyzing an action at a series of smaller steps to move closer to the goal.
• Method of focal objects – putting seemingly non-matching characteristics of different procedures together to make something new that will get you closer to the goal.
• Morphological analysis – analyzing the outputs of and interactions of many pieces that together make up a whole system.
• Proof – trying to prove that a problem cannot be solved. Where the proof fails becomes the starting point or solving the problem.
• Reduction – adapting the problem to be as similar problems where a solution exists.
• Research – using existing knowledge or solutions to similar problems to solve the problem.
• Root cause analysis – trying to identify the cause of the problem.

The strategies listed above outline a short summary of methods we use in working toward solutions and also demonstrate how the mind works when being faced with barriers preventing goals to be reached.

One example of means-end analysis can be found by using the Tower of Hanoi paradigm . This paradigm can be modeled as a word problems as demonstrated by the Missionary-Cannibal Problem :

Missionary-Cannibal Problem

Three missionaries and three cannibals are on one side of a river and need to cross to the other side. The only means of crossing is a boat, and the boat can only hold two people at a time. Your goal is to devise a set of moves that will transport all six of the people across the river, being in mind the following constraint: The number of cannibals can never exceed the number of missionaries in any location. Remember that someone will have to also row that boat back across each time.

Hint : At one point in your solution, you will have to send more people back to the original side than you just sent to the destination.

The actual Tower of Hanoi problem consists of three rods sitting vertically on a base with a number of disks of different sizes that can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top making a conical shape. The objective of the puzzle is to move the entire stack to another rod obeying the following rules:

• 1. Only one disk can be moved at a time.
• 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
• 3. No disc may be placed on top of a smaller disk.

  Figure 7.02. Steps for solving the Tower of Hanoi in the minimum number of moves when there are 3 disks.

Figure 7.03. Graphical representation of nodes (circles) and moves (lines) of Tower of Hanoi.

The Tower of Hanoi is a frequently used psychological technique to study problem solving and procedure analysis. A variation of the Tower of Hanoi known as the Tower of London has been developed which has been an important tool in the neuropsychological diagnosis of executive function disorders and their treatment.

GESTALT PSYCHOLOGY AND PROBLEM SOLVING

As you may recall from the sensation and perception chapter, Gestalt psychology describes whole patterns, forms and configurations of perception and cognition such as closure, good continuation, and figure-ground. In addition to patterns of perception, Wolfgang Kohler, a German Gestalt psychologist traveled to the Spanish island of Tenerife in order to study animals behavior and problem solving in the anthropoid ape.

As an interesting side note to Kohler’s studies of chimp problem solving, Dr. Ronald Ley, professor of psychology at State University of New York provides evidence in his book A Whisper of Espionage  (1990) suggesting that while collecting data for what would later be his book  The Mentality of Apes (1925) on Tenerife in the Canary Islands between 1914 and 1920, Kohler was additionally an active spy for the German government alerting Germany to ships that were sailing around the Canary Islands. Ley suggests his investigations in England, Germany and elsewhere in Europe confirm that Kohler had served in the German military by building, maintaining and operating a concealed radio that contributed to Germany’s war effort acting as a strategic outpost in the Canary Islands that could monitor naval military activity approaching the north African coast.

While trapped on the island over the course of World War 1, Kohler applied Gestalt principles to animal perception in order to understand how they solve problems. He recognized that the apes on the islands also perceive relations between stimuli and the environment in Gestalt patterns and understand these patterns as wholes as opposed to pieces that make up a whole. Kohler based his theories of animal intelligence on the ability to understand relations between stimuli, and spent much of his time while trapped on the island investigation what he described as  insight , the sudden perception of useful or proper relations. In order to study insight in animals, Kohler would present problems to chimpanzee’s by hanging some banana’s or some kind of food so it was suspended higher than the apes could reach. Within the room, Kohler would arrange a variety of boxes, sticks or other tools the chimpanzees could use by combining in patterns or organizing in a way that would allow them to obtain the food (Kohler & Winter, 1925).

While viewing the chimpanzee’s, Kohler noticed one chimp that was more efficient at solving problems than some of the others. The chimp, named Sultan, was able to use long poles to reach through bars and organize objects in specific patterns to obtain food or other desirables that were originally out of reach. In order to study insight within these chimps, Kohler would remove objects from the room to systematically make the food more difficult to obtain. As the story goes, after removing many of the objects Sultan was used to using to obtain the food, he sat down ad sulked for a while, and then suddenly got up going over to two poles lying on the ground. Without hesitation Sultan put one pole inside the end of the other creating a longer pole that he could use to obtain the food demonstrating an ideal example of what Kohler described as insight. In another situation, Sultan discovered how to stand on a box to reach a banana that was suspended from the rafters illustrating Sultan’s perception of relations and the importance of insight in problem solving.

Grande (another chimp in the group studied by Kohler) builds a three-box structure to reach the bananas, while Sultan watches from the ground.  Insight , sometimes referred to as an “Ah-ha” experience, was the term Kohler used for the sudden perception of useful relations among objects during problem solving (Kohler, 1927; Radvansky & Ashcraft, 2013).

Solving puzzles.

   Problem-solving abilities can improve with practice. Many people challenge themselves every day with puzzles and other mental exercises to sharpen their problem-solving skills. Sudoku puzzles appear daily in most newspapers. Typically, a sudoku puzzle is a 9×9 grid. The simple sudoku below (see figure) is a 4×4 grid. To solve the puzzle, fill in the empty boxes with a single digit: 1, 2, 3, or 4. Here are the rules: The numbers must total 10 in each bolded box, each row, and each column; however, each digit can only appear once in a bolded box, row, and column. Time yourself as you solve this puzzle and compare your time with a classmate.

How long did it take you to solve this sudoku puzzle? (You can see the answer at the end of this section.)

   Here is another popular type of puzzle (figure below) that challenges your spatial reasoning skills. Connect all nine dots with four connecting straight lines without lifting your pencil from the paper:

Did you figure it out? (The answer is at the end of this section.) Once you understand how to crack this puzzle, you won’t forget.

   Take a look at the “Puzzling Scales” logic puzzle below (figure below). Sam Loyd, a well-known puzzle master, created and refined countless puzzles throughout his lifetime (Cyclopedia of Puzzles, n.d.).

What steps did you take to solve this puzzle? You can read the solution at the end of this section.

Pitfalls to problem solving.

   Not all problems are successfully solved, however. What challenges stop us from successfully solving a problem? Albert Einstein once said, “Insanity is doing the same thing over and over again and expecting a different result.” Imagine a person in a room that has four doorways. One doorway that has always been open in the past is now locked. The person, accustomed to exiting the room by that particular doorway, keeps trying to get out through the same doorway even though the other three doorways are open. The person is stuck—but she just needs to go to another doorway, instead of trying to get out through the locked doorway. A mental set is where you persist in approaching a problem in a way that has worked in the past but is clearly not working now.

Functional fixedness is a type of mental set where you cannot perceive an object being used for something other than what it was designed for. During the Apollo 13 mission to the moon, NASA engineers at Mission Control had to overcome functional fixedness to save the lives of the astronauts aboard the spacecraft. An explosion in a module of the spacecraft damaged multiple systems. The astronauts were in danger of being poisoned by rising levels of carbon dioxide because of problems with the carbon dioxide filters. The engineers found a way for the astronauts to use spare plastic bags, tape, and air hoses to create a makeshift air filter, which saved the lives of the astronauts.

   Researchers have investigated whether functional fixedness is affected by culture. In one experiment, individuals from the Shuar group in Ecuador were asked to use an object for a purpose other than that for which the object was originally intended. For example, the participants were told a story about a bear and a rabbit that were separated by a river and asked to select among various objects, including a spoon, a cup, erasers, and so on, to help the animals. The spoon was the only object long enough to span the imaginary river, but if the spoon was presented in a way that reflected its normal usage, it took participants longer to choose the spoon to solve the problem. (German & Barrett, 2005). The researchers wanted to know if exposure to highly specialized tools, as occurs with individuals in industrialized nations, affects their ability to transcend functional fixedness. It was determined that functional fixedness is experienced in both industrialized and nonindustrialized cultures (German & Barrett, 2005).

In order to make good decisions, we use our knowledge and our reasoning. Often, this knowledge and reasoning is sound and solid. Sometimes, however, we are swayed by biases or by others manipulating a situation. For example, let’s say you and three friends wanted to rent a house and had a combined target budget of $1,600. The realtor shows you only very run-down houses for $1,600 and then shows you a very nice house for $2,000. Might you ask each person to pay more in rent to get the $2,000 home? Why would the realtor show you the run-down houses and the nice house? The realtor may be challenging your anchoring bias. An anchoring bias occurs when you focus on one piece of information when making a decision or solving a problem. In this case, you’re so focused on the amount of money you are willing to spend that you may not recognize what kinds of houses are available at that price point.

The confirmation bias is the tendency to focus on information that confirms your existing beliefs. For example, if you think that your professor is not very nice, you notice all of the instances of rude behavior exhibited by the professor while ignoring the countless pleasant interactions he is involved in on a daily basis. Hindsight bias leads you to believe that the event you just experienced was predictable, even though it really wasn’t. In other words, you knew all along that things would turn out the way they did. Representative bias describes a faulty way of thinking, in which you unintentionally stereotype someone or something; for example, you may assume that your professors spend their free time reading books and engaging in intellectual conversation, because the idea of them spending their time playing volleyball or visiting an amusement park does not fit in with your stereotypes of professors.

Finally, the availability heuristic is a heuristic in which you make a decision based on an example, information, or recent experience that is that readily available to you, even though it may not be the best example to inform your decision . Biases tend to “preserve that which is already established—to maintain our preexisting knowledge, beliefs, attitudes, and hypotheses” (Aronson, 1995; Kahneman, 2011). These biases are summarized in the table below.

Were you able to determine how many marbles are needed to balance the scales in the figure below? You need nine. Were you able to solve the problems in the figures above? Here are the answers.

   Many different strategies exist for solving problems. Typical strategies include trial and error, applying algorithms, and using heuristics. To solve a large, complicated problem, it often helps to break the problem into smaller steps that can be accomplished individually, leading to an overall solution. Roadblocks to problem solving include a mental set, functional fixedness, and various biases that can cloud decision making skills.

References:

Openstax Psychology text by Kathryn Dumper, William Jenkins, Arlene Lacombe, Marilyn Lovett and Marion Perlmutter licensed under CC BY v4.0. https://openstax.org/details/books/psychology

Review Questions:

1. A specific formula for solving a problem is called ________.

a. an algorithm

b. a heuristic

c. a mental set

d. trial and error

2. Solving the Tower of Hanoi problem tends to utilize a  ________ strategy of problem solving.

a. divide and conquer

b. means-end analysis

d. experiment

3. A mental shortcut in the form of a general problem-solving framework is called ________.

4. Which type of bias involves becoming fixated on a single trait of a problem?

a. anchoring bias

b. confirmation bias

c. representative bias

d. availability bias

5. Which type of bias involves relying on a false stereotype to make a decision?

6. Wolfgang Kohler analyzed behavior of chimpanzees by applying Gestalt principles to describe ________.

a. social adjustment

b. student load payment options

c. emotional learning

d. insight learning

7. ________ is a type of mental set where you cannot perceive an object being used for something other than what it was designed for.

a. functional fixedness

c. working memory

Critical Thinking Questions:

1. What is functional fixedness and how can overcoming it help you solve problems?

2. How does an algorithm save you time and energy when solving a problem?

Personal Application Question:

1. Which type of bias do you recognize in your own decision making processes? How has this bias affected how you’ve made decisions in the past and how can you use your awareness of it to improve your decisions making skills in the future?

anchoring bias

availability heuristic

confirmation bias

functional fixedness

hindsight bias

problem-solving strategy

representative bias

trial and error

working backwards

Answers to Exercises

algorithm:  problem-solving strategy characterized by a specific set of instructions

anchoring bias:  faulty heuristic in which you fixate on a single aspect of a problem to find a solution

availability heuristic:  faulty heuristic in which you make a decision based on information readily available to you

confirmation bias:  faulty heuristic in which you focus on information that confirms your beliefs

functional fixedness:  inability to see an object as useful for any other use other than the one for which it was intended

heuristic:  mental shortcut that saves time when solving a problem

hindsight bias:  belief that the event just experienced was predictable, even though it really wasn’t

mental set:  continually using an old solution to a problem without results

problem-solving strategy:  method for solving problems

representative bias:  faulty heuristic in which you stereotype someone or something without a valid basis for your judgment

trial and error:  problem-solving strategy in which multiple solutions are attempted until the correct one is found

working backwards:  heuristic in which you begin to solve a problem by focusing on the end result

Share This Book

• Increase Font Size

Tower of Hanoi

Introduction

About this implementation, run the demo, data output file, further reading.

The Tower of Hanoi puzzle is a classic in studying planning in children and adults (see references) .

In this puzzle, participants need to move discs from the left peg to the right peg (see image on the right). There are two constraints;

Larger discs are not allowed to be placed on smaller discs.

Discs shall be moved one at the time.

In this example, there are three pegs with only three discs. These three discs can be moved to the goal in as little as seven steps.

In this experiment, each "trial" is actually just one step. After each move by the participant, the time used so far as well as the total steps is save.

Click here to run a demo of the Tower of Hanoi task

Meaning of the columns in the output datafile. You need this information for your data analysis.

The PsyToolkit code zip file

Byrnes, M.M. & Spitz, H.H. (1979). Developmental progression of performance on the Tower of Hanoi problem. Bulletin of the Psychonomic Society, 14 (5) , 379-381. (Publisher link)

Davis, H.P., Klebe, K.J. (2001). A longitudinal study of the performance of the elderly and the young on the Tower of Hanoi Puzzle and Rey Recall. Brain and Cognition, 46 , 95-99. (Publisher link)

Schiff, R. & Vakil, E. (2015). Age differences in cognitive skill learning, retention and transfer: The case of the Tower of Hanoi Puzzle. Learning and Individual Differences, 39 , 164-171. (Publisher link)

• Subscriber Services
• For Authors
• Publications
• Archaeology
• Art & Architecture
• Bilingual dictionaries
• Classical studies
• Encyclopedias
• English Dictionaries and Thesauri
• Language reference
• Linguistics
• Media studies
• Medicine and health
• Names studies
• Performing arts
• Science and technology
• Social sciences
• Society and culture
• Overview Pages
• Subject Reference
• English Dictionaries
• Bilingual Dictionaries

Recently viewed (0)

• Save Search
• Share This Facebook LinkedIn Twitter

Related Content

Related overviews.

difference equation

problem solving

More Like This

Show all results sharing these subjects:

• Mathematics and Computer Science

Tower of Hanoi

Quick reference.

A logical puzzle, frequently studied in cognitive psychology and used as a test of problem-solving ability, consisting of three pegs, on one of which are placed a number of discs of varying diameter, the largest at the bottom and the smallest at the top (see illustration). The problem is to move the tower of disks over to one of the other pegs in the smallest number of moves, moving one disc at a time and using the third peg as a temporary way station as required, and never placing a larger disc on top of a smaller one. The puzzle is of ancient (possibly Indian) origin but was rediscovered by the French mathematician Edouard Lucas (1842–91) and marketed as a toy in 1883. Lucas proved that, for any number n of discs, the minimum number of moves is given by the formula 2 n − 1. Hence 3 discs can be transferred in 7 moves, 4 discs in 15 moves, 5 discs in 31 moves, and so on. See also General Problem Solver. [So called because of its supposed resemblance to a certain type of Vietnamese building, Lucas's toy having been described as a simplified version of the Tower of Brahma, which was said to contain 64 gold discs, and which would therefore require a minimum of 2 64 − 1 (more than 18 billion billion) moves to solve]

From:   Tower of Hanoi   in  A Dictionary of Psychology »

Subjects: Science and technology — Mathematics and Computer Science

Related content in Oxford Reference

Reference entries, tower of hanoi n., towers of hanoi.

View all related items in Oxford Reference »

Search for: 'Tower of Hanoi' in Oxford Reference »

• Oxford University Press

PRINTED FROM OXFORD REFERENCE (www.oxfordreference.com). (c) Copyright Oxford University Press, 2023. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single entry from a reference work in OR for personal use (for details see Privacy Policy and Legal Notice ).

date: 04 May 2024

• Cookie Policy
• Privacy Policy
• Legal Notice
• Accessibility
• [66.249.64.20|185.80.150.64]
• 185.80.150.64

Character limit 500 /500

Plus.Maths.org

The Tower of Hanoi: Where maths meets psychology

The Tower of Hanoi.

Mathematicians and psychologists don't cross paths that often and when they do you wouldn't expect it to involve an (apparently) unassuming puzzle like the Tower of Hanoi. Yet, the puzzle holds fascination in both fields. In psychology it helps to assess someone's cognitive abilities. In maths it displays a wealth of beautiful features and leads you straight to surprisingly tricky questions that still haven't been answered.

The rules of the game are straight-forward. You've got three pegs and a number of discs (eight of them in the original version), stacked up on one of the pegs in order of size, with the biggest disc at the bottom. Your task is to transfer the whole tower onto a different peg, disc by disc, but you're not allowed to ever place a larger disc onto a smaller one.

The mathematician Andreas M. Hinz is someone who has looked at the game from both the mathematical and the psychological angle. He is about to publish a book about the Tower and he has collaborated with psychologists to produce a new tool for assessing patients. He explains that it's the game's simplicity that makes it so interesting to psychologists. "The game is easy to explain and you can watch people think," he says. "[Test persons] make the moves in front of the experimenter and so one can see every step, every single strategy the person tries. That's why psychologists like it so much."

The game lends itself particularly to assessing people's ability to plan ahead and to chop a task into more digestible chunks: to move the whole tower you first need to move the tip of it, and the same rules apply to this sub-problem. It's also easy to vary the problem: you can add more discs or you can stipulate new starting and final configurations that don't have all the discs stacked up on one peg. It turns out that both of these features, the game's recursive nature and its variability, lead to some very interesting maths too.

The game plan

The best way to see the scope of the game is to draw a network, or graph , that displays all the possible configurations and moves. Suppose we play the game with three discs and three pegs. Label the discs 1, 2 and 3 with 1 being the smallest one and 3 the largest one. Also label the pegs 1, 2 and 3. Now suppose discs 1 and 3 are on peg 1 and disc 2 is on peg 3. You can encode this situation using the triple (1,3,1). The positions in the triple correspond to the discs and the value in a position tells you which peg the corresponding disc is sitting on. There's no confusion about the order in which discs sit on a given peg because we know that they have to be arranged in order of size. So all the legal configurations of discs can be encoded unambiguously in triples of numbers.

Connecting the dots.

Now for each triple draw a dot on a piece of paper. Connect two dots if a single move can get you from one of them to the other. For example, the dot corresponding to the starting position (1,1,1) (all discs on peg 1) is joined to the dots corresponding to positions (2,1,1) (disc 1 on peg 2 and the rest still on peg 1) and (3,1,1) (disc 1 on peg 3 and the rest still on peg 1). Altogether there are 3 3 =27 possible positions. These can be arranged to give you the following graph:

The Hanoi graph H 3 .

This object is called a Hanoi graph and it's denoted by H 3 . The subscript 3 indicates that we are looking at a game with three discs.

The Hanoi graph makes it easy to keep track of how someone is playing the game. "The main reasons why psychologists were so enthusiastic about the Hanoi graph is that you can draw the [sequence of moves] the test person has followed on it," explains Hinz. "You can easily see whether the person has made the best moves or, if not, where they had problems, at which stages they were thinking for a long time, etc. So you can get a lot of information from the result of a test on one person, or even a group if you overlay their traces on the graph."

Playing the game with three discs is easy, so what can we say about the game with 4, 5, 6 or any number n of discs? In terms of the graphs a very pretty picture emerges: the Hanoi graph H 4 for the four-disc version of the game consists of three copies of H 3 each connected to each of the other two by exactly one edge.

The Hanoi graph H 4 consists of three copies of H 3 . Click here for a larger version of the image.

Similarly, H 5 consists of three copies of H 4 , H 6 consists of three copies of H 5 and so on. This is due to the recursive nature of the game: if you ignore the biggest disc, the n +1-disc version of the puzzle turns into the n -disc version. Say for example that you have four discs and that the biggest one, disc 4, is sitting on peg 1. Any legal move you can make with the remaining three discs is also a legal move in the three-disc version you get by pretending disc 4 isn't there. So if you look at the nodes in H 4 that correspond to disc 4 sitting on peg 1 (these are the nodes whose labels end in a 1) what you see is a copy of H 3 . Similarly, you get a copy of H 3 for the nodes which have disc 4 sitting on peg 2 and another copy for the nodes with disc 4 sitting on peg 3.

How do you move between these copies? You can only ever move disc 4 when the other three discs are all stacked up on one of the other two pegs. There are two nodes representing this situation in each copy of H 3 (one for each of the other two pegs the remaining discs can be stacked up on) and from each you get an edge to one of the other two copies (representing the move of disc 4 ). So the copies are linked pairwise by one edge. The same argument works to show that H n +1 consists of three copies of H n for any number n of discs.

Andreas M. Hinz introducing his book, The Tower of Hanoi — Myths and Maths , at the European Congress of Mathematics in Krakow in July 2012.

Adding ever more discs to the puzzle doesn't actually make it much more difficult once you have cracked the method for solving it. But things change when you stipulate that the game should start and end not with all discs sitting in a tower on one peg, but with different arrangements of discs. "In this case the puzzle becomes pretty hard," says Hinz. "Psychologists use this variation in tests, but its structure was not very well understood by them. [We helped them] with this mathematical model of a graph, which can be analysed mathematically."

For example, using graphs you can see immediately that no matter which starting and finishing configurations you stipulate, it is always possible to solve the puzzle, no matter how many discs there are. This is because, as you can easily deduce from the recursive structure, each Hanoi graph H n is connected : there's a path between any two of its nodes.

Triangle connections

For mathematicians the possibility of adding discs poses another intriguing question. What can we say about the graph for a hypothetical game with an infinite number of discs? Well, have a look at the image below.

Sierpiński's triangle.

This is Sierpiński's triangle, which you get from another infinite process. You start with a (filled-in) equilateral triangle and remove the middle (up-side down) triangle you get from connecting the mid-points of the three sides (you only remove the inside of that triangle, leaving behind the sides). You're left with three equilateral triangles and again remove the centre triangle from each of them, leaving you with 9 triangles. Keep going, always removing centre triangles from what's left, ad infinitum. The object you get in the limit is Sierpiński's triangle.

As you add more and more discs to the Tower of Hanoi game, the corresponding graph, suitably rescaled, starts to look more and more like Sierpiński's triangle. And the object you get in the limit as n tends to infinity has exactly the same structure as Sierpiński's triangle.

There is an equally intriguing connection to another triangle beloved by mathematicians: Pascal's triangle. (We won't define it here, if you have not come across it, there is a good explanation here .) If you take the first 2 n rows of Pascal's triangle and connect odd numbers that lie next to each other, either horizontally or diagonally, by a line, then the graph you get has exactly the same structure as the Hanoi graph H n .

The first eight rows of Pascal's triangle with adjacent odd entries connected.

These kind of connections aren't only beautiful, they are also useful. Results that are hard to prove for one of these objects may be easier to prove for another and can then be transferred. For example, suppose you travel around Sierpiński's triangle, but without ever leaving the fractal itself. What's the average distance between two points? No-one had been able to answer this question until Hinz calculated it using Hanoi graphs: it's 466/885 (assuming that the side-length of the initial triangle in the construction of Sierpiński's triangle is 1).

Adding pegs

So much for adding discs, but what happens if you introduce another peg? The game itself becomes easier because you have more scope for moving discs around. But the graphs also lose their neat structure. There are now more configurations of discs that allow you to move the largest disc — the smaller ones no longer need to be stacked up on one peg. This means that the chunk of the graph that has the largest disc sitting on peg 1, say, and the chunk that has it sitting on peg 2 are connected by more edges than just one. This makes the graphs more complex. "For four pegs the graphs are usually not planar anymore," explains Hinz. "This means you cannot draw them on a sheet of paper [without the edges crossing]. You need three dimensions for that. We still do not understand these graphs very well because they are strongly intertwined."

Hinz with the co-authors of his book. From left to right: Ciril Petr, Andreas M. Hinz, Sandi Klavžar, and Uros Milutinović.

This complexity means that seemingly simple questions can be surprisingly hard to solve. For example, nobody knows how long the shortest solution is for the classical finishing and starting configurations. There are strategies for solving the multi-peg puzzle and the notorious Frame-Stewart conjecture says that these are optimal. But although the conjecture is over 70 years old the problem is still undecided. It has been proved, with the aid of computers, only for games with up to 30 discs.

Hinz is a mathematical physicist by trade, but his fascination with the Tower of Hanoi has been an interesting diversion. "The collaborations with people from graph theory, who are my co-authors on the book, and with psychologists have been fascinating," he says. The assessment tool he produced with psychologists is now being used, for example to test people with dementia or who have suffered stroke, to see which areas of the brain have been impaired.

But it's not all about usefulness. "The mathematician Ian Stewart once said that people are intrigued by maths because it is fun, it is beautiful and it is useful," says Hinz. "But I would like to add a fourth point: people like maths because it is surprising." As a mathematical object the Tower of Hanoi certainly fits the bill on all four points.

Further reading

You can find a list of Hinz's publications on the Tower of Hanoi here . The book The Tower of Hanoi — Myths and Maths by A.M. Hinz, S. Klavžar, U. Milutinović and C. Petr will be published by Birkhäuser in January 2013. For more information and links, see the book's website .

About the author

Marianne Freiberger is Editor of Plus . She interviewed Andreas M. Hinz at the European Congress of Mathematics in Krakow in July 2012.

• Add new comment

Broken link?

The link to the proof for the fewest number of moves -- "(Try to work this out for yourself, or see the proof here.)" -- is not working. It leads to a page that says 'access denied.'

Link fixed now - Thanks

The collaborations with

The collaborations with people from graph theory, who are my co-authors on the book, and with psychologists have been fascinating," he says. http://www.incrediblemotivation.com/spbcThe assessment tool he produced with psychologists is now being used, for example to test people with dementia or who have suffered stroke, to see which areas of the brain have been impaired.

The book is available since 31st January 2013

http://link.springer.com/book/10.1007/978-3-0348-0237-6/page/1 http://www.amazon.de/The-Tower-Hanoi-Myths-Maths/dp/3034802366 http://www.amazon.com/The-Tower-Hanoi-Myths-Maths/dp/3034802366

"(3,1,1) (disc 1 on peg 3 and the rest still on peg 3)" should be: "(3,1,1) (disc 1 on peg 3 and the rest still on peg 1)"

Thanks for pointing that out!

Thanks for pointing that out! We've fixed it.

Towers of Hanoi

my dad (actuary) and I (journeyman maths student) looked at this in 1950s.... we thought the rule was: even disks left odd disks right additional "modulus arithmetic" tuition about going around to the other side seemed cool and simple..... graph theory is also cool but harder for pre-highschool "student" (soi-dis)

Bob "A" [email protected]

Love this article and love the resulting book chapter in the IMA's "50 Visions of Mathematics" book. Such a neat idea - to frame the problem using graph theory and the fractal stuff is the icing on the cake!

The Frame-Stewart conjecture

In 2014 Thierry Bousch published a solution to The Reve`s puzzle (four pegs version). His article is here http://bit.ly/rvspzl2014 and an English rendering of Bousch’s approach appears here http://bit.ly/tohbook2ed . Just recently there appeared a flawed article in DMAA claiming a proof of the Frame-Stewart conjecture, but a group of authors wrote http://bit.ly/FSCnote , so the FSC with five or more pegs remains an open problem.

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Computer science theory

Course: computer science theory   >   unit 1, towers of hanoi.

• Move three disks in Towers of Hanoi
• Towers of Hanoi, continued
• Challenge: Solve Hanoi recursively
• You may move only one disk at a time.
• No disk may ever rest atop a smaller disk. For example, if disk 3 is on a peg, then all disks below disk 3 must have numbers greater than 3.

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page