“Towers of Hanoi”: Radix 6 Number Solution

Java implementation by Apostolos Syropoulos

We first give the pseudocode that solves the puzzle, adapted from the original code of Gault and Clint:

int N; /* Tower's height */ if ( N % 2 != 0 ) /* N is odd */ { n = N-1; ba = 4; ac = 5; cb = 0; m = 6; } else /* N is even */ { n = N-2; ba = 134; ac = 69; cb = 73; m = 216; } while ( n > 2 ) { n--; ab = (ac * 6 + 1) * m + cb; ca = (cb * 6 + 2) * m + ba; bc = (ba * 6 + 3) * m + ac; m = m * m * 6; n--; ba = (bc * 6 + 4) * m + ca; ac = (ab * 6 + 5) * m + bc; cb = ca * 6 * m + ab; m = m * m * 6;; } if ( n == 2 ) { n--; ab = (ac * 6 + 1) * m + cb; bc = (ba * 6 + 3) * m + ac; m = m * m * 6; } if ( n == 1 ) { ac = (ab * 6 + 5) * m + bc; } printSolution(ac);

It is not immediately evident but this algorithm needs a BigNumber facility in order to operate properly. So, our Java program makes use of the BigInteger class. Since, readers may not familiar with this relatively new class, we give the following code snipet demostrates the basic operations one may perform with BigIntegers.

BigInteger a, b, c; a = new BigInteger("3"); b = new BigInteger("7"); c = new BigInteger("10"); a = b.multiply(new BigInteger("10").add(c)); System.out.println(a.toString());

The first 3 lines after the declaration initialize the vaious variables. The fourth line multiplies b by by the sum of 10 plus c. The last line shows how one can print a BigIntegerâ€•simply by transforming it to a String.