The solution by Glenn C. Rhoads is based on treating the current move number as a bit string and uses bit operations to extract the information in a surprisingly short, efficient, and mysterious manner. The solution assumes that poles are numbered from 0 to 2 and the initial pole is pole number 0. Now, if the current move number is even then the destination pole is pole number 1, else it is pole number 2. Suppose that the variable x holds the current move number, then the destination pole is computed by the expression

and the pole of departute by the expression

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)); } }

The command moveDisk( (char)(from+65), (char)(to+65)); is common to both solutions and it is a simple trick to print A instead of 0, B instead of 1, and C instead of 2.

Back to main page
Get the source code