![]() Is easy enough, trivial you might even say. But what if you do not know how to move a tower of three? How about movingĪ tower of two disks to peg two and then moving the third disk to peg three, and then moving the tower of height two on top of it? But what if you still do not know how to do this? Surely you would agree that moving a single disk to peg three That you knew how to move a tower of height three to peg three then it would be easy to move the fourth disk to peg two and move the three from peg three on top of it. But what if you do not know how to move a tower of height four? Suppose If youĪlready knew how to move a tower of four disks to peg two, you could then easily move the bottom disk to peg three, and then move the tower of four from peg two to peg three. Suppose you have a tower of five disks, originally on peg one. How do we go about solving this problem recursively? How would you go about solving this problem at all? What is our base case? Let's think about this problem from the bottom up. You do not need fancy disks and poles–a pile of books or pieces of paper will workįigure 1: An Example Arrangement of Disks for the Tower of Hanoi If you have not tried to solve this puzzle before, you should try it now. Notice that, as the rules specify, the disks onĮach peg are stacked so that smaller disks are always on top of the larger disks. At a rate of one move per second, that is 584, 942, 417, 355 584, 942, 417, 355 years! Clearly there is more to this puzzle than meets the eye.įigure 1 shows an example of a configuration of disks in the middle of a move from the first peg to the third. ![]() When they finished their work, the legend said, the temple would crumble into dust and the world wouldĪlthough the legend is interesting, you need not worry about the world ending any time soon. The priests worked very efficiently, day and night, moving one disk every second. They could only move one disk at a time,Īnd they could never place a larger disk on top of a smaller one. Their assignment was to transfer all 64 disks from one of the three poles to another, with two important constraints. Poles and a stack of 64 gold disks, each disk a little smaller than the one beneath it. At the beginning of time, the priests were given three He was inspired by a legend that tells of a Hindu temple where the puzzle was presented to young priests. Stk.The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. Stk.append((In,numRings-1,fromPeg,usePeg,toPeg)) Stk.append((To,numRings,fromPeg,toPeg,usePeg)) #B save state If numRings != 0: #push down to 1 numRing #A State,numRings,fromPeg,toPeg,usePeg = stk.pop() Tower1(numRings-1,usePeg,toPeg,fromPeg) #D Tower1(numRings-1,fromPeg,usePeg,toPeg) #B ![]() #recursive solutionĭef tower1(numRings,fromPeg,toPeg,usePeg): In this case there is one state on the stack. The stack saves the order of the calls and their state. Progress_bar(ans) # calls progress bar functionīelow is a recursive and equivalent iterative solution. Write("Total moves: %s" % (moves), align="center", font=("Courier", 16, "bold")) Moves += 1 # amount of total moves is incremented x is x-position of peg"""ĭ.write("Moved %s times" %(str(d.moves)), align="left", font=("Courier", 16, "bold"))ĭ.moves += 1 # increments the number of moves each time the disc is moved """Hanoi tower, a subclass of built-in type list""" Self.moves = 0 # stores the number of times the disc is moved Self.speed(11-n) # sets the speed of movement of the rectangles (the bigger, the slower) Turtle._init_(self, shape="square", visible=False) Import pickle # used to save an object to a file Import time # used for time-related functions (in pause) When an even number is input as the number of discs the program doesn't even start.įrom tkinter import * # used for the dialog boxįrom tkinter.simpledialog import askinteger # used for the dialog boxįrom tkinter import ttk # used for the progress bar It works somehow when I input an odd number, however, when the third turn passes things go wrong. It throws an error: "can't pop from empty list". I'm trying to figure out how to implement a non-recursive algorithm for the Hanoi Towers problem in function hanoi_2 below, but I have no idea how to continue.
0 Comments
Leave a Reply. |