CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Algorithm for 3-color Tower of Hanoi"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #681
Reading Topic #681
mr_homm
Member since May-22-05
Feb-12-06, 07:16 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
"Algorithm for 3-color Tower of Hanoi"
 
   I promised a few days ago in another thread that I would post this algorithm, but then I got very busy for a while. Here it is, finally:

Assumptions:

3 pegs, 3N disks of N different sizes, 3 colors of each size. Size N is the largest disk, size 1 the smallest.
Rules: A larger disk must never sit on top of a smaller disk. Equal size disks are OK to stack. The only allowed move is to transfer a single disk from one peg to another.
Starting Position: Each peg holds all N disks of a single color, ordered by size from largest (bottom) to smallest (top).
Ending Position: Same as starting position, but the colors of the stacks are rotated among the pegs, so that no peg holds the same color stack as it did in the starting position. In other words, a derangement of the stacks in the starting position.

Definitions:

A BASE of depth k is an arrangement of the k largest disks of each color (3k disks altogether) across all 3 pegs, so that no two disks of the same size are on the same peg.

A STACK of depth m is an arrangement of the m smallest disks of each color (3m disks altogether) into a single stack on one of the pegs, so that all three disks of each size (1 through m) are together on that one peg.

The idea:

Since there are very many positions possible, I will choose a subset of particularly simple positions that is broad enough to include all the absolutely necessary positions that must be used in a solution. By confining my moves to this subset, I will get a particularly simple algorithm, although it will not be possible to prove that it'solves the puzzle in the minimum number of moves.

Since in order to effect a derangement of the largest disks, all the smaller ones must be gathered into a single stack, a stack of depth N-1 is necessary at some point. Since the starting and ending positions are bases of depth N, these are necessary positions as well. The simplest definition of a subset of all positions that would include these is this: A stack of depth k on top of a base of depth N-k. I will choose these to be the allowed positions. The starting and ending positions fit into this scheme with k=0, and the intermediate stack fits with k=N-1.

I will only consider sequences of moves that start and end with allowed positions. There are four basic operations needed:

1: MOVE(a,b) moves the top disk of peg a to peg b. MOVE is invertible, and the inverse of MOVE(a,b) is MOVE(b,a).

2: SHIFT(a,b,c,k) moves a stack of depth k from peg a to peg b and ignores peg c. SHIFT is invertible, and the inverse of SHIFT(a,b,c,k) is SHIFT(b,a,c,k). It can be defined recursively just like the algorithm for the ordinary one-color Tower of Hanoi:


SHIFT(a,b,c,k)
{
if k > 0
{
SHIFT(a,c,b,k-1)
MOVE(a,b)
MOVE(a,b)
MOVE(a,b)
SHIFT(c,b,a,k-1)
}
}


3: GATHER collects the top layer of disks from a base onto the bottom of a stack of depth k located at peg a, leaving the resulting larger stack on peg c, and using peg b as a temporary location. It can be defined non-recursively by calling SHIFT:


GATHER(a,b,c,k)
{
MOVE(b,c)
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
}


4: SPREAD is the inverse of GATHER, and distributes the bottom 3 disks from a stack of depth k+1 on peg a to form a new layer on top of a base, and leaves the reduced stack on peg c, using peg b as a temporary location. It is defined much as GATHER:


SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
MOVE(a,b)
}


Some observations:

SHIFT reverses the color order in the bottom 3 disks of the stack. However, because SHIFT calls itself twice in each recursion, all disks above the bottom 3 have had their color order reversed an even number of times (in fact a power of 2). Hence all the color order in the stack is preserved, except for its very bottom layer of 3 disks. GATHER and SPREAD each call SHIFT twice, so that in practice, even the bottom layer of the stack has its color order preserved.

GATHER and SPREAD preserve a record of the color order of the base and the stack. If the colors are numbered 1, 2 and 3, then the color order of the top layer of the base can be thought of as a permutation of those numbers, call it B. Similarly, the color order in the bottom 3 disks of a stack is some permutation of [1,2,3] (ordered from the top down), call it S. The calling arguments of GATHER are some permutation of [1,2,3] as well, [a,b,c] = p([1,2,3]), where p is a permutation operation. As is easy to check (there are only a few cases) S=p(B). For instance, if the colors in the base are in the order 3,2,1, and if GATHER is called with parameters [a,b,c] = [1,3,2], its permutation is (2,3). The permutation of the bottom 3 colors of the stack will then be (2,3)[3,2,1] = [3,1,2].

SPREAD similarly gives B=q(S), where [c,b,a] = q-1([1,2,3]). Note the order reversal here. In order for SPREAD to be a true inverse of GATHER, the stack has to start where GATHER left it, and end where GATHER found it. Also, of course, q is inverted because SPREAD takes S to B instead of B to S. In short, q is the inverse of the reverse of the parameter permutation of SPREAD. Examining the definitions of GATHER and SPREAD line by line shows that each operation in SPREAD(c,b,a,k) is the exact inverse an operation in GATHER(a,b,c,k), and that the operations are carried out in the reverse order.

Recursive GATHER and SPREAD:

I defined GATHER and SPREAD nonrecursively to make it clearer how they preserve color permutation information. For any given base + stack position, there are two possible ways to apply GATHER or SPREAD: if the stack of depth k is on peg 1, for instance, GATHER(1,2,3,k) and GATHER(1,3,2,k) could be applied. These would leave the stack in different positions and also leave the bottom three disks in the new larger stack in a different color order. Therefore, the only way to make GATHER and SPREAD recursive and still inverse of each other, is to define a standard choice if permutation at each depth in such a way that SPREAD is inverse to GATHER at each depth.

Such a choice would have to be made in any case, merely to make GATHER and SPREAD recursive; the point here is that the choices must be compatible. For both GATHER and SPREAD, the previous call to them must leave the stack in the starting position for the next call. I will chose to make GATHER always rotate the parameters backwards in the subroutine call, and SPREAD always rotate them forwards, as follows (new definitions replace the old definitions):


GATHER(a,b,c,k)
{
if k>0
{
GATHER(b,c,a,k-1)
}
MOVE(b,c)
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
}


SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
MOVE(a,b)
if k>0
{
SPREAD(c,a,b,k-1)
}
}


With these definitions, it is easy to check that SPREAD(c,b,a,k) is the inverse of GATHER(a,b,c,k) at the kth depth, and that the recursive calls are to SPREAD(a,c,b,k-1) and GATHER(b,c,a,k-1), which are inverses at the k-1 depth. Therefore, the recursive SPREAD and GATHER are inverses at all levels.

Now the solution to the 3-color Tower of Hanoi with 3N disks is:


GATHER(1,2,3,N)
SHIFT(3,2,1,N)
SHIFT(2,1,3,N)
SPREAD(1,3,2,N)


The first line gathers all the disks into a stack on peg 3, and the next two lines move the stack to peg 1 (using 2 SHIFT calls, because doing it with just one would leave the bottom 3 disks on the stack in the wrong order). Since GATHER has put all the disks onto 1 peg, the SHIFT operations are equivalent to permuting the pegs with the permutation (1,2,3). Normally the inverse of GATHER(1,2,3,N) would be SPREAD(3,2,1,N), but because of the permutation of peg positions, the correct inverse has parameter order (1,2,3)[3,2,1] = [1,3,2]. Because the parameters have been rotated, SPREAD is "fooled" into distributing the colors onto different pegs than the ones they started on. In fact, the colors of the final position are permuted by the same permutation mentioned just above, (1,2,3).

In general you could solve the puzzle for whatever cyclic permutation of the colors you wanted by defining:


PERMUTE(a,b,c,N)
{
GATHER(a,b,c,N)
SHIFT(c,b,a,N)
SHIFT(b,a,c,N)
SPREAD(a,c,b,N)
}


This will not work, I think, for non-cyclic permutations [a,b,c].

Well, that's it. It is more complicated than the solution to the 1 color Tower of Hanoi, and it may not be optimal, but it clearly works. Perhaps some use could be made of the fact that GATHER and SPREAD keep the color permutation information in a recoverable form to make a true "next step" algorithm.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
Algorithm for 3-color Tower of Hanoi mr_homm Feb-12-06 TOP
  RE: Algorithm for 3-color Tower of Hanoi alexb Feb-12-06 1
  RE: Algorithm for 3-color Tower of Hanoi alexb Feb-22-06 2
     RE: Algorithm for 3-color Tower of Hanoi alexb Feb-22-06 3
         RE: Algorithm for 3-color Tower of Hanoi mr_homm Feb-23-06 4
             RE: Algorithm for 3-color Tower of Hanoi alexb Feb-23-06 5
                 RE: Algorithm for 3-color Tower of Hanoi mr_homm Feb-25-06 6
                     RE: Algorithm for 3-color Tower of Hanoi alexb Feb-25-06 7
                         RE: Algorithm for 3-color Tower of Hanoi mr_homm Mar-05-06 8
                             RE: Algorithm for 3-color Tower of Hanoi alexb Mar-05-06 9
                                 RE: Algorithm for 3-color Tower of Hanoi mr_homm Mar-05-06 10
                                     RE: Algorithm for 3-color Tower of Hanoi mr_homm Mar-06-06 11

Conferences | Forums | Topics | Previous Topic | Next Topic
alexb
Charter Member
1792 posts
Feb-12-06, 07:17 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #0
 
   Stuart, thank you.

It's in my "to do " pipe now.

Alex


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1792 posts
Feb-22-06, 02:49 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
2. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #0
 
   I've put it in

https://www.cut-the-knot.org/Curriculum/Combinatorics/Hanoi3c.shtml

Works as advertised, indeed. Thank you. Your Description is at

https://www.cut-the-knot.org/recurrence/TricolorHanoiAuto.shtml

Now, it begs for improvement. For, it is clearly redundant.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1792 posts
Feb-22-06, 07:18 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
3. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #2
 
   Now that I looked at it, there is definitely something wrong with the writeup. The two definitions of both GATHER and SPREAD are identical, except for the recursive part. If the latter is included there is huge inefficiency. If it's omitted (which gives the nonrecursive definition), the algorithm does not go through.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Feb-23-06, 07:01 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
4. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #3
 
   >Now that I looked at it, there is definitely something wrong
>with the writeup. The two definitions of both GATHER and
>SPREAD are identical, except for the recursive part. If the
>latter is included there is huge inefficiency. If it's
>omitted (which gives the nonrecursive definition), the
>algorithm does not go through.

Yes, I see that there is an error in the redefinition of GATHER and SPREAD. When I originally defined them non-recursively, I had GATHER changing the stack size from k to k+1, and SPREAD changing the stack size from k+1 to k. These were the simplest definitions to present, but when I defined the recursive forms of GATHER and SPREAD, I wanted them to produce or destroy a stack of size k. Therefore, I should have used k-1 in place of k in the bodies of the recursive definitions (except in the recursive calls themselves, of course).

Since making these changes in the recursive definitions without also making them in the non-recursive ones would mess up the exposition, I suggest the following change:

Replace this text:

-------------------------------------

3: GATHER collects the top layer of disks from a base onto the bottom of a stack of depth k located at peg a, leaving the resulting larger stack on peg c, and using peg b as a temporary location. It can be defined non-recursively by calling SHIFT:


GATHER(a,b,c,k)
{
MOVE(b,c)
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
}


4: SPREAD is the inverse of GATHER, and distributes the bottom 3 disks from a stack of depth k+1 on peg a to form a new layer on top of a base, and leaves the reduced stack on peg c, using peg b as a temporary location. It is defined much as GATHER:


SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
MOVE(a,b)
}


---------------------------------

with this:

--------------------------------

3: GATHER collects the top layer of disks from a base onto the bottom of a stack of depth k-1 located at peg a, leaving the resulting larger stack on peg c, and using peg b as a temporary location. It can be defined non-recursively by calling SHIFT:


GATHER(a,b,c,k)
{
MOVE(b,c)
SHIFT(a,b,c,k-1)
MOVE(a,c)
SHIFT(b,c,a,k-1)
}


4: SPREAD is the inverse of GATHER, and distributes the bottom 3 disks from a stack of depth k on peg a to form a new layer on top of a base, and leaves the reduced stack on peg c, using peg b as a temporary location. It is defined much as GATHER:


SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k-1)
MOVE(a,c)
SHIFT(b,c,a,k-1)
MOVE(a,b)
}


--------------------------------

and replace this text

--------------------------------


GATHER(a,b,c,k)
{
if k>0
{
GATHER(b,c,a,k-1)
}
MOVE(b,c)
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
}



SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k)
MOVE(a,c)
SHIFT(b,c,a,k)
MOVE(a,b)
if k>0
{
SPREAD(c,a,b,k-1)
}
}


-------------------------------

with this

-------------------------------


GATHER(a,b,c,k)
{
if k>1
{
GATHER(b,c,a,k-1)
}
MOVE(b,c)
SHIFT(a,b,c,k-1)
MOVE(a,c)
SHIFT(b,c,a,k-1)
}



SPREAD(a,b,c,k)
{
SHIFT(a,b,c,k-1)
MOVE(a,c)
SHIFT(b,c,a,k-1)
MOVE(a,b)
if k>1
{
SPREAD(c,a,b,k-1)
}
}


----------------------------------

Note that the calls to SHIFT now have k-1 and the IF statement now says k>1 instead of k>0. These are the only changes. The algorithm was very redundant because it was reaching one level too deep every time. I'm surprised that it worked at all with this error!

Thanks for taking the time to implement this algorithm for the 3 color tower of Hanoi page. The applet is really fun to watch (even if the algorithm was embarassingly redundant).

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1792 posts
Feb-23-06, 12:17 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
5. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #4
 
   >The algorithm was very redundant because it was
>reaching one level too deep every time. I'm surprised that
>it worked at all with this error!

Must be quite robust.

>Thanks for taking the time to implement this algorithm for
>the 3 color tower of Hanoi page.

Was there anything else? Actually, it took less time than formatting HTML.

>The applet is really fun
>to watch (even if the algorithm was embarassingly
>redundant).

I added a Stop and a OneStep button. So there is even more fun. I think there is now a good foundation for attacking the other problem.

Many thanks.

Alex


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Feb-25-06, 08:02 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
6. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #5
 
   >>it worked at all with this error!
>
>Must be quite robust.

That is what is so surprising. This is a very "rigid" algorithm, which does no seeking or checking, only assumes that the starting configuration is valid (i.e., is an allowed position for the algortithm) and takes steps which preserve the validity. Once the disk position is in an invalid state, there is no mechanism for finding a valid state (in fact, if such a mechanism existed, it would amount to the "next step" algorithm that we would ultimately like to find).

>
>I added a Stop and a OneStep button. So there is even more
>fun. I think there is now a good foundation for attacking
>the other problem.
>

Yes, this makes it much easier to play with and try out variations. One thing I tried is to put the disks into an invalid position by hand and then run single steps of the algorithm. This produced weird looking results, including having disk stacks that violate the smaller-above-larger rule. This is as expected of course, but it'shows that the algorithm is not so robust after all.

By the way, I still see some redundancies in the moves, but this is not due to any error in the presentation or implementation of the algorithm; the algorithm itself is simply not optimal, which I already suspected. I will have a try at increasing the efficiency of the existing algorithm, but if this is not easy, I think I will move along to thinking about a next-step algorithm. Already, I have some ideas about how to make one, but I need to look at the details to see if the ideas really can be made to work. I will post here if I come up with anything useful.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1792 posts
Feb-25-06, 08:45 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
7. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #6
 
   >Once the disk position is in an
>invalid state, there is no mechanism for finding a valid
>state

Right. For this reason, the One step button had to be disabled after a manual move. It was my omission that it was not. Thank you for drawing my attention to that.

>I will post here if I come up with anything useful.

I'll be looking forward.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Mar-05-06, 05:41 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
8. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #7
 
   I have been thinking some more about a next-step algorithm, and I think I see how to do it. However, it is not all that short, so I will post my thoughts in stages.

Stage 1:

First, let's reduce the problem to its essentials. Since larger disks are never on top of smaller disks, the disks can be thought of as layers, like geological strata. The disks below a given layer may be distributed unevenly, so that the layer may not be flat, but that does not affect the moves available to disks in that layer. Therefore, for a given layer, the positions of all disks below it are irrelevant.

As for the disks above the given layer, they must all be gathered into a single stack before any move at all can be made in the given layer. Every move has a start and end peg, which must be free, and an unused peg, where the stack must sit. Therefore, any proposed move within a given layer has as a precondition, that the smaller disks are already gathered into a single stack on the unused peg.

Since the moves are colorblind, we can separate the problem into two parts: (a) how to move disks to a specific geometric position, irrespective of their colors, and (b) how to permute the colors of a geometric position.

Stage 2:

Working on task (a) above, let us try to find a convenient representation of the geometric position of a layer. Here is a good visualization, which is similar to ones I have seen used for other peg games: Let [n1,n2,n3] represent the number of disks (of the given layer) on pegs 1,2, and 3, and let (a-->b) represent a single disk move from peg a to peg b. Then the possible positions and moves form a triangular grid, where the numbers of disks on the pegs form barycentric coordinates for the grid points.

[030]
/ \
/ \
/ \
/ C \
/ \
[120]-------[021]
/ \ / \
/ \ (1,3) / \
/ \ / \
/ C \ / C \
/ \ / \
[210]-------[111]-------[012]
/ \ / \ / \
/ \ (2,3) / \ (1,2) / \
/ \ / \ / \
/ C \ / C \ / C \
/ \ / \ / \
[300]-------[201]-------[102]-------[003]


On this diagram, (1-->2) is a step upwards parallel the left side of the triange, (1-->3) is a step right parallel to the bottom, and (2-->3) is a step down parallel to the right side. The reverse moves are steps in the reverse direction. This makes it very easy to see the shortest sequence of moves from one geometric arrangement to another.

Since each move requires first restacking all the smaller disks onto the unused peg, the cost of a longer path is significantly more moves of the smaller disk layers. It may happen that the smaller disks are in an arrangement that makes them cheaper to stack onto one peg than another, but if this requires one more move at the current layer, the advantage will be lost, so in all cases the shortest path is preferred. It may also happen that there are two possible shortest paths, in which case the one with the cheaper stacking cost for the smaller disk layers would be preferred. It turns out that this case is eliminated by color order considerations below.

Step 3:

The small triangles marked with a letter "C" are color commutative, i.e., taking a route of moves around one of these triangles (in either direction) puts the disks of the current layer back in the same geometric arrangement and also in the same color order. This is because these triangles represent moves which take a single disk, and hop it around all three pegs and back home again, without moving any of the other disks in the layer. The triangles marked with a permutation symbol permute the colors. If you start from the central position [111] and move around the triangle marked (1,3) either clockwise or counter clockwise, and return to [111] the disks will return to their original geometric arrangement, but with the disks on pegs 1 and 3 switched. Similarly, traversing the triangles marked (1,2) and (2,3) will switch the disks on the corresponding pegs.

Now in order to make use of this, we have to have a way of deciding which permutation we currently have, and which one we want. However, since the geometric arrangements look different, how are we to know that


Red
White
Blue (empty) (empty)

is the same permutation as


Red White Blue
?

The way to decide this is to define a standard geometric position and standard order, and then INDUCE a standard color order on the other positions. In order to do that, we have to have a unique path from the standard position to each other position, and that means we must extract a TREE (subgraph with no loops) from our triangular graph above. There is no unique choice, of course, but here is one that I think is nicely symmetrical: Choose the central position [111] as standard, and the color order RWB as the standard order for this position. Then use the following tree to connect other positions to the center:

[030]
/
/
/
/ C
/
[120] [021]
\ /
\ (1,3) /
\ /
C \ / C
\ /
[210]-------[111]-------[012]
/ \ \
(2,3) / \ (1,2) \
/ \ \
C / C \ C \
/ \ \
[300]-------[201] [102] [003]

That's as far as I've got yet. More steps to follow.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1792 posts
Mar-05-06, 07:41 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
9. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #8
 
   Stuart,

for a few days I'll be tending to my sick sister and won't have time to look into this. Please pay no heed.

Alex


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Mar-05-06, 06:25 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
10. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #9
 
   Alex,

>for a few days I'll be tending to my sick sister and won't
>have time to look into this. Please pay no heed.

For what they are worth, my good wishes go to you and your sister. I will post further stages of the algorithm when I have worked out the details. Nothing is final yet anyway, and there is no hurry.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Mar-06-06, 08:15 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
11. "RE: Algorithm for 3-color Tower of Hanoi"
In response to message #10
 
   Clarification to Stage 2:

When I said that shorter paths were less costly, I neglected to specify that it is the number of corners, not the number of edges, in the path that determines the cost. To proceed from one [300] to [030] for instance is a path of three edges, but in only involves moving disks from peg 1 to peg 2, and so the stack of smaller disks can continue to sit on peg 3 during the whole process. There is always an initial cost no matter what the first path edge is, because the smaller disks must be stacked out of the way first. This initial cost is usually unknown, because the distribution of smaller disks could be anything.

However, after the first edge, there is no further cost until the path turns a corner. At that time, the smaller disks need to be restacked onto the peg that will be unused in the next edge. It doesn't matter whether it is a sharp turn (120 degrees) or a lazy turn (60 degrees), because in either case, the smaller disks will need to be restacked once. Therefore the cost of a path is always the c*k + u, where c is the number of corners, k the cost of moving a stack of smaller disks out of the way (which is always the same and depends only on the height of the stack of smaller disks), and u is the unknown cost of moving an arbitrary arrangement of smaller disks onto a stack out of the way.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK