Why do the Tower of Hanoi roles change without any visible moves?

Question

While working on the Tower of Hanoi puzzle, I noticed that sometimes the roles of the towers (source, destination, and auxiliary) change, but no disks are moved or printed.

At first, I thought these changes might be due to how Java handles tower positions. I assumed that to move a disk from one tower to another, the towers needed to be next to each other physically. For example, I thought the setup should be something like A B C for moving from tower A to B, not A C B or C B A, with the source always being first and the destination next to it.

Are these role changes just part of the process, or do they actually affect how the algorithm works? Can someone help identify the source of my confusion and explain why these steps happen without any visible moves and how they fit into the overall solution?

Here the algorithm

package Algo;

public class ToursDeHanoi {
    
    public static void hanoi(int n, char source, char destination, char auxiliary) {
        if (n == 1) {
            System.out.println("move le disque 1 de la tour " + source + " à la tour " + destination);
            return;
        }
        
        hanoi(n - 1, source, auxiliary, destination);
      
        System.out.println("move le disque " + n + " de la tour " + source + " à la tour " + destination);

        hanoi(n - 1, auxiliary, destination, source);
    }

    public static void main(String[] args) {
        int n = 3; 
        System.out.println("Solution pour " + n + " disques :");
        hanoi(n, 'A', 'C', 'B');
    }
}

Answer 1

The roles that are currently assigned to the towers, i.e. what you get as function parameters, indicate the roles for moving n "as a whole" from source to destination.

Imagine you have three disks on the first position:

   ▄▄
  ▄▄▄▄
 ▄▄▄▄▄▄
________  ________  ________
   A         B         C

Let's say you want those three disks to be moved to position C. Then you would pass "C" as destination. It is the true destination for those three disks. It is important to be clear what the meaning of this destination is: it is the destination of the three disks together, not the destination of the next move.

But as you are not allowed to move those three in one operation, you recursively solve the problem for moving only the top two disks. And we can see that if we manage to move those two disks to stack B (not C), we are on track to solve the puzzle, as once that is done we can move the largest disk with a valid move to stack C and then solve the problem of moving the two disks at B to C. So for moving the 2 disks we actually want stack B to be the destination. Again, that is the destination for moving those two disks together, not the destination of the next move.

We are not allowed to move those two disks together in one go, so you solve this with recursion where you will move one disk to stack C. Note how stack B and C alternate in their roles for different values of n. This is the base case and so the move can be made. This time the destination (stack C) was really the target of a valid, one-disk move, as n is 1.

So in short, the role that a specific position gets is specific for the given n: it indicates what the destination is to be for all of those top n disks -- as if you could move them in one go. This destination is different when n is different. More precisely, the destination will be the same for a given source, when the value of n is even. It will be the other position for all n that are odd: it alternates.

I hope this explains it.