Suppose you are forbidden to move any disk directly between peg 1 and peg 2; every move must involve peg 0. Describe an algorithm to solve this version of the puzzle in as few moves as possible. Exactly how many moves does your algorithm make

Answer / Explanation:

We should note that this is a recursive algorithm and therefore the algorithm will move the to n disks from the source peg src (either 1 or 2) to the destination Peg dst (either 1 or 2) where every move uses Peg 0.

We should also note that the forbidden peg never moves or changes, so we can code it into an algorithm which states thus:

F H (n, src, dst)

if n > 0

F H (n - 1, src, dst)

move disk n from Peg src to peg 0

F H (n - 1, dst, src)

move disk n from Peg 0 to peg dst

F H (n - 1, src, dst)

Where the initial call is F H (n, 1, 2).

Therefore, the number of moves satisfies the recurrence T (n) = 3T (n - 1) + 2. Therefore, We can easily verify by induction that T (n) = 3n - 1.

Here is a complete proof of correctness of the algorithm.

Let "n" be an arbitrary non-negative integer, and assume that F H (m, a, b) correctly moves "m" disks from "a" to "b" for every non-negative integer m
so assume n > 0. By the inductive hypothesis, the first recursive call correctly moves the top n-1 disks from src - to - dst.

The second line moves disk "n" from src - to peg 0 which is legal because all smaller disks are on peg dst.

By the inductive hypothesis, the second recursive call correctly moves the top n-1 disks from dst - to - src. The fourth line moves disk n from peg to dst which is legal because all smaller disks are on peg src. Finally, by the inductive hypothesis, the first recursive call correctly moves the top n-1 disks from src - to - dst.