Tower of Hanoi: Five Surprising Lessons From a Classic Puzzle

A cognitive analysis demonstrates its power.

Posted Feb 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. 

2015 MathsisFun
Tower of Hanoi example
Source: 2015 MathsisFun

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.

The third discovery 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.

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. 

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.

References

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.