The Towers of Hanoi Problem

This article discusses the Towers of Hanoi problem, its real-world applications, and possible algorithms for solving it. It explores the use of recursion and iterative algorithms in finding solutions. Find study material and solved assignments on Desklib.

1
THE TOWERS OF HANOI PROBLEM
By
Name
Professor’s Name
Course Number
College/University Name
Street
Date

2
Introduction
In the present world, mathematical ideas and concepts have found numerous applications in peoples’
lives in making decisions and in solving real problems. For example, concepts like calculus and
cryptography have help in solving major world problems. Furthermore, more research on mathematic,
through collaboration in research promote socialization in all corners of the world. Finally, continuous
research on mathematics is important since it trains people to develop abstract thinking as well as
developing a skeptical mindset (Kazak, Wegerif & Fujita, 2015). Moreover, this report is based on a
mathematical problem known as The Towers of Hanoi.
Furthermore, the Tower of Hanoi as a puzzle was developed in 1883 by Edouard Lucas (French
Mathematician) (Grosu, 2015). In addition, he was motivated by a Hindu temple legend in which the
puzzle got shown to young priests. Moreover, it comprises three towers or three pegs with n number
of disks with holes in their centers for stacking to the pegs and disks placed in a manner that one is over
the other (Grosu, 2015). In addition, it is notable that the aim of the game is that the stack is moved to
the subsequent peg by keenly following set simple rules. It is worth noting that in the process no disk
should be placed on top of a smaller disk. In addition, it is notable that there exists a unique solution of
minimum move taking 2n – 1 steps which can be recursively described: for n > 0, then moving a tower of
n – 1disks recursively from first peg to temporary one, and also from initial peg moving disk n to
destination peg then lastly moving tower for n – 1 disks recursively from impermanent peg to the first
destination. Thus given M0(n) as there is a move in the number, then, relation recurrence would be
M0(n) = M0(n−1) + 1 + M0(n−1) for n > 0, with M0(0) = 0, having solution M0(n) = 2n – 1.
Problem Definition
Tower of Hanoi as a mathematical game is considered to comprise of three rods, a varied disks with
different sizes and can easily slide onto each other. In addition, this puzzle begins with the disks that are
in a neat stack that seems to ascend in order of size, where the smallest being at the top thereby leading
to formation of a conical shape (Donnarumma, Maisto & Pezzulo, 2016). Furthermore, the major aim of
the game is to ensure that the whole stack is moved to the other rod, by observing rules: Firstly, a single
disk to move at a time. Secondly, every move comprise of using the disk that is on top from one of the
given rods and then making it to slide onto a different rod, specifically to be on other disks’ top present
on the same rod and finally, no disk should be put on top of a disk that is smaller.
Real World Application of Towers of Hanoi Problem
Notably, both the past and present of Towers of Hanoi has mainly comprised recreational math,
however, its future would involve major applications in real world. To begin with, the puzzle can be
applied to assess the degree of different brain injuries and it as well acts as a support in rebuilding of
neural pathways located in the brain (Williams et al., 2014) In addition, in regard to this effect it also
forges new connections found in the prefrontal lobe. Furthermore, while attempting to get solutions to
Towers of Hanoi do exercise various parts of the brain that normally aid in managing time as well as
making complex arguments or creating ideologies to present a business plan(Williams et al., 2014). On
the other hand, it is worth noting that even if one fails to actually solve the puzzle, but anyone who just
attempts to solve the problem would then benefit as trying to solve the puzzle is entertaining.
Furthermore, The Towers of Hanoi is not only beneficial in mental and physical terms, but also in terms
of various jobs. Often, psychologists use the Towers of Hanoi to examine and research problem solving
skills. Moreover, in order to acquire these problem solving skills, one must calculate strategies and

3
moves and at the same time perform predictions to possible outcomes (entertainment) (Dogmus,
Erdem, & Patoglu, 2014). On the other hand, recursive rule of the Towers of Hanoi are always studied
and also applied in in computer algorithms and programming which therefore helps in reducing the
length of time taken in creating a program.
Towers of Hanoi Solution
According to Thien et al. (2016), to offer solution to the Problem, recursion method is majorly used.
Recursion by definition refers to steps that are included within other steps. Moreover, using recursion
majorly develops key insights and this makes everything to become simpler. Moreover, the insight is
establishing what data actually should be recused on and determining the essential feature from the
problem that need to change. Furthermore, a recursion is done on the largest disk that should be
moved. In addition, a recursive function which use the largest disk located in the tower to be moved as
the parameter is written. On the other hand, the function would three parameters that indicate from
which indicate the peg from which the tower is moved, followed by another indication to which peg the
tower should move to, followed by the other peg, which therefore can be temporarily used to make this
happen. Below is a figure showing example of recursion case in figure
Figure 1: Recursive processes
It is worth noting that recursion is used in solving the Tower of Hanoi as a problem since it provides
solutions to various problems which can further be split into sub problems hence making the process
simpler.
Possible Algorithms
Iterative Algorithm: Computing is another alternative of solving Towers of Hanoi problem, and in this
case iterative algorithm is used (Hinz & Petr, 2016). Moreover, the solution is majorly based on the use
of binary tree of 2n − 1 nodes in which the recursive steps are associated. Furthermore, every node of
the trees labeled where each label represent a move. In addition, the moves that are possible are six
which are different and are all marked as in figure 2 below. It is notable that the move in every level
holds a special pattern. For instance, for odd z y’ x levels get repeated whereas for the even levels xyz’
are always repeated. Thus the in order transversal for the binary tree provides solution to the problem.
Additionally, the defined binary number is associated by j to each and every node in the binary tree.
Often, the labels together with the disk number to corresponding node showing various moves
computed from j. The table below shows summary of the six moves alongside the corresponding label.
In addition, in figure 3 below the binary tree is shown.

4
Figure 2: Showing various moves and their corresponding labels (Source: Author)
Figure 3: Showing binary tree with recursive steps connected to Towers of Hanoi solution for n =5
(Source: Herter, & Rote, 2018)
Moreover, it is notable that inorder numbering for nodes begin from initial level , denoted as nth
level.Thus , given that n is registered as odd, the the pattern of the odd category becomes zy’x’ while for
the even n patttern becomes xyz’ where the trend would keep on altering to other one (Herter & Rote,
2018). In addition, the algorithm is then designed in a way to select only correct pattern where the
number j gets converted into 0, 1 and 2, so that given an odd pattern, 0 represents z, 1 represents y’
while 2 represents x’. On the other hand, for even trends,0 would stand for x as 1 represents y whereas
2 stands for z’. Notably, when the j the level function has been realized, maximum i that 2i | j (where 2i
divides j) is computed. Furthermore, it is noteworthy that n – i from computing shows the level number.
it is also notable that for odd numbers, the value i equals 0, thus other odd numbrers would show
apperance towards the nth level.
In addition, once the value of I has been computed, then j the variable, gets shifted in i + 1 times where
result obtained is then divided by 3. Motreover, the remainder would become 0 , 1 and 2 as had been
noticed earlier above. Besides, computations of the function i can either be performed by using loopless
or loop. Thus it is worth noting that the Algorithm work below shows the computation using the inner
loop (Hinz & Petr, 2016). Threfore, the time complexity has been proved for the algorithm used is O (2n).

5
Conclusion
In conclusion, the Towers of Hanoi as a problem has been noticed to have varied applications to human
life like exercising brain to come with new ideologies and it as well entertains through puzzling.
Moreover, recursive method has been used in attempt to give solution to the Hanoi problem. In
addition, the Towers of Hanoi as a mathematical problem can help in various fields when its solution is
obtained. Furthermore, computing method through Iterative algorithm, its solution has been found
since the number of discs, direction of movement and name of pegs are computed.

6
References
Kazak, S., Wegerif, R. and Fujita, T., 2015. The importance of dialogic processes to conceptual
development in mathematics. Educational Studies in Mathematics, 90(2), pp.105-120.
doi.org/10.1007/s10649-015-9618-y
Grosu, C., 2015. A new lower bound for the Towers of Hanoi problem. arXiv preprint arXiv:1508.04272.
https://arxiv.org/abs/1508.04272
Donnarumma, F., Maisto, D. and Pezzulo, G., 2016. Problem solving as probabilistic inference with
subgoaling: explaining human successes and pitfalls in the tower of hanoi. PLoS computational
biology, 12(4), p.e1004864. doi.org/10.1371/journal.pcbi.1004864
Williams, D.L., Mazefsky, C.A., Walker, J.D., Minshew, N.J. and Goldstein, G., 2014. Associations between
conceptual reasoning, problem solving, and adaptive ability in high-functioning autism. Journal of autism
and developmental disorders, 44(11), pp.2908-2920. doi.org/10.1007/s10803-014-2190-y
Dogmus, Z., Erdem, E. and Patoglu, V., 2014. ReAct!: An interactive educational tool for AI planning for
robotics. IEEE Transactions on Education, 58(1), pp.15-24. doi: 10.1109/TE.2014.2318678
Herter, F. and Rote, G., 2018. Loopless Gray code enumeration and the Tower of Bucharest. Theoretical
Computer Science, 748, pp.40-54. doi.org/10.1016/j.tcs.2017.11.017Get rights and content
Hinz, A.M. and Petr, C., 2016. Computational solution of an old Tower of Hanoi problem. Electronic
Notes in Discrete Mathematics, 53, pp.445-458. doi.org/10.1016/j.endm.2016.05.038
Thien, N.D., Terracina, A., Iocchi, L. and Mecella, M., 2016. Robotic teaching assistance for the “tower of
hanoi” problem. International Journal of Distance Education Technologies (IJDET), 14(1), pp.64-76.
doi: 10.4018/IJDET.2016010104