Problem statement as in the book:

Let's look first at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:

The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.

Just reading this and the next paragraph and I stared with solving the problem, with a pen and a paper. The next paragraph that I read is also interesting.

Lucas furnished his toy with a romantic legend about a much larger Gold -wow. Tower of Brahma, which supposedly has 64 disks of pure gold resting on three diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end.

"The Tower of Brahma", Brahma is an Indian God. Now it interests me even more.

Trial runs now:

To make it easy myself to understand, I stared with small numbers of disks.

Let,

n be number of disks

m be number of moves -- this is what we’ll record.

(n=0)

Ha ha ha, without doing anything was able to say it would take no moves.

Thus, (m=0)

(n=1)

This just takes one move. Move the disk from first to last. To record my moves I would just name the pegs as A, the starting peg, B the swap peg, C the target peg.

1:AC

Thus, (m=1)

(n=2)

This is also went easy, move smallest disk to peg B, then move other disk to Peg C and then place the smallest disk over the other disk. To make it easy for us to record let us name smallest disk as 1 and other in the increasing sequence.

1:AB-C

2:A-C-

(“-“means no move for this disk)

Thus, (m=3)

(n=3)

This also goes fine.

1:AC-B-A-C

2:A-B---C-

3:A---C---

Thus, (m=7)

Now, I saw something interesting, there are two patterns in with these disks are moving, ABCA and ACBA. Let us see if this holds well with n=4.

(n=4)

1:AB-C-A-B-C-A-B-C

2:A-C---B---A---C-

3:A---B-------C---

4:A-------C-------

Yes, moving pattern still holds good.

(m=15)

Getting the above solution took me some good time. I failed to get it in the first run. It was going too astray, so I stared again. Anyway I managed to get the solution in 15 moves eventually. This also has the same pattern going on. Now there is something else is quite evident, biggest disk always moves A to C and it only gets to move once.

By now I have one thing clear in my mind, for first time move (n-1)th heap on B or to take it a step ahead move (n-2)th heap on C, and so on.

Now, let us try n=5.

(n=5)

1: AC-B-A-C-B-A-C-B-A-C-B-A-C-B-A-C

2: A-B---C---A---B---C---A---B---C-

3: A---C-------B-------A-------C---

4: A-------B---------------C-------

5: A---------------C---------------

(m=31)

This also follows our pattern ABCA and ACBA. By now I can see another interesting sequence for number of moves per disk.

For,

(n=5)

Number of moves 5th disk are 1

4: 2

3: 4

2: 8

1: 16

(n=4)

4: 1

3: 2

2: 4

1: 8

(n=3)

3: 1

2: 2

1: 4

(n=2)

2: 1

1: 2

(n=1)

1: 1

And this should and does sum up to 31, 15, 7, 3, and 1 respectively. Now this is interesting these numbers are from a series 2^0, 2^1, 2^2, 2^3 and 2^4. And most of us know Sum of “X^Y” for Y=0 to n-1 is “(X^n) – 1”.

Thus number of moves need to move an “n” disk heap from A to C are “(2^n) -1”. That’s “2^0 - 1 = 0”, “2^1 - 1 = 1”, “2^2 - 1 = 3”, “2^3 - 1 = 7”, “2^4 - 1 = 15”and “2^5 - 1 = 31”.

Now I am In search of an algorithm that can be applied to any number of disks.

Let us try moving 4 disks, that is:

(A: 4321, B: -, C: -)

Move 4321 heap on C, from A.

Means,

Move 321 heap on B, from A

Move 4 to C, from A.

Move 321 heap on C, from B, over 4.

(A: -, B: -, C: 4321)

(A: 4321, B: -, C: -)

Move 321 heap on B, from A

Means,

Move 21 heap on C, from A.

Move 3 to B, from A.

Move 21 heap on B, from C. over 3.

(A: 4, B: 321, C: -)

(A: -, B: 321, C: 4)

Move 321 heap on C, from B, over 4.

Means,

Move 21 heap on A, from B.

Move 3 to C, from B, over 4.

Move 21 heap on C, from A, over 34.

(A: -, B: -, C: 4321)

(A: 4321, B: -, C: -)

Move 21 heap on C, from A.

Means,

Move 1 to B, from A.

Move 2 to C, from A.

Move 1 to C, over 2, from B.

(A: 43, B: -, C: 21)

(A: 4, B: 3, C: 21)

Move 21 heap on B, from C. over 3.

Means,

Move 1 to A, from C, over 4.

Move 2 to B, from C, over 3,

Move 1 to B, from A, over 23

(A: 4, B: 321, C: -)

(A: -, B: 321, C: 4)

Move 21 heap on A, from B.

Means,

Move 1 to C, from B, over 4.

Move 2 to A, from B.

Move 1 to A, from C, over 2.

(A: 21, B: 3, C: 4)

(A: 21, B: -, C: 43)

Move 21 heap on C, from A, over 34.

Means,

Move 1 to B, from A.

Move 2 to C, from A, over 34.

Move 1 to C, from B, over 234.

(A: -, B: -, C: 4321)

So, we can see something in this move pattern that is we have 3 classifications of the pegs. Namely, resting peg, swap peg, and target peg let us denote those as R(n), S(n), and T(n) respectively for nth disk.

Now we can say (more generalized form),

Move nth heap on T (n), from R (n)

Means,

Move (n-1)th heap on S(n), from R(n)

Move n to T(n), from R(n).

Move (n-1)th heap on T(n), from S(n), over n.

Move 0th heap on T (0), from R (0).

Means,

Move nothing

Now we’ll just leave this recursive solution as is, and look for some patterns, knowing recursive solutions are slow.

Let me try a non-recursive solution also and remember we had a Pattern ABCA, and ACBA there is another pattern of moves. Smallest disk moves every alternate move, that is starting from the first move and first move is always for the smallest.

Moves of disk,

1: 1-3-5-7-9-11 and so on and so forth.

2: -2---6---10---14 and so on and so forth.

3: ---4-------12-------18 and so on and so forth.

4: -------8---------------24 and so on and so forth.

--

Logically nth, disk should first move after (n-1)th heap is moved on S(n) and that’s “(2^(n-1)-1)+1”th move. See if “321” formation has to happen on B for 4 to get on C. We know by now it will take 7 moves before 4 moves. Thus it is “2^(n-1)”th move or for 4 its 8th move. So the first move of any disk isn’t a function of number of disks.

First move of nth disk happens at “2^(n-1)”th move of the disk system.

Let us see when nth disk will move the second time, let us take the moves of moving 4 disks.

(A:4321, B: -, C: -)

(A:432, B: 1, C: -)

(A:43, B: 1, C: 2)*

(A:43, B: -, C: 21)

(A:-4, B: 3, C: 21)

(A:41, B: 3, C: 2)

(A:41, B: 32, C: -)*

(A:4, B: 321, C: -)

(A:-, B: 321, C: 4)

(A:-, B: 32, C: 41)

(A:2, B: 3, C: 41)*

(A:21, B: 3, C: 4)

(A:21, B: -, C: 43)

(A:2, B: 1, C: 43)

(A: -, B: 1, C: 432)*

(A: -, B: -, C: 4321)

(“*” marks the move of disk 2)

1

2

4 3

+-------+-------+---

1

2

3 4

+-------+-------+---

--

See the recursive algorithm we made, that says move “n-1”th heap on S(n), and then move nth disk to T(n).

1

2

3

4

+-------+-------+---

--

And later move “n-1”th heap to T(n).

3 1

4 2

+-------+-------+---

1

4 3 2

+-------+-------+---

(First time “n-1”th disk moves is after “n-2”th heap was moved to T(n)=C )

1

2

4 3

+-------+-------+---

(Moving “n-2”th heap over “n-1”th disk)

1

2

3 4

+-------+-------+---

(nth disk moves to T(n) )

1

2 3 4

+-------+-------+---

(“n-2”th heap again moves to R (n) to free “n-1”th disk to move to T(n) )

1 3

2 4

+-------+-------+---

(second time “n-1”th disk moves)

--

Meanwhile, first time “n-1”th disk moved was “2^(n-2)” after that it took ( ( 2^(n-2) ) - 1) moves to get “n-2”th heap over it. Then one move for n to move to T(n). Then ( ( 2^(n-2) ) - 1) moves to set “n-1”th disk free to move on nth disk, that is making “n-2”th heap on R(n). Thus moves after first move are “ ( ( 2^(n-2) ) - 1) + 1 + ( ( 2^(n-2) ) - 1) = (2 ^(n-1) -1)”. This is for “n-1”th disk, so for nth disk it should be “2^n - 1”.

So, second move for 2 should be after “2^2 - 1=3”, for 3 should be “2^3 - 1=7”, and for 4 should be “2^4 - 1=15”. Now we can say nth disk moves after this many moves, that is 2^n moves after first move or second move is that 2^(n-1)+2^n moves.

First two moves

1:1,3

2:2,6

3:4,12

4:8,24

And so on

Second move for nth disk is at 2^(n-1)+2^n move of the disk system.

Now let us look for the mth move of an nth disk. Suppose we again have 4 disks:

(A:4321, B: -, C: -)

(A:432, B: 1, C: -)

(A:43, B: 1, C: 2)*

(A:43, B: -, C: 21)

(A:-4, B: 3, C: 21)

(A:41, B: 3, C: 2)

(A:41, B: 32, C: -)*

(A:4, B: 321, C: -)

(A:-, B: 321, C: 4)

(A:-, B: 32, C: 41)

(A:2, B: 3, C: 41)*

(A:21, B: 3, C: 4)

(A:21, B: -, C: 43)

(A:2, B: 1, C: 43)

(A: -, B: 1, C: 432)*

(A: -, B: -, C: 4321)

This algorithm is target driven, 4 needs to reach C (Target) for that it needs “123” heap on B (Swap) for this 3 needs “12” heap on C (Swap for 3, as its Target is B, from A). So after “(A:-, B: 321, C: 4)” move 3 needs 2 to go to A, and 2 makes 1 to go to C. So there is one thing clear, pack and unpack is going on. Let us see the movement of disk 1, on the first step 4 needs to go to C, thus instruction flows to 2 to move to C and then 2 wants 1 to move to B. Once 2 reaches C it asks, 1 to come over it. After this way for 3 is clear thus it moves, then 3 needs 2 over it. This would force 1 to move off 2 and then come back.

Leaving the first move every other move needs pack and unpack both.

Move (n-1)th heap on S(n)

Move n to T(n)

Move (n-1)th heap on T(n)

Move (n+1) to T(n+1)

Move (n-1)th heap on S(n)

Move n to T(n)

Move (n-1)th heap on T(n)

Move (n+2) to T(n+2)

Move (n-1)th heap on S(n)

Move n to T(n)

Move (n-1)th heap on T(n)

Move (n+1) to T(n+1)

Move (n-1)th heap on S(n)

Move n to T(n)

Move (n-1)th heap on T(n)

This shows after every unpack/pack we have movement of some higher number disk and we can quite evidently see between any two moves of nth disk we have “Move (n-1)th heap” twice plus one more move. This is just the same as second move. That is 2^n-1 or we can say every 2^n moves nth disk will move.

So,

mth move of nth disk, M(m,n) = 2^(n-1) + (m-1)2^n

or M(m,n) = 2^n( 1/2 + (m-1) )

or M(m,n) = 2^n(m-1/2)

Let us verify for few values of m and n,

M(1,1)=1

M(3,2)=4(2.5)=10

M(2,4)=16(1.5)=24

Now let us look at the direction of movement, remember ABCA and ACBA. Let us try to prove that. Before we go ahead let us look at the recursive algorithm we deduced.

Move nth heap on T (n), from R (n)

Means,

Move (n-1)th heap on S(n), from R(n)

Move n to T(n), from R(n).

Move (n-1)th heap on T(n), from S(n), over n.

Move 0th heap on T (0), from R (0).

Means,

Move nothing

Now if R (n) =A, T (n) =C, so S (n) =B

And know T (n-1) = S (n), as we start with all are at R (n), so R (n-1) =A, Thus S (n-1) =C. One nth disk moves to T (n) =C, “n-1”th disk will be at S (n) =B, now new target for n-1 is T (n) =C and S (n-1) = R (n) = A

Moves:

n:A(B)C

n-1:A(C)B(A)C

Notation: “n:A(B)C” means A is the resting peg, B is the swap peg and C is the target peg for the nth disk.

Moves:

n-1:A(C)B

n-2:A(B)C(A)B

Moves:

n-1:B(A)C

n-2:B(C)A(B)C

Move let us see how many ways any disk can move,

A(C)B, B(A)C,C(B)A,A(B)C,C(A)B,B(C)A

The above moves are part of the patterns we saw before.

ABCA has A(C)B, B(A)C,C(B)A

ACBA has A(B)C,C(A)B,B(C)A

If we say, ABCA as clockwise and ACBA as anticlockwise, visualize by keeping pegs in a triangle. We will have to prove disk moving in one formation only sticks to the same formation for whole run.

Let x can be A, B or C.

Moves

n: x(x-1)x+1

n-1: x(x+1)x-1,x-1(x)x+1

n: x(x+1)x-1

n-1: x(x-1)x+1,x+1(x)x-1

So we can see if nth disk wants to move from x to x+1, then it needs to move “n-1”th disk from x to x-1 to x+1, or to say x to x-1 to x-2. For nth disk’s move from x to x-1, it is x to x+1 to x-1, or to say x to x+1 to x+2.

We can see x(x+1)x-1 and x-1(x)x+1 move in the same direct (anticlockwise)and so do x(x-1)x+1 and x+1(x)x-1 (clockwise).

So we slow if nth disk moves clockwise, “n-1”th disk moves anticlockwise and visa versa. Now let us look at the bigger picture. Largest Disk always moves from A to C that is anticlockwise. This moves the heap over it from two times, that also in clockwise direction. This would make next heap four times in anticlockwise direction and so on so forth.

This even gives the proof for the series we saw before, 2^0, 2^2…, 2^n-1 as number of moves for disk in descending order.

So, we can say now

If largest disk is even, then all even disks move in anticlockwise direction and all odd disks move on clockwise direction. Now as smallest disk always moves first, the first movement will be clockwise, that is AB.

Else if largest disk is odd, then all odd disks move in anticlockwise direction and all even disks move on clockwise direction. Thus the first movement will be anticlockwise, that is AC.

Let us make a formula to get the disk direction, if N the largest disk and n is the target disk,0 < n <=N.

Direction, D(N,n) = (N-n) mod 2

0 will mean anticlockwise, that is ACBA

1 will mean clockwise, that is ABCA

From previous discussion we even know that mth move of nth disk happens at “2^n (m-1/2)”. Now we even know how nth disk move in an N disk set.

M(m,n) = 2^n(m-1/2)

or

m=M(m,n)/2^n+1/2

This M(m,n) is nothing but kth move of this disk system. Let us write it again with k.

m=k/2^n+1/2

This would give us a fractional number, and will have to discard the fraction part of it to get the location of nth disk at kth disk system move.

m=floor(k/2^n+1/2)

As all disks are on A to begin with, we can do something more.

Let peg A=0, B=1, C=2

Peg location of nth disk on kth move, P(n,k) = floor(k/2^n+1/2) mod 3. So if I make to define a function that return a list, [ACB] or [ABC] depending on the input, D(N,n) will be an input to that.

L(a) = [ACB] for a =0, And

L(a) = [ABC] for a =1

Now, P(n,k) is the index in the returned list for some value of N and n. Now if L(a)[i] means ith index of list L(a).

Then location of nth disk, in a set of N disks, on the kth system move,

W(n,N,k) = L( D(N,n) ) [P(n,k)]

or

W(n,N,k) = L( (N – n) mod 2 ) [floor( (k/2^n) + (1/2) ) mod 3]

where,

L(a) = [ACB] for a =0, And

L(a) = [ABC] for a =1

Let us try a few,

W(2,4,8)=L(4-2 mod 2)[floor(8/2^2+1/2) mod 3] = L(0)[2] = B

W(4,5,24)=L(5-4 mod 2)[floor(24/2^4+1/2) mod 3] = L(1)[2] = C

Let us now try “The Tower of Brahma”

W(64,64,2^63)=L(0 mod 2)[ floor( 2^63/2^64+1/2 ) mod 3 ] = L(0)[1] = C, the first and the last time the largest disk of Brahma’s tower moves or it is half way to end of the world.

Now we have a mathematical representation of the recursive algorithm we had deduced before.

Before I sign off, don't you see this disk system recording time like a clock? Assuming moving any disk takes the same amount of time.

## No comments:

Post a Comment