#Chegg code hanoi towers trial
#Chegg code hanoi towers free

Move disk N from the source to the target peg c. Move top N-1 disks from the source to the spare peg b. Move disk N from the source to the target peg (base case) 2. Suppose you want to move N disks from peg A (source) to peg C (target), with peg B as the spare.

This special case where the problem is simple enough to solve without further delegation is called the base case. Eventually, the problem must be small enough that it’s simple to solve without breaking it down any further. Recursion involves defining a problem’s solution in terms of solutions to smaller problems. Although they probably didn’t know it, they were on track to defining a recursive solution to the problem.

#Chegg code hanoi towers free

I was excited to hear one group set an intermediate goal of getting the top 4 disks to the spare peg in order to free up the bottom disk. When working on the 5-disk problem, I began to hear groups of girls discussing their strategies. These patterns were helpful in signaling when we’d made a non-optimal move. The smallest disk was moved every 2nd move, the next smallest every 4th move, the next smallest every 8th move, and so on. We noticed another pattern in the frequency that the disks were moved. When solving the puzzle optimally, a disk will never be directly touching another of the same color. The largest disk was light brown, the next largest was dark brown, and so on. Most of the girls had a version of the puzzle in which the disks alternated colors. We also noticed some other interesting patterns while solving the puzzle. We explained the power of what they were doing: using a simple version of the problem (2 or 3 disks) to learn the puzzle and define a strategy that makes it straightforward to solve with any number of disks. Some also used the sequence of steps from the 2-disk problem to attempt the 4 and 6-disk problem. Some of them used this pattern to help them solve the 5-disk problem. After the girls were comfortable solving the 3-disk problem, we recorded their moves together on a white board and they were able to identify the pattern.

Make the only allowed move between B and Cįor a given pair of pegs, there is always only one possible move that does not break the rules.

Make the only allowed move between A and C.

Make the only allowed move between A and B.

Assuming you have pegs A, B, and C and you’re trying to move the tower from A to C… It turns out that depending on whether the puzzle has an even or odd number of disks, there is a repeatable pattern in the moves required to solve it optimally. If you solve the puzzle with 3 disks, a relatively easy task, and write down each move you make, you may notice a pattern in the sequence of moves. How can we approach this puzzle in a way that makes it straightforward, even repetitive, to solve as we add more disks? There are a few strategies that can be used with Tower of Hanoi.

#Chegg code hanoi towers trial

While trial and error may be feasible with 3 or 4 disks, a more thoughtful strategy becomes necessary with more disks. Most girls were shocked to learn that it would take 585 billion years. To reinforce how quickly the problem grows, we asked how long it would take to solve the 64-disk puzzle optimally if you made one move per second. Some groups even came up with the exact expression describing how the optimal number of moves relates to the number of disks: (2^N)-1, where N is the number of disks. The girls recognized that the problem effectively doubled in size with each added disk. Together we maintained a chart of the optimal number of moves required to solve the puzzle with 1, 2, 3, and 4 disks. After they learned that the 3-disk puzzle could be solved in 7 moves, they were motivated to find that optimal sequence of steps. After an initial explanation of the rules, we let the girls try the puzzle with just 3 disks and asked them to count their moves. The rules are simple to understand, but the puzzle quickly becomes complex to solve as more disks are added.Īt Next Century’s Women in Computing day this year, we had a session on the Tower of Hanoi puzzle. Only the topmost disk from a stack may be movedįor any given number of disks, there is an optimal number of moves in which the puzzle can be solved.A larger disk may never be placed on a smaller disk.The goal of the puzzle is to move all disks from one rod (or section) to another while obeying the following simple rules: Easier yet, there are online versions you can play ( ). If you don’t have a puzzle that looks exactly like the one pictured, you can make your own version using coins or any variable sized disks and a piece of paper divided into three sections.