Musings on why the Towers of Hanoi is hard to comprehend

So we have looked at the recursive solution to the Towers of Hanoi (ToH), and it seems somewhat magical. If you work through the trace line by line, you can see how the problem is in its essence recursive. Then why is the Towers of Hanoi a horrible recursive problem for novices? Towers of Hanoi may not be very appropriate for a novice programmer, because although the problem seems easy, and the solution exudes elegance, trying to explain the solution is far more convoluted.

whatpeoplethinkTOH

Part of the problem lies with the problem itself. It is best illustrated in a tactile manner, so that it can be physically manipulated. It works on paper too, but obviously playing a game is much easier.

Before it’s use as one of the poster-children for recursion, the “Tower of Hanoi” was actually used in experimental psychology. One study from 1962 looked at the effects of verbalization on problem solving [1], or more specifically investigating how acts of verbalizing during problem solving result affected problem solving effectiveness. Here however they refer to the problem as the “three circle problem”, i.e. “the task of transferring discs graduated in size from one circle to another in a triangular configuration of three circles“. This work was based on previous work from 1932 [2], yet is a doppelgänger of the Tower of Hanoi.

The work [2] looked at solving the issue with a variable number of discs, from 3-8, even asking participants to “try and find a general rule by which the problem may be solved“. The authors pose a series of differing trials, some with generalized instructions, others with none. When participants were finished solving 8 discs, they were asked for (i) a general statement of the most efficient way of transferring any number of discs, and (ii) a formula for computing the least number of moves necessary for transferring any number of discs. What was clear from the experiments is that the task, although a tactile one, was difficult for the subjects. Some took upwards of 3 hours, and one participant made nearly 15,000 moves. It was evident that those groups provided with generalized instructions fared better than those with none, who were not even able to formulate a generalization.

Indeed there has been some exploration into why problems like Tower of Hanoi are hard to solve from a problem solving perspective [3]. But why the difficulty? Here are some insights [3]:

  • The problem rules can be a major source of difficulty.
  • Rules consistent with real world knowledge aid problem solving, as does the physical representation in the ToH problem.
  • Intensive training on the rules significantly decreases the difficulty of the problems.
  • Participants cycle through a substantial amount of exploratory behaviour before they reach a point where they can proceed quickly to their goal.

Kotovsky et al. [3] concluded that problems that impose higher processing loads require more training. A problem solver has a limited amount of processing capacity that is easily overloaded by the memory requirements of unfamiliar problem rules. The difficulty in solving the ToH algorithmically is likely grounded in some of the psychological aspects of problem solving. In part it may be the digital nature of how the problem is presented. External representations such as a physical Tower of Hanoi game can serve as memory aids, extending working memory [4]. But external representations, can also be intrinsic to the problem, without them the problem may actually change in nature. They can be used to guide, constrain, and even determine cognitive behaviour [4].

The problem is that ToH, like similar problems can be solved using a physical game, or even on paper, however it is the process of making the solution recursive that is the issue. When solving the problem, people aren’t necessarily doing so using a recursive cognitive process. A computational function is recursive if (and only if), one of its processes is a call to itself. This results in an internal application of the same function, while at the same time keeping whatever it was doing before in memory, creating a chain of deferred functions. While it might be possible to solve the ToH with three discs using working memory, the more discs added to the problem, the harder this becomes.

[1] Gagne, R.M., Smith, Jr., E.C., “A study of the effects of verbalization on problem solving”, Journal of Experimental Psychology, 63(1), pp.12-18 (1962)
[2] Ewert, P.H., Lambert, J.F., “Part II: The effect of verbal instructions upon the formation of a concept”, Journal of General Psychology, 7, pp.400-412 (1932)
[3] Kotovsky, K., Hayes, J.R., Simon, H.A., “Why are some problems hard? Evidence of Tower of Hanoi”, Cognitive Psychology, 17, pp.248-294 (1985)
[4] Zhang, J., “The nature of external representations in problem solving”, Cognitive Science, 21(2), pp.179-217 (1997)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.