Back to main page
Get the source code

The soloution by Adam Moorhouse is based on ideas similar to the above solution. The author enumerates the poles from 1 to 3. Here is an explanation of the solution in the authors own words (the original code is in C++, but here we present the Java equivalent):

   static void hanoi(int height)
   {
      final double log2 = Math.log(2);

      for( int move = 1; move < (1 << height) ; move++) 
      {
         // The piece moved is the most significant bit changed 
         // when we go from  to .  This can be found
         // by taking the log (base 2) of (  xor  ) 
         // rounding down, and adding one. */
              
         int piece = (int)( Math.log( move ^ ( move - 1 )) / log2 )  + 1;

         // Our  has moved a number of times equal to the bits
         // beyond (more significant than) the 'th bit. So it
         // has moved move >> piece (right shift) times.  The direction
         // depends on if is even or odd.  Here, odd pieces decrement and
         // even ones increment. */
	      
         int from Pole = ( move >> piece ) * ( piece % 2 == 0 ? 1 : -1 ) % 3;
         int toPole = ( from + (piece % 2 == 0 ? 1 : -1)) % 3;

         //  is simply one step further in the right direction. 
         // Sadly, modular division (on my compiler) doesn't return the 
         // least residue, so I have to add this cheesy fix.
         fromPole  = (from +3) % 3;
	 toPole = (to + 3) % 3;
         moveDisk( (char)(from+65), (char)(to+65));
      }
   }

Back to main page
Get the source code