|
|Store|
|
|
|
|
|
|
|
CTK Exchange
saumil07
Charter Member
2 posts |
Feb-16-01, 09:24 AM (EST) |
 |
"THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
|
You guys out there probably know about the towers of hanoi....let me give you a different perspective that has bogged me for the past few days..... The regular problem has 3 needles, and you have to move n disks from source to destination using the auxiliary pin. You can move from source to auxiliary OR source to destination and vice versa. This recursive solution takes 2^n moves in the worst case. MY problem, however has restrictions imposed upon it. You can move from source to auxiliary, from auxiliary to source, from aux. to destination, and from destination back over to aux. and to source. THE move that is NOT ALLOWED is from source to destination straight. So everytime you go from source to destination, you have to move through auxiliary. This adds great complexity to the program. Please let me know if anybody has a recursive solution to this. Thanks PATRICK |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
672 posts |
Feb-16-01, 09:29 AM (EST) |
 |
1. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #0
|
>Please let me know if anybody >has a recursive solution to >this. Before we start seeking a recursive solution, I suggest we find any solution for some simple case. Could you please find a solution for the two disks problem that satisfies your constraint. Let me know and we'd work out the rest. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
 |
saumil07
Charter Member
2 posts |
Feb-17-01, 07:54 PM (EST) |
 |
2. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #1
|
Hi, let me try to show you what the base case for 2 disks would be, with the specified constraints. There are 2 disks on Source (S), none on Aux. (A) and none on Destination (D) when the problem starts. You move the smallest disk (uppermost) to A and then over to D. Next, you move the biggest (2nd disk) to A, and then proceed by moving the smalles from D on back over to S. Move the biggest from A to D, and then move the smallest from S to A and then over to D, completing the problem for the simple case. It takes 7 moves to move 2 disks over, and 19 to move 3, and 38 to move 4. Does this make sense, or would you require more details? Thanks PATRICK |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
 |
alexb
Charter Member
672 posts |
Feb-17-01, 09:29 PM (EST) |
 |
3. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #2
|
Now I see. Candidly I missed the point. Let me think of it. But just in passing. I checked with the Encyclopedia of Integer Sequences (https://www.research.att.com/~njas/sequences/) for 2, 7, 19, 38 ... The sequence has not been recorded. So that if you are not mistaken as regard 19 and 38, you have a chance to register a new sequences under your name. I'll be thinking of your problem. Alexander Bogomolny |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
 |
PATRICK (Guest)

guest
|
Feb-18-01, 03:45 PM (EST) |
|
4. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #3
|
Add another restriction to it. You cannot move from Aux. to Source either. So that adds another move when there are 3 discs. the sequence becomes 2, 7, 20, etc. Makes the problem even more complex. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
 |
alexb
Charter Member
672 posts |
Feb-18-01, 05:09 PM (EST) |
 |
5. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #4
|
> Makes the problem even more complex I am not sure about that. I think that they are about the same. You may get a more straightforward problem if, in addition, you also exclude direct moves from Dst to Aux. With those three restrictions you may be able to obtain an upper bound for your probems. The problem with three restrictions may be looked at this way. Place your pegs on a circle so that only clockwise moves are allowed. The pegs Src, Aux, Dst will be traversed clockwise. Let's forget for a moment about the designations source, auxiliary and destination, and think of just having N disks on one of the pegs. Let Tn be the number of moves needed to move the pegs 1 arc clockwise, and Sn be the number of moves needed to move n pegs 1 arc counterclockwise. Then Tn = Sn-1 + 1 + Sn-1, and Sn = Tn-1 + 2 + Tn-1. In matrix notations, let vn = (Tn Sn)T and a = (1 2)T. Then vn = A·vn-1 + a, where A is the matrix with rows (0 2) and (2 0). We may take v0 = 0, so that v1 = a. Then, successively, v2 = Aa + a, v3 = A2a + Aa + a, v4 = A3a + A2a + Aa + a, etc. The solution is almost immediate if you separate the sequences of odd and even n's. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|

You may be curious to visit the old CTK Exchange archive.
|Front page|
|Contents|
Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
|
Advertise
|