Tower of Hanoi Isomorphs

Problem Solving

The semantics of a representation may be very important in determining the difficulty of the problem. The examples below were used in a User Interface Course given at Brunel University. The original work was by John Hayes of CMU.

The first example is the standard Tower of Hanoi problem. This is followed by two isomorphs of the Tower of Hanoi problem called Monster Problems 2 and 4.

The students started by getting familiar with the Tower of Hanoi problem and then were asked to solve the two Monster problems. They were told the three problems were isomporphs. Most managed to solve Monster 2 and none solved Monster4 in a practical session.

Tower of Hanoi

In Monster Problem 2, there are three five-handed extra-terrestrial monsters standing on three crystal globes. Because of the quantum-mechanical peculiarities of their neighbourhood, both monsters and globes come in exactly three sizes with no others permitted (small, medium, and large). The medium-sized monster was standing on the small globe. The small monster was standing on the large globe. The large monster was standing on the medium-sized globe. Since this situation offended their keenly developed sense of symmetry, they proceeded to transfer themselves from one globe to another so that each monster would have a globe proportionate to his own size. Monster etiquette complicates the solution of the problem since it requires:

1. That only one monster may be transferred at a time.
2. That if two monsters are standing on the same globe, only the larger of the two may be transferred.
3. That a monster may not be transferred to a globe on which a larger monster is standing.

The problem is to find by what sequence of transfers can the monsters arrive on the correct globes.

In Monster Problem 4, three five-handed extra-terrestrial monsters are holding three crystal globes. Because of the quantum-mechanical peculiarities of their neighbourhood, both monsters and globes come in exactly three sizes with no others permitted (small, medium, large). The medium-sized monster is holding the small globe. The small monster is holding the large globe. The large monster is holding the medium-sized globe. Since this situation offended their keenly developed sense of symmetry, they proceeded to shrink and expand themselves so that each monster would have a globe proportionate to his own size. Monster etiquette complicated the solution of the problem since it requires:

1. That only one monster may be changed at a time.
2. That if two monsters have the same size, only the monster holding the larger globe may be changed.
3. That a monster may not be changed to the same size as a monster holding a larger globe.

By what sequence of changes could the monsters have solved this problem.

Monster 2 involves moving things from one place to another, while Monster 4 involves changing the size of things. It is twice as hard to solve Monster 4 than Monster 2 even though the two problems are exact isomorphs.

The student uses a notation to solve the problem. When asked to solve Monster 2 or Monster 4, a notation to describe the sequence of events in the solution of the problem is required. For example, a typical solution to Monster problem 2 might start:

           M   L   S
       0   L   S   M
       1   -  L,S  M
       2   M  L,S  -

A typical solution to Monster problem 4 might start:

           M   L   S
       0   L   S   M
       1   L   L   M
       2   L   L   S

The belief is that people fail to transfer solutions from a problem to its isomorph when the two problems differ in an important way in their semantics. We believe that humans categorise perceptions of the world into (at least) the following six semantic categories:

1. Object
2. Event
3. Location
4. Time
5. Property
6. Action

When corresponding elements in two problem isomorphs belong to different semantic categories, then people will have great difficulty in transferring the solution of one problem to the solution of the other. For example, the categories of corresponding elements in various isomorphs of the Tower of Hanoi problem are:

In consequence, transfer from Tower of Hanoi to Monster Problem number 2 is easy, but that transfer to Monster Problem number 4 is difficult.

This has implications on how the User Interface to a problem should be defined.