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.

Game origin

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 A, Band 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.