In a variant of the Towers of Hanoi puzzle, the three towers are labeled 0, 1, a

Question

In a variant of the Towers of Hanoi puzzle, the three towers are labeled 0, 1,
and 2, respectively. You are only allowed to move disks from a tower labeled i to the next one labeled (i + 1)
mod 3. You can imagine the towers as being arranged in a circular fashion, in which case, the constraint says
that you can only move disks in an anti-clockwise manner. So, for example, in order to move a disk from tower
0 to tower 2, you would have to first move it to tower 1, if both 0 1 and 1 2 are legal moves, and this
sequence would cost two moves instead of just one.
(a) Develop a divide and conquer algorithm for moving n disks from tower 0 to tower 2.
(b) Analyze the asymptotic number of moves your algorithm makes.

Explanation / Answer

Suppose the positions are 0-Source, 1-destination, 2- Auxillary

Step 1 Move n-1 disks from source to aux
Step 2 Move nth disk from source to dest
Step 3 Move n-1 disks from aux to dest

START
Procedure Hanoi(disk, source, dest, aux)

IF disk == 0, THEN
move disk from source to dest   
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF

END Procedure
STOP

The Tower of Hanoi problem with 3 pegs and n disks takes 2**n - 1 moves to solve, so if you want to enumerate the moves, you obviously can't do better than O(2**n) since enumerating k things is O(k)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.