Hanoi Tower problem

The origin of the tower of Hanoi problem

It's said that in the ancient temple of India , There is one called the Hanoi Tower (Hanoi) The game of . The game is on a copper device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate . The goal of the game ： hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules ： Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .

Thought analysis

If there is only one disc, move the disc directly from the initial column to the target column

The number of discs is 2 Move the small disc to the auxiliary column, and then move the large disc to the target column

If you have any n Disc We can put this n A disc is regarded as 2 A plate —— The bottom plate and all the upper plates
（1） The above n-1 A disk moves to B column （ here A The column is the initial column ,B The column is the target column ,C Columns are auxiliary columns ）
（2） Move the lowest disc to the target column （ here A The column is the initial column ,C The column is the target column ,B Columns are auxiliary columns ）
（3） Move all disks on the auxiliary column to the target disk （ here B The column is the initial column ,C The column is the target column ,A Columns are auxiliary columns ）

public class HanoiTower {
    

    public static void main(String[] args) {
    
        hanoiTower(4,'A','B','C');
    }

    /** * * @param num  Number of discs  * @param a  Starting column  * @param b  Auxiliary column  * @param c  Target column  */
    public static void hanoiTower(int num,char a,char b,char c){
    
        /* If there is only one disc, the disc can be directly removed from a The column moves to c column */
        if (num == 1){
    
            System.out.println(" The first 1 A disk from  " + a + "->" + c);
        }else{
    
            /* The number of discs is greater than 1*/
            /* First move all the disks above to from A Move to B column  C Columns as auxiliary columns */
            hanoiTower(num-1,a,c,b);
            /* Move the bottom disk to C column */
            System.out.println(" The first "+num+" A disk from  " + a + "->" + c);
            /* hold B The disc on the column moves to C column  A Columns are auxiliary columns */
            hanoiTower(num-1,b,a,c);
        }
    }
}

Running results

 The first 1 A disk from  A->B
 The first 2 A disk from  A->C
 The first 1 A disk from  B->C
 The first 3 A disk from  A->B
 The first 1 A disk from  C->A
 The first 2 A disk from  C->B
 The first 1 A disk from  A->B
 The first 4 A disk from  A->C
 The first 1 A disk from  B->C
 The first 2 A disk from  B->A
 The first 1 A disk from  C->A
 The first 3 A disk from  B->C
 The first 1 A disk from  A->B
 The first 2 A disk from  A->C
 The first 1 A disk from  B->C

Process finished with exit code 0