“Towers of Hanoi”: French Solution
Java implementation by Apostolos Syropoulos

The French solution is given in the form of pseudo-code in [4]. The code shown below is an adaption of that code to Java:

PEG x, y, z; boolean current_even, previous_even; x = B; y = C; z = A; previous_even = "n is even"; for (i=1; i<=(Math.pow(2, n)-1); i++) { current_even = "the rightmost 1 in the binary representation of i has an even index"; if (current_even) { swap(y, z); } else if (!current_even && previous_even) { swap(x, z); } else if (current_even && !previous_even) { swap(x, z); swap(y, z); } move(x, y); previous_even = current_even; }

The first problem we must tackle is a way to determine whether the rightmost 1 in the binary representation of i has an even index. Let's suppose we have at our disposal Si, then its i-th element is the index of the rightmost 1 in the binary representation of i. Computing Si is not difficult, if we think that the elements of Si are symmetric, i.e., there is a middle element at position m and for any k, elements at positions m-k and m+k are equal. Using this remark we can easily derive the following code:

S[0] = 0; S[1] = 1; for (i=2; i <= height; i++) { middle = (int)Math.pow(2, i-1); S[middle] = i; for (j=middle+1; j <= 2*middle-1; j++) { S[j] = S[j-middle]; } }

The rest of the pseudo-code can be straightforward implemented in Java. The only problem may a way to determine whether an integer is even or odd. We can simply check the expression i mod 2, if it is equal to zero, then i is even, otherwise it is odd. The following Java code does the job:

(i % 2 == 0) ? true : false

Back to main page
Get the source code