Tower of Hanoi

Rules

This is a simple puzzle, containing n disks of different sizes and 3 poles. The objective of the puzzle is to move the entire stack from the starting pole to the goal pole, obeying the following simple 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 i.e. a disk can only be moved if it is the uppermost disk on a stack. (3) No disk may be placed on top of a smaller disk.

The Legend

A romantic legend manufactured by Edouard Lucas as an accompaniment to the popular game he invented, the Tower of Hanoi. According to the tale of the Tower of Brahma, in the Indian city of Benares, beneath a dome that marked the center of the world, is to be found a brass plate in which are set three diamond needles, ”each a cubit high and as thick as the body of a bee.” Brahma placed 64 disks of pure gold on one of these needles at the time of Creation. Each disk is a different size, and each is placed so that it rests on top of another disk of greater size, with the largest resting on the brass plate at the bottom and the smallest at the top. Within the temple are priests whose job it is to transfer all the gold disks from their original needle to one of the others, without ever moving more than one disk at a time. No priest can ever place any disk on top of a smaller one, or anywhere else except on one of the needles. When the task is done, and all 64 disks have been successfully transferred to another needle, ”tower, temple, and Brahmins alike will crumble into dust, and with a thunder-clap the world will vanish.” The pre- diction (thunder-clap aside) seems fairly safe given that the number of steps required to transfer all the disks is 2 64 − 1, which is approximately 1.8447 ∗ 10 19 . Assuming one second per move, this would take about five times longer than the current age of the universe!
(Source: http://www.daviddarling.info/encyclopedia/T/Tower_of_Brahma.html)

In the following is a short description of two paradigms which were experimented on.

Mental representation 1 - Object perspective

When undergoing the Think Aloud experiment with the Object-oriented programming paradigm (using the language Java) subjects firstly set up the internal representation of the problem space using programmable objects. Afterwards, some form of graph theory was implemented - stable states were identified (positions of disks on poles) and moves between them. As the problem space was set up, some search algorithm (usually depth search) was executed over the problem graph, that produced the end solution. Solutions obtained this way were sub-optimal, but the physical representation was very clear and though the code was long (mean: 120 lines of code) and it took long time (average: 2.8
hours) to produce, it was subjectively easily readable.

Mental representation 2 - Logic perspective

When undergoing the same experiment with the Logic programming paradigm (using the language Prolog), the initial process of designing the code took longer, but the whole programming process was concluded in a much shorter time. The idea subjects used here was double recursion (to move unwanted disks away) and a move of the desired disk. This procedure produces an optimal solution in an shorter period of time (average: 28 minutes) and with less written code (mean: 22 lines of code) compared to the Object oriented programming paradigm, however the code is subjectively much harder to read.

Example of solutions

For better understanding, two Java implementations are following, one for each representation used.

Object-oriented programming paradigm

Logic programming paradigm

public class TowerOfHanoi
{
   List<Pole> poles;
   Set<List<Pole>> visited = new Set<>();
   List<Move> movesTaken;

   public List<Pole> init()
   {
       Disk d1, d2, d3 = new Disk();
       Pole p1, p2, p3 = new Pole();
       d1.size = 1;
       d2.size = 2;
       d3.size = 3;
       p1.disks.add(d3);
       p1.disks.add(d2);
       p1.disks.add(d1);
       return new List<Pole>() {p1, p2, p3};
   }

   public List<Move> movesAvailable()
   {
       List<Move> available = new List<>();
       // Check each pole
       for (pole : this.poles)
       {
           if (! pole.isEmpty())
           {
               Disk d = pole.disks.getLast()
               List remainingPoles = poles.copy().remove(pole);
               for (endPole : remainingPoles)
               {
                   if (endPole.isEmpty() || endPole.disks.getLast().size > d.size)
                   {
                       Move m = new Move();
                       m.d = d;
                       m.start = pole;
                       m.end = endPole;

                       // Check if already visited state
                       List<Pole> copy = poles.copy();
                       move(copy, m);
                       boolean already = false;
                       for (v : visited)
                       {
                           if (copy.equals(v))
                               already = true;
                       }
                       if (! already)
                           available.add(m);
                   }
               }
           }
       }
       return available;
   }

   public void move(List<Pole> state, Move m)
   {
       for (pole : state)
       {
           if (pole == m.start)
              pole.remove(m.d);
           if (pole == m.end)
              pole.add(m.d);
       }
   }

   public boolean endState()
   {
       return poles.p3.equals(new List<Disk>() {d3, d2, d1};);
   }

   public static List<Move> main()
   {
       init();
       movesTaken = new List<Move>();
       while (! endState())
       {
            Move m = movesAvailable().getFirst();
            visited.add(poles.copy());
            move(poles, m);
            movesTaken.add(m);
       }
       return movesTaken;
   }

   public class Disk
   {
      int size;
   }
   public class Pole
   {
      List<Disk> disks = new List<>();
   }

   public class Move
   {
      Disk d;
      Pole start;
      Pole end;
   }

}

public class MainClass {
   public static void main(String[] args) {
      int nDisks = 3;
      doTowers(nDisks, "A", "B", "C");
   }
   public static void doTowers(int topN, char from, char inter, char to) {
      if (topN == 1) {
         System.out.println("Disk 1 from " + from + " to " + to);
      } else {
         doTowers(topN - 1, from, to, inter);
         System.out.println("Disk " + topN + " from " + from + " to " + to);
         doTowers(topN - 1, inter, from, to);
      }
   }
}