In the earlier Article: Recursive Algorithm for solving Three Peg Tower of Hanoi Puzzle the algorithm for solving the Classical puzzle was discussed. The number of 1 Disk moves needed for moving a stack of n disks from the Source-Peg to the Target-Peg was derived to be: Number of Moves = 2n - 1. Due to the exponent of n, this number rises very rapidly with increasing value of n. Therefore, while the solution is acceptable for a puzzle or a game, it becomes impractical for a real life situation. In the practical world there is no reason to restrict to just 3 Pegs. Therefore, we need to investigate a solution Algorithm using more than 3 Pegs. We will refer to the setup with more than 3 Pegs as the "Tower of Chicago Using more than 3 Pegs".
Consider a Tower of Chicago set up with 4 Pegs and 3 Disks as shown in Figure 1 below. There is a SourcePeg with a stack of 3 Disks. There are two Auxiliary Pegs: AuxPeg-1, AuxPeg-2; and there is a TargetPeg. The initial state of this setup is as shown in Figure 1 below. The goal is to move the stack of Disks in the SourcePeg to the TargetPeg, with the minimum number of moves, while adhering to the two rules: You can move only the the top-most disk on any Peg - at a time, and you cannot place a larger disk on top of a smaller disk.
So, the simplest scheme to utilize the increased number of Auxiliary Pegs, is to simply move one Disk from the SourcePeg to each of the AuxiliaryPegs, i.e., move Disk D-1 to from SourcePeg to AuxPeg-1, and then move Disk D-2 from SourcePeg to AuxPeg-2. Each of these two moves obeys both the rules. Also, it opens up Disk D-3 so that it can be moved to the bottom of the TargetPeg where it needs to be in the final solution - see Figures 2-a, 2-b above, and Figure 2-c below. Now that The largest Disk D-3 is at the bottom of the TargetPeg's stack, we can proceed to move Disk D-2 from from AuxPeg-2 to TargetPeg on top of the larger diameter Disk D-3. Finally we can move Disk D-1 from from AuxPeg-1 to TargetPeg on top of the larger diameter Disk D-2 - see Figures 2-d, 2-e below.
What is demonstrated above, we may call it the Distribution-Accumulation Algorithm. We Distribute the Disks in the SourcePeg's stack amongst all the Auxiliary Pegs - One Disk to each AuxPeg. Since intially all AuxPegs are empty, the rule above is easily and trivially obeyed. If the number of Disks in the SourcePeg's stack is just 1 more than the number of available AuxPegs, then the last Disk on the SourcePeg - the Bottom-Most and largest diameter Disk - will be opened up and can be moved directly to the TargetPeg. Now each of the smaller Disks is currently the Top-Most Disk in an AuxPeg. So we can now Accumulate the disks from the top of all the AuxPegs, in the order of decreasing diameters, to fill up the TargetPeg.
To sum up, we distribute all the Disks - except the Bottom-Most Disk - from the SourcePeg to all the AuxPegs. Then we move the Bottom-Most Disk from the SourcePeg to the TargetPeg. Then we accumulate all the Top-Most Disks from all the AuxPegs into the TargetPeg, in the correct order. This is what we call the Trivial Solution.
The Trivial Solution can be represented by the following three step procedure:
Trivial Solution with (n - 1) Auxiliary Pegs and n Disks:
Step a: Move the successive (n - 1) top Disks, from the top of the SourcePeg to one of the empty Auxiliary Pegs, one Top Disk at a time.
Step b: Move the nth Disk (largest diameter of the n Disks) from the SourcePeg to the TargetPeg.
Step c: Move the top Disk from each Auxiliary Peg, in the order of decreasing Disk diameter, to the top of the TargetPeg stack.
The number of moves needed for Trivial Solution is a function of the number of Disks n, and number of Auxiliary Pegs n - 1. As there are (n - 1) AuxPegs, the Distribution of (n - 1) Disks (Step a above) from the SourcePeg - to one Disk for each AuxPeg, will require (n - 1) moves. Moving the last Disk from SourcePeg to TargetPeg (Step b above) will require 1 move. The Accumulation of the (n - 1) Top Disks from the AuxPegs to the TargetPeg (Step c above) will take another (n - 1) moves.
Therefore the total number of moves for the Trivial Solution described above is: MovesTrivial Soln = 2(n - 1) + 1 = 2n - 1 moves.
The trivial siolution is simple, but it has a limitation. What if the number of Disks in the SourcePeg, exceeds the number of AuxPegs by more than 1 Disk? In our 4 Pegs case, what if we had 6 Disks instead of 3? To overcome this limitation, now we need to use the our simple trivial solution as a building block to construct a more complex solution using a 3 Step Recursion Model .
Please read about the Recursion Programming Model in the earlier article in this series.
Consider the case of 4 Pegs and 6 disks. We can simplify the 6 disk case as follows. Split the stack of Disks on the SourcePeg into two parts: "Top Part of the SourcePeg Stack" stack is Disks D-1, D-2 and D-3, and the "Bottom Part of the SourcePeg Stack" stack is Disks D-4, D-5 and D-6 - see Figure 3 below. In the Trivial solution listed above, we moved a stack of 3 Disks from the SourcePeg to the TargetPeg. However, if we move the "Top Part of the SourcePeg" stack directly to the TargetPeg, then the "Bottom Part of the SourcePeg" which contains the larger diameter Disks (D-4, D-5, D-6) cannot be put on the TargetPeg since it will already contain the smaller diameter Disks D-1, D-2, D-3.
Therefore, we will switch the "Peg Roles" when we are moving the "Top Part of the SourcePeg" and recursively execute the entire Trivial Solution inside the Step 1 of the parent recursion with the switched "Peg Roles": The TargetPeg plays the role of AuxPeg-1, the AuxPeg-2 plays the role of AuxPeg-2, and AuxPeg-1 plays the role of TargetPeg, i.e., essentially AuxPeg-1 and TargetPeg switch their roles. Please refer to the Figures 3, 4, 5, and 6 below to see the the recursive trivial solution play out inside the Step 1, with the "Top Part of the SourcePeg Stack". We will call this the first part of Step-1 of the parent recursion.
At the end of this first part of the Step-1, the "Top Part of the SourcePeg Stack" (Disks D-1, D-2, and D-3) is located on AuxPeg-1, and the "Bottom Part of the SourcePeg Stack" (Disks D-4, D-5, and D-6) is still located on the SourcePeg. At this time, we can focus just on the "Bottom Part of the SourcePeg Stack" and consider a 3-Peg system of SourcePeg, AuxPeg-2, and the TargetPeg. Now, instead of 2 empty Auxiliary Pegs, we have only one empty Auxiliary Peg (AuxPeg-2). The AuxPeg-1 contains the set of smaller diameter Disks D-1. D-2, D-3, so we cannot use it when we are moving the larger diameter Disks D-4, D-5, D-6, since a larger diameter Disk cannot be placed on top of a smaller diameter Disk. Therefore, set AuxPeg-1 aside for the time being.
We can again execute the trivial solution listed above to a system of only 1 empty Auxiliary Peg.
The number of Disks moved = The number of empty AuxPegs + 1 = 1 + 1 = 2.
But the SourcePeg still has 3 Disks. Therefore once again we will split the 3 Disk SourcePeg stack (Disks D-4, D-5, D-6) into two parts:
(new) "Top Part of the SourcePeg Stack" stack is Disks D-4, D-5, and the (new) "Bottom Part of the SourcePeg Stack" stack is D-6.
Once again now we can switch the "Peg Roles" - and make AuxPeg-2 play the role of the TargetPeg and the TargetPeg play the role of the AuxPeg-2 and execute the the trivial solution for the 3 Peg system - please see Figures 7, 8 below. At the end of it the (new) "Top Part of the SourcePeg Stack" (Disks D-4, D-5) is located on AuxPeg-2 and the (new) "Bottom Part of the SourcePeg Stack" (Disk D-6) is still located on the SourcePeg - Figure 8 below. At this point we have completed the second part of Step 1 of the parent recursion.
At the end of Step 1 of the parent recursion, we have a 3 Disk stack (Disks D-1, D-2, and D-3) on AuxPeg-1, a 2 Disk stack (Disks D-4, D-5) on AuxPeg-2, and the Bottom-most and largest diameter Disk D-6 is is the only Disk on the SourcePeg. The TargetPeg is still empty, so we can directly move D-6 from the SourcePeg to the TargetPeg where it will now become the Bottom-most Disk - which is where it belongs in the final state. This is the Step 2 of the parent recursion. It represents the midpoint of the entire process, and the SourecPeg is now empty - please see Figures 9 below.
Now that the SourcePeg is empty, we can make it play the Role of an AuxPeg-1 for the next step: Step 3 of the parent recursion.
The first part of Step 3 is to move the 2 Disk stack (D-4, D-5) from AuxPeg-2 to the TargetPeg on top of the Disk D-6. This is because the Disks D-4 and D-5 are bigger in diameter, so they need to go on the Target-Peg first, before the smaller Disks that are on AuxPeg-1. The original AuxPeg-1 does not participate in this first part of Step 3 at all.
So, we will recursively execute the trivial solution listed above, within the Step 3 of the Parent recursion, on the three Pegs and 2 Disks system made up of:
AuxPeg-2 playing the role of SourcePeg (with its 2 Disk stack), the empty SourcePeg playing the Role of AuxPeg-2, and the TargetPeg playing the Role of TargetPeg.
In effect, the SourcePeg and AuxPeg-2 have switched their Roles and AuxPeg-1 is not participating. Please see Figures 10, 11, 12 below to see how it progresses. At the end of the execution of the first part of Step 3, the SourcePeg and AuxPeg-2 are empty, the TargetPeg has the stack of 3 Disks (D-4, D-5, D-6) that was the original "Bottom Part of the SourcePeg Stack", and AuxPeg-1 has the original "Top Part of the SourcePeg Stack" (Disk D-1, D-2 and D-3) - see Figure 12.
Now we can execute the second part of Step 3 of the parent recursion, which is to move the 3 Disk stack (D-1, D-2, D-3) from AuxPeg-1 to the TargetPeg on top of the stack of Disks D-4, D-5, D-6.
So, recursively execute the trivial solution listed above, within the Step 3 of the Parent recursion, on the Four Pegs and 3 Disks system made up of:
AuxPeg-1 playing the role of SourcePeg containing 3 Disk stack (D-1, D-2, D-3), the empty SourcePeg playing the Role of AuxPeg-1, empty AuxPeg-2 playing the role of AuxPeg-2, and the TargetPeg playing the Role of TargetPeg - please see Figure 12 above and Figures 13, 14, 15 below. In the final state - Figure 15 - the entire stack of Disks D-1 through D-6 is located on the TargetPeg in the correct order.
This entire 3 Step Recursion Model can be summarized as follows:
Step 1: Consider the Top n Disks of the SourcePeg where n equals the number of AuxPegs that are empty. Execute recursively the above Trivial Solution on Top n disks of the SourcePeg, using the "Peg Roles" as:
Original Source Peg = Source Peg, current AuxPeg-1 = TargetPeg, all other (n - 2) empty AuxPegs as themselves, and Original TargetPeg as AuxPeg-1.
After executing each recursion, keep the current AuxPeg-1 (it played the role of TargetPeg) aside and rename all the empty AuxPegs as -1, -2 etc., eveluate if the remaining number of Disks still exceeds the number of empty AuxPegs, and if it does, execute the next recursion and then repeat.
When the number of Disks left on the SourcePeg is less than number of empty AuxPegs, keep the very Bottom-Most (largest diameter) Disk aside for Step 2 and execute the last recursion of Step 1 - it might be a partial one as the remaining number of Disks on the SourcePeg may be less than the remaining number of empty AuxPegs.
Step 2: Move the Bottom-Most (largest diameter) Disk from the SourcePeg to the TargetPeg.
Step 3: Iterate - in the correct order - through all the AuxPegs that were partially filled and kept aside during Step 1. For each of these AuxPegs, execute the trivial solution using the "Peg Roles", Original Source Peg = AuxPeg-1, the selected filled AuxPeg = SourcePeg, the empty AuxPegs = themselves, and original TargetPeg = TargetPeg. The order in which the partially filled AuxPegs are processed is important - it should be the exact opposite order in which they were filled in the Step 1 above.
We will also determine the total number of moves that would be needed. Note that Step 2 needs only 1 move.
Total number of moves needed = Total Number of Moves in Step 1 + 1 + Total Number of Moves in Step 3.
Please Note that n is the number of disks in the very first iteration of Step 1 which is equal to the maximum number of empty AuxPegs + 1.
Total Number of Moves in Step 1 = NStep1moves
However, Step 1 and Step 3 are physically identical for each of the iterations. Therefore,
Total number of moves needed = 2(NStep1moves) + 1
NStep1moves
= Sum up the number of moves for individual recursions from n Disks (n - 1 empty AuxPegs) to 2 Disks (1 empty AuxPeg)
In the expressions below the variable k is used as the running summation variable and the limits are from k=2 to k=n.
NStep1moves = ∑(2k - 1)k=2...n
NStep1moves = 2.∑ k k=2...n - ∑1k=2...n
NStep1moves = 2.∑ k k=2...n - (n - 1)
NStep1moves = 2.∑ k k=2...n + (1 - n)
The first term in the above equation's right hand side can be simplified as below:
2.∑ k k=2...n = 2.{∑ k k=2...n + 1 - 1} = 2.{∑ k k=1...n - 1}
2.∑ k k=2...n = 2{[n.(n+1)/2] - 1} = n(n+1) - 2
Making the above substitution we get the formula for NStep1moves as:
NStep1moves = n.(n+1) - 2 + (1 - n) = n2 - 1
Therefore, Total number of moves needed = 2.(NStep1moves) + 1 = 2.(n2 - 1) + 1
Total number of moves needed = 2.n2 - 1
Therefore, given a system of 4 total Pegs, we have 2 empty AuxPegs (maximum) at the start, so value of n = 2 + 1 = 3.
The first iteration value of n: n = Number of empty AuxPegs + 1 = 2 + 1 = 3
Maximum number of Disks on the SourcePeg that can be moved with Distribution-Accumulation alone = P = n(n + 1)/ 2 = 3(3 + 1)/2 = 6
Total number of moves needed = 2n2 - 1 = 2(32) - 1 = 18 - 1 = 17 moves.
Please verify on www.towerofchicago.com using option (2) - "Tower of Chicago Using more than 3 Pegs". In the setup select 4 Pegs and 6 Disks and click the "Generate Moves" button. Verify the Number of Moves needed, and also walk through the moves using the "Next" and "Previous" buttons to verify the 3 Step Recursion Model as well as the use of the Trivial Solution described above.
Similarly, please verify the above formulae for the 5 Total Pegs system - n = 3 + 1 = 4, Max Number of Disks = 4x5/2 = 10, Total Moves = 2(42) - 1 = 32 - 1 = 31
Notice that for the 5 Pegs a total of 10 Disks can be moved in just 31 moves , from the SourcePeg to the TargetPeg, by using the Distribution-Accumulation Algorithm alone. In the earlier Article in this series - Recursive Algorithm for solving Three Peg Tower of Hanoi Puzzle it was shown that for the classical 3 Pegs system using the Recursion Algorithm alone a system of 10 Disks on 3 Pegs would need 210 - 1 moves that is 1023 moves. So, increasing the number of Pegs from 3 to 5 and using the Distribution-Accumulation algorithm yields a big decrease, 1023 to 31, in the number of moves needed. This should make the physical process more efficient. However, please note that the 3 Step Recursion Model presentad above, has a limitation.
In the Three Step Recursion Model Algorithm described above, for a 5 Peg system, using the Distribution-Accumulation alone, we are limited to moving a maximum of 10 Disks, whereas with the earlier 3 Peg Recursive Algorithm For Tower of Hanoi, we could move any number of Disks - not just a maximum of 10 Disks. With more than 3 Pegs and the Distribution-Accumulation Algorithm, as the number of Disks stacked on the SourcePeg increases, we will need more and more Auxiliary Pegs to complete the Task. There is a practical limit on how many Pegs can be provided. So, how do we remove the limit on the number of Disks that can be moved from the SourcePeg to the TargetPeg using a reasonable number of Pegs?
The answer to the above question has two parts - both of which involve some undisclosed logic. First part is that after doing two recursions in the Step 1 of the above 3 Step process do not put the first AuxPeg aside. Instead re-execute the trivial step again to consolidate all the Disks moved so far into a single AuxPeg and keep repeating this process. The second part is to blend the 3-Peg Tower of Hanoi Recursive Algorithm with the n-Peg Distribution-Accumulation Algorithm in such way designed to optimize the benefits of both - the flexibility of the first and the efficiency of the second. The resulting number of moves is still significantly less than (2n - 1) - calculated for the 3-Peg Recursive Algorithm for Tower of Hanoi, and more than what would be predicted by the formula 2.n2 - 1 for the n-Peg Distribution-Accumulation Algorithm.
Within the option "Tower of Chicago Using more than 3 Pegs" the User can increase the number of Pegs up to 10 and increase the number of Disks up to 20. Both limits are not limitations of the Algorithm, but a limitation of the screen size for display. Theoretically the solution can be extended to any number of Disks and Pegs.
Moving a stack of disks from one peg to another peg while obeying a rule of never placing a larger diameter disk on top of smaller diameter disk may appear like a game. However, it is entirely possible, that some real physical business process mimics this situation. It may be that instead of the disks, there may be some other complex items that have to be vertically stacked, and instead of the disk size rule, some other property of the items is used to determine the ordering of the stack. If your business domain has a similar situation, I can devise a similar solution based on a thorough analysis of the constraints of your system.
For demonstration purpose, the solution is displayed on a Screen and also in Text form in the window named "List of All Moves" at the bottom of the Canvas that displays the Pegs and the Disks. However, the List of Moves could also be sent to your System in the form of JSON response. The solution can be deployed as a Web Service responding to an authenticated HTTP request with a JSON payload. This solution is deployed on AWS cloud. It is available worldwide.
I can develop and deploy on AWS Cloud, a custom-designed solution to your particular business problem, in the form of a Restful Service. I can also set up Authentication for your selected users. You can setup a regression test suites on your systems to test the solutions via HTTPS requests. There are significant cost savings possible by utilizing small size custom solutions on a pay per use basis as compared to in-house code development and code maintenance.
At the bottom of the Home Page there is a Button named "About the Author/Developer". Click this button, to send me a message, and please include your eMail to set up direct communication.