How can one solve the tower of hanoi problem if there are discs of similar width in it?

1.2k Views Asked by At

For example a line with '1111' represents a disc with diameter of length 4. Similarly a line with '111' represents a disc with diameter of length 3.

Below is the representation of a tower that has 5 discs. ground disc has a diameter 9, disc '2' d=5, disc '3 and 4' d=3 and disc '4' has d = 1.

$1$

$111$

$111$

$ 11111$

$111111111$

How Many moves will it take to move these kind of towers?

3

There are 3 best solutions below

0
On

If you have two equal disks, then as long as they're on different pegs, you can't ever move any larger disk. So it makes no sense to stay in this situation longer than necessary. The optimal solution must therefore be to keep all disks of the same size together, only splitting them up temporarily when you need to move all of them from one peg to another, which then needs to happen one at a time.

This reduces the problem to the usual Towers of Hanoi problem with one disk per size class. You just need to multiply the number of moves each disk makes in the standard problem (namely $2^n$ where $n$ is the number of larger sizes) by the number of disks of a given size, and then add everything together.

0
On

It is possible to move such a tower faster: First "merge" equal sized disks into one, then solve the problem for the reduced number of disks, then replace each move of a disk obtained by merging $k$ disks with moving the $k$ merged disks. In your example, we first need to move $4$ disks, which takes $2^2-1=15$ moves. Among these, $4$ moves concern the "III" disk, and get replaced with $8$ single moves, resulting in a total of $15-4+8=19$ moves (instead of $31$ moves).

1
On

After considering all the suggested methods and some calculations I came up with this recursive call:

We all know that when there are no blocks of similar width we use the call : $T_{n+1} = 2T_{n}+1$ So some insight will clearly tell you that in case the block is of same width as the previous it's call would be $T_{n+1} = T_{n}+1$