Fonseca 1

Armando Fonseca

Professor Richard Glass

CMP 207

March 18, 2008

The Tower of Hanoi

The Legend is about some priests in the temple of Brahma. They were given a puzzle consisting of a golden platform with three diamond needles on which were placed sixty-four golden disks. The priests were to move one disk per day. Following these rules, once the priests are finished, the legend claims that world will end!(NyHoff 538).

            The Tower of Hanoi puzzle, invented in 1883 by the French mathematician Edouard Lucas, has become a classic example in the analysis of algorithms and discrete mathematical structures. The puzzle consists of n discs, no two of the same size, stacked on three vertical pegs, in such a way that no disc lies on top of a smaller disc. A permissible move is to take the top disc from one of the pegs and move it to one of the other pegs, as long as it is not placed on top of a smaller disc(Romik 1).

            An easy solution is the recursive way. The procedure for moving a tower of h disks from a peg I onto a peg J, with K being the remaining third peg:

·  If h >1 move the h-1 smaller disks from peg I to peg K.

·  Now the largest disk, i.e. disk h-1 can be moved from peg I to peg J.

·  If h>1 then again use this procedure to move the h-1 smaller disks from peg K to peg J(Lewis and Chase 324).

Works Cited

Lewis, John and joseph Chase.    Java Software Structures. Reading: Pearson Education, 2005.

Nyhoff, Larry.  ADTs,Data Structures and Problem Solving with C++. Reading: Pearson-Prentice Hall, 2005.

Romik, Dan. “Shortest paths in the Tower of Hanoi graph and    finite automata.” SIAM Journal on Discrete Mathematics.2006. EBSCO Databases. Academic Search Premier. Nassau Community College Lib., Garden City, New York. 13 March, 2008 Host Research < http://search.ebscohost.com>

 

 

 

 

                                                                            

Write a program that will solve the problem for 4 disks and 3 pegs.

//********************************************************************
//  TowersOfHanoi.java       
//  
//  Represents the classic Towers of Hanoi puzzle.
//
//  This code was base in the example of Lewis and chase in their 
//  book: "Java Software Structures"
//
//********************************************************************

public class TowersOfHanoi {
   private int totalDisks;   // total disks playing in the towers
   
   public TowersOfHanoi ( ) {
     this.totalDisks = 0;
   }

   //-----------------------------------------------------------------
   //  Sets up the puzzle with the specified number of disks.
   //-----------------------------------------------------------------
   public TowersOfHanoi ( int disks )  {
      this.totalDisks = disks ;
      this.solve ( ) ;
   }
   
   // MUTATOR:
   public void setTotalDisks ( int totalDisks ) {
     this.totalDisks = ( 0 <= totalDisks ) ? totalDisks : 0 ;
   }

   //ACCESSOR:
   public int getTotalDisks ( ) {
     return this.totalDisks ;
   }

   //-----------------------------------------------------------------
   //  Performs the initial call to moveTower to solve the puzzle.
   //  Moves the disks from tower 1 to tower 3 using tower 2.
   //-----------------------------------------------------------------
   public void solve ( ) {
      this.moveTower ( this.getTotalDisks ( ) , 1 , 3 , 2 ) ;
   }
   
   //-----------------------------------------------------------------
   //  Moves the specified number of disks from one tower to another
   //  by moving a subtower of n-1 disks out of the way, moving one
   //  disk, then moving the subtower back. Base case of 1 disk.
   //-----------------------------------------------------------------
   private void moveTower ( int numDisks, int start, int end, int temp ) {
      if ( 1 == numDisks ) {
         this.moveOneDisk ( start , end ) ;
      }
      else {
        this.moveTower ( numDisks-1, start , temp , end ) ;
        this.moveOneDisk ( start , end ) ;
        this.moveTower (numDisks-1, temp, end, start);
      }
   }

   //-----------------------------------------------------------------
   //  Prints instructions to move one disk from the specified start
   //  tower to the specified end tower.
   //-----------------------------------------------------------------
   private void moveOneDisk ( int start , int end ) {
      System.out.println ( "Move one disk from " + start + " to " + end ) ;
   }

   public static void main ( String args [ ] ) {
      TowersOfHanoi hanoi = new TowersOfHanoi ( 4 );

   }
}

 Create your own educational wiki!HelpPublic, not yet premium Privacy Policy RSS