Tower of Hanoi — Golang version
I recently revisited the movie “Rise of the Planet of the Apes”. In the movie, Caesar played a Tower of Hanoi game. Do you still have any impressions? It is quite difficult to play a few games by myself 😭, today we will use Golang to implement the Tower of Hanoi game.
Legend has it that the person who first invented this problem was the French mathematician Edouard Lucas.
In the holy temple of Benares (in northern India) in the center of the world, three jeweled needles are inserted into a brass plate. When Brahma, the main god of Hinduism, created the world, he wore 64 pieces of gold from the bottom to the top on one of the needles, which is the so-called Tower of Hanoi.
Day or night, there is always a monk moving these pieces of gold according to the following rule: move only one piece at a time, and no matter which needle it is on, the small piece must be on top of the larger piece.
The monks prophesied that when all the gold pieces were moved from the pin Brahma wore to the other pin, the world would be destroyed in a thunderclap, and the Brahma pagoda, temples, and sentient beings would also perish.
There are many variants of this legend, it is unknown who it is, but the mathematical problems left are very classic.
The mathematical knowledge left behind: the relationship between the number of gold pieces and the number of moving steps is
2^n — 1
The number of moves of a gold piece is 2 to the power of 1 minus 1
The number of moves of 2 gold pieces is 2 to the power of 2 minus 1
The number of moves of 3 gold pieces is 2 to the power of 3 minus 1
The number of moves of n pieces of gold is 2 to the nth power minus 1
If the legend is true, the monks need
2^64 — 1steps move to complete this task; Assuming they move one piece of gold per second, it would take 584.9 billion years to complete. The entire universe is only 13.7 billion years old, so it is still early for the universe to be destroyed…
Analysis of game rules
Suppose there are 3 pillars in this game, namely
C. What needs to be moved are the beads, one of which already has N sorted beads, the largest one is at the bottom, the beads are getting smaller and smaller in order, and the other 2 empty columns.
- Only one bead can be moved at a time
- The small beads must be on top of the large beads
The initial state is shown in the figure below
The ultimate goal is to move all the beads on the column to the other column.
As shown below.
- Empty your brain and think about the simplest and most rude solution logic first. Think of the beads as a whole.
- To meet the basic conditions for the large bead to be down, it is definitely necessary to empty the largest bead on
Aand then put the largest bead on the
Ccolumn. Suppose the largest bead number is
- If you want to move to the
Ccolumn, the first step to be realized must be to move all
N-1beads to the
Bcolumn, only in this way the
Nthbead (that is, the largest bead) can be moved to the
- Move the
N-1beads to the
Bcolumn, because the big ones are down and the small ones are up, so the
N-1beads are also ordered on the
- Finally, move the N-1 beads from the B column to the C column to complete the final goal.
Realize the first step: Move N-1 beads on A to B.
Why move N-1 to B first? Because what you finally achieve is to move all the beads from A to C, and the order cannot be changed, only the big ones are on the bottom and the small ones are on the top.
Then you must first move the largest number to C, otherwise, the conditions will not be met. To move the largest bead from A to C, you must vacate the largest bead on A, that is, all the beads above the largest bead must be removed.
And you only have 3 pillars, there must be no other beads on C, otherwise, you will not meet the conditions, all these N-1 beads can only be placed on B, and they are still in order.
The second step moves the Nth bead (the largest bead) on A to C.
This is very simple, just move the largest plate from A to C in one step. As shown below.
The third step moves N-1 beads on B to C.
Reminder: To achieve moving N-1 beads to C, is it to find the largest bead among them, and then move the largest bead first. So the words here actually become repeating steps 1 and 2, find the largest one from the N-1, move to C first, and repeat.
The third step is actually equivalent to changing the requirements. Suppose K = N - 1.There are K beads on column B, column A is empty, column C has the largest bead so for column B with K beads it is equivalent to empty.The first step is to move K-1 beads on B to A.The second step moves the Kth bead on B to C.The third step moves K-1 beads on A to C.
As shown below.
Find the largest of the remaining beads first, in this demo is four. Then move it.
Repeat the above steps in a loop until there is only one bead left, move directly to C, and the game is over.
What is an auxiliary column? Assuming that you now have all the beads to be moved on A, and the goal is to move to C, then B is an auxiliary column for N-1 beads. Because they can only stay here temporarily, otherwise they will not meet the rules of the game.
Here you need to find the auxiliary pillar first, don’t think about how to implement it, first clarify the logic.
To achieve moving from A to B, then C is the auxiliary column.To move from A to C, then B is the auxiliary pillar.To achieve the move from B to C, then A is the auxiliary column.
From the above analysis, we can see that this is actually a cyclic repetitive operation, very similar to recursion, all of which can be implemented using recursion.
To use recursion there are 2 necessary conditions
- Find the recursive formula
- Find the exit conditions
In this game, the exit condition is to move directly to the C-pillar when there is only one bead.
So what is the recursion formula? According to the above logical analysis, it can be decomposed into 3 steps.
- The first step is to move [N-1] plates from A to B
- The second step is to move the [Nth] plate from A to C
- The third step is to move the [remaining N-1] plates from B to C
Below is the pseudo-code of the Golang implementation
Thank you for reading this article, If you think the article is well written, please follow me.
If you find any errors in this article, please leave a message for discussion.
Have a great day.