Solve Towers of Hanoi: An Algorithm Example w/ Recursion

[mathmari]

Hey!

The Towers of Hanoi problem consists of three pegs $A$, $B$ and $C$, and $n$ squares of varying size. Initially the squares are stacked on peg$A$ in order of decreasing size, the largest square on the bottom. The problem is to move the squares from peg$A$ to peg$B$ one at a time in such away that no square is ever placed on a smaller square. Peg$C$ may be used for temporary storage of squares.

I have to write an algorithm to solve this problem.

I made an example for $n=3$. The moves are the following:

Move the square from pegA to pegB
Move the square from pegA to pegC
Move the square from pegB to pegC
Move the square from pegA to pegB
Move the square from pegC to pegA
Move the square from pegC to pegB
Move the square from pegA to pegB

right?? (Wondering)

How could we write it as an algorithm?? Maybe using recursion?? But how?? (Wondering)

 

[Evgeny.Makarov]

To move $n$ squares from $X$ to $Y$ using $Z$, move $n-1$ squares from $X$ to $Z$ using $Y$, move the last square from $X$ to $Y$, and finally move $n-1$ squares from $Z$ to $Y$ using $X$.

 

[mathmari]

To move $n$ squares from $X$ to $Y$ using $Z$, move $n-1$ squares from $X$ to $Z$ using $Y$, move the last square from $X$ to $Y$, and finally move $n-1$ squares from $Z$ to $Y$ using $X$.

So, is it as followed:

procedure move(n, X, Z, Y)
if n=1 then
   printf("%d->%d", X, Y);
move(n-1, X, Y, Z);
move(1, X, Z, Y)
move(n-1, Z, X, Y)

Is it correct? (Wondering)

Is the execution time of the algorithm in terms of the number of times a square is moved, given from the recurrence:
$$T(n)=2T(n-1)+2$$
?? (Wondering)

I have to prove also that $2^n-1$ moves are both necessary and sufficient for the solution to this problem. How could I do that?? (Wondering)

 

[Evgeny.Makarov]

procedure move(n, X, Z, Y)
if n=1 then
   printf("%d->%d", X, Y);
move(n-1, X, Y, Z);
move(1, X, Z, Y)
move(n-1, Z, X, Y)

You need either a [m]return[/m] or an [m]else[/m] statement after [m]if[/m].

Is the execution time of the algorithm in terms of the number of times a square is moved, given from the recurrence:
$$T(n)=2T(n-1)+2$$

Why $+2$ and not $+1$?

I have to prove also that $2^n-1$ moves are both necessary and sufficient for the solution to this problem. How could I do that??

Sufficiency follows from the fact that $2^n-1$ is the solution to the recurrence equation above. I can't say how to prove necessity right now. I would read some sources starting from Wikipedia.

 

[soroban]

Hello, mathmari!

The Towers of Hanoi problem consists of three pegs $A$, $B$ and $C$, and $n$ disks of varying size.
Initially the disks are stacked on peg $A$ in order of decreasing size, the largest disk on the bottom.
The problem is to move all the disks from peg $A$ to another peg one at a time in such a way
that no disk is ever placed on a smaller disk

I have to write an algorithm to solve this problem.

I solved this problem many years ago.
It has a very simple procedure.
I assume you can modify it for your algorithm.

The smallest disk (#1) is always moved to the right.
. . From peg A, to peg B, to peg C, then back to peg A, to peg B, and so on

The smallest disk is moved as described on the 1st, 3rd, 5th, 7th, etc. move.

The even-numbered moves will be the only available legal move.

I'll demontrate with 3 disks.

Start

$$\begin{array}{ccc} \boxed{1} & | & | \\ \boxed{\;2\;} & | & | \\ \boxed{\;\;3\;\;} & | & | \\ \hline A & B & C \end{array}$$Move 1 to B, 2 to C

$$\begin{array}{ccc}| & |& | \\ |&| & | \\ \boxed{\;\;3\;\;} & \boxed{1} & \boxed{\;2\;} \\ \hline A & B & C \end{array}$$Move 1 to C, 3 to B

$$\begin{array}{ccc}|&|&| \\ | & | & \boxed{1} \\ | & \boxed{\;\;3\;\;} & \boxed{\;2\;} \\ \hline A&B&C \end{array}$$Move 1 to A, 2 to B

$$\begin{array}{ccc}|&|&| \\ |&\boxed{\;2\;} & | \\ \boxed{1} & \boxed{\;\;3\;\;} & | \\ \hline A&B&C\end{array}$$Move 1 to B

$$\begin{array}{ccc}| & \boxed{1} & | \\ |&\boxed{\;2\;} & | \\ | & \boxed{\;\;3\;\;}& | \\ \hline A&B&C \end{array}$$

 

[mathmari]

You need either a [m]return[/m] or an [m]else[/m] statement after [m]if[/m].

So, should it be as followed??

procedure move(n, X, Z, Y)
1.   if n=1 then
2.       printf("%d->%d", X, Y);
    else
3.       move(n-1, X, Y, Z);
4.       move(1, X, Z, Y)
5.       move(n-1, Z, X, Y)

(Wondering)

Why $+2$ and not $+1$?

Is it as followed??

$3: T(n-1)$
$4: 1$
$5: T(n-1)$

$\Rightarrow T(n)=2T(n-1)+1$

$T(1)=1$

(Wondering)

Sufficiency follows from the fact that $2^n-1$ is the solution to the recurrence equation above. I can't say how to prove necessity right now. I would read some sources starting from Wikipedia.

To show that $2^n − 1$ moves are necessary and sufficient to solve the Towers of Hanoi problem without having a specific algorithm, do we have to show this by induction?? (Wondering)

 

[Evgeny.Makarov]

So, should it be as followed??

procedure move(n, X, Z, Y)
1.   if n=1 then
2.       printf("%d->%d", X, Y);
    else
3.       move(n-1, X, Y, Z);
4.       move(1, X, Z, Y)
5.       move(n-1, Z, X, Y)

Yes.

Is it as followed??

$3: T(n-1)$
$4: 1$
$5: T(n-1)$

$\Rightarrow T(n)=2T(n-1)+1$

$T(1)=1$

Yes.

To show that $2^n − 1$ moves are necessary and sufficient to solve the Towers of Hanoi problem without having a specific algorithm, do we have to show this by induction?

Why would you want to avoid concrete algorithms? Since this algorithm has complexity $2^n − 1$, the optimal complexity is $\le2^n − 1$. To prove the converse inequality, note that to move the largest disk from $X$ to $Y$, all other disks have to be on $Z$. That is, any algorithm that solves the configuration $(n,0,0)$ must go though the configuration $(1,0,n-1)$, just like the algorithm above does. Using this idea, it should be possible to write an inductive proof than any algorithm uses at least as many steps.

 

[mathmari]

Why would you want to avoid concrete algorithms?

I thought that I have to because the two questions (writing the algorithm and proving that the neccesary and sufficient number of moves is $2^n-1$) are in different exercises.

Since this algorithm has complexity $2^n − 1$, the optimal complexity is $\le2^n − 1$. To prove the converse inequality, note that to move the largest disk from $X$ to $Y$, all other disks have to be on $Z$. That is, any algorithm that solves the configuration $(n,0,0)$ must go though the configuration $(1,0,n-1)$, just like the algorithm above does. Using this idea, it should be possible to write an inductive proof than any algorithm uses at least as many steps.

So, I have to prove by induction that the number of moves to solve the Tower of Hanoi problem is at least $2^n-1$ ($T(n)\geq 2^n-1$ ), right?? (Wondering)

If $n=0$ we don't have to do anything: $T(0) \geq 2^0-1=0 \checkmark$

We suppose that it stands for $n=k$, that means that when we have $k$ squares, we have to do at least $2^k-1$ moves.

When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$. Then we have to move the last square from $X$ to $Y$. Then we have to move the $k$ squares from $Z$ to $Y$, right?? (Wondering)

But how could I show that these are at least $2^{k+1}-1$ moves?? (Wondering)

 

[Evgeny.Makarov]

I thought that I have to because the two questions (writing the algorithm and proving that the neccesary and sufficient number of moves is $2^n−1$) are in different exercises.

Well, this does not mean you can't use a solution to another exercise.

We suppose that it stands for $n=k$, that means that when we have $k$ squares, we have to do at least $2^k-1$ moves.

When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$. Then we have to move the last square from $X$ to $Y$. Then we have to move the $k$ squares from $Z$ to $Y$, right?? (Wondering)

But how could I show that these are at least $2^{k+1}-1$ moves?

So, assume the distance from Boston's Logan International Airport to New York's LaGuardia airport is at least 190 miles, the distance from the airport to the Pennsylvania train station (still in New York) is 5 miles and the distance from there to Washington, D.C.'s Union Station is at least 200 miles. Please tell me I don't have to explain that if you have to travel from Boston to Washington, D.C. through LaGuardia airport and Penn stattion, then you travel at least $190+5+200$ miles.

 

[mathmari]

When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$ with $2^k-1$ moves.
Then we have to move the last square from $X$ to $Y$ with $1$ move.
Then we have to move the $k$ squares from $Z$ to $Y$ with $2^k-1$ moves.

Therefore, we have to do at least $2^k-1+1+2^k-1=2 \cdot 2^k-1=2^{k+1}-1$ moves.

Is it correct?? (Wondering)

 

[Evgeny.Makarov]

Yes, though you should say "at least" everywhere (also in the induction hypothesis) or alternatively you should say "exactly ... in the shortest solution" everywhere.

 

[mathmari]

Yes, though you should say "at least" everywhere (also in the induction hypothesis) or alternatively you should say "exactly ... in the shortest solution" everywhere.

So, to show that $2^n-1$ moves are both necessary and sufficient for the solution of the Tower of Hanoi problem, can I formulate it as followed?? (Wondering)

Since we have found an algorithm which has complexity $2^n − 1$, the optimal complexity is $\le2^n − 1$.

We have to prove that a lower bound of the number of moves that are needed to solve the Tower of Hanoi problem is $2^n-1$ ($T(n)\geq 2^n-1$ ).

If $n=0$ we don't have to do anything: $T(0) \geq 2^0-1=0 \checkmark$

We suppose that it stands for $n=k$, that means that when we have $k$ squares, we have to do at least $2^k-1$ moves.

When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$ with at least $2^k-1$ moves.
Then we have to move the last square from $X$ to $Y$ with at least $1$ move.
Then we have to move the $k$ squares from $Z$ to $Y$ with at least $2^k-1$ moves.

Therefore, we have to do at least $2^k-1+1+2^k-1=2 \cdot 2^k-1=2^{k+1}-1$ moves.

So, $2^n-1$ moves are both necessary and sufficient for the solution of the Tower of Hanoi problem.

 

[Evgeny.Makarov]

This is OK, but I would either define $T(n)$ beforehand (earlier in the thread you used $T(n)$ as the solution of the recurrence relation $T(n)=2T(n-1)+1$, which is not the sense it has here) or not use it at all.

 

[mathmari]

This is OK, but I would either define $T(n)$ beforehand (earlier in the thread you used $T(n)$ as the solution of the recurrence relation $T(n)=2T(n-1)+1$, which is not the sense it has here) or not use it at all.

Ok! So, should it be as followed??

Since we have found an algorithm which has complexity $2^n − 1$, the optimal complexity is $\le2^n − 1$.

We have to prove that a lower bound of the number of moves that are needed to solve the Tower of Hanoi problem is $2^n-1$.

If $n=0$ we don't have to do anything: So, the number of moves are $\geq 2^0-1=0 \checkmark$

We suppose that it stands for $n=k$, that means that when we have $k$ squares, we have to do at least $2^k-1$ moves.

When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$ with at least $2^k-1$ moves.
Then we have to move the last square from $X$ to $Y$ with at least $1$ move.
Then we have to move the $k$ squares from $Z$ to $Y$ with at least $2^k-1$ moves.

Therefore, we have to do at least $2^k-1+1+2^k-1=2 \cdot 2^k-1=2^{k+1}-1$ moves.

So, $2^n-1$ moves are both necessary and sufficient for the solution of the Tower of Hanoi problem.

(Wondering)

Or should I formulate the base of the induction in an other way?? (Wondering)

 

[Evgeny.Makarov]

So, should it be as followed?

The important thing is that this proof fully convinces you. Then if it does not convince someone else, at least you will be able to explain it to them. There are several things that I would still change, but there is no optimal text; the aim is a clear understanding in your head and its decent exposition as a text.

I would emphasize that the problem is symmetric w.r.t. pegs. That is, it takes the same number of steps to move $n$ disks from $X$ to $Y$ as from $Z$ to $X$ (and any other ordered pair of pegs). This is used in the proof because the induction hypothesis says simply, "Moving $k$ disks requires $\ge 2^k-1$ moves" without specifying the pegs, and this hypothesis is applied to two different pairs of pegs. In fact, now that I think of it, it is better to formulate the statement proved by induction (which is the same as the induction hypothesis) as follows: "If $U$, $V$ are two pegs and $W$ is the remaining peg, moving $k$ disks from $U$ to $V$ using $W$ requires $\ge 2^k-1$ moves". Here $U,V,W\in\{X,Y,Z\}$.

I would also point out where I use the induction hypothesis: "When we have $n=k+1$ squares we have to move the $k$ squares from $X$ to $Z$, which by induction hypothesis takes at least $2^k-1$ moves".

Then I would remind the reader that to move $k+1$ disks from $U$ to $V$ using $W$, we must move the top $k$ disks from $U$ to $W$ using $V$. This is the only way to move the largest disk from $U$ to $V$. Otherwise, it may not be clear why in the proof you are considering the same algorithm that you used to establish an upper bound on complexity. It may seem at first that there may be a completely different, faster algorithm.

These are some points that seem important to me personally and that I would therefore reflect in a proof. The important thing is that you fully understand your own proof.

Or should I formulate the base of the induction in an other way?

Yes, I would probably start with $k=1$ or explain that the problem to move 0 disks requires 0 moves by definition.

 

[mathmari]

I tried it again...

Since we have found an algorithm which has complexity $2^n − 1$, the optimal complexity is $\le2^n − 1$.

We have to prove that a lower bound of the number of moves that are needed to solve the Tower of Hanoi problem is $2^n-1$.

Base:
If $n=1$ we have to move one square from peg$X$ to peg$Y$. So, in this case one move is required, $1 \geq 2^1-1=1 \checkmark$.

Induction hypothesis:
If we have $n=k$ squares, we suppose that moving them from peg$U$ to peg$V$ using peg$W$ requires at least $2^k-1$ moves. ($U, V, W \in \{X,Y,Z\}$)

Inductive step:
To move $n=k+1$ squares from peg$X$ to peg$Y$ using peg$Z$, we must move the top $k$ squares from peg$X$ to peg$Z$ using peg$Y$ which by induction hypothesis takes at least $2^k-1$ moves.
Then we move the largest square from peg$X$ to peg$Y$ with $1$ move.
Then we move the $k$ squares from peg$Z$ to peg$Y$ using peg$X$ which by induction hypothesis takes at least $2^k-1$ moves.

Therefore, we have to do at least $2^k-1+1+2^k-1=2 \cdot 2^k-1=2^{k+1}-1$ moves. So, $2^n-1$ moves are both necessary and sufficient for the solution of the Tower of Hanoi problem. Is it better now?? (Wondering)

 

[Evgeny.Makarov]

Yes, I think it's fine.

 

[mathmari]

Yes, I think it's fine.

Ok! Thank you very much! (Smile)

If I want to write the algorithm in ALGOL, how can I write the command [m]printf("%d->%d", X, Y);[/m] ?? (Wondering)
Maybe [m]write "X"-> "Y" [/m] ?? (Wondering)

 

[Evgeny.Makarov]

Do you mean ALGOL as in Algol 60 or as in pseudocode?

 

[mathmari]

Do you mean ALGOL as in Algol 60 or as in pseudocode?

I mean ALGOL 60.

We have the following pseudocode:

procedure move(n, X, Z, Y)
   if n=1 then
       printf("%d->%d", X, Y);
    else
       move(n-1, X, Y, Z);
       move(1, X, Z, Y)
       move(n-1, Z, X, Y)

The equivalent ALGOL program is the following:

procedure MOVE(n, X, Z, Y)
    begin
       [COLOR="#FF0000"]if n=1 then write "X" -> "Y"[/COLOR]
       else
          begin
             MOVE(n-1, X, Y, Z);
             MOVE(1, X, Z, Y);
             MOVE(n-1, Z, X, Y) 
          end
    end

Is it correct?? (Wondering)

What about the red line?? (Wondering)

 

[Evgeny.Makarov]

       [COLOR="#FF0000"]if n=1 then write "X" -> "Y"[/COLOR]

I don't know ALGOL, but in most programming languages things in quotes are constants. Also, I doubt that [m]->[/m] is allowed outside of a string like this.

 

[mathmari]

I don't know ALGOL, but in most programming languages things in quotes are constants. Also, I doubt that [m]->[/m] is allowed outside of a string like this.

Could I write [m]write "Move square from pegX to pegY"[/m] ?? (Wondering)P.S. The language I use is called Pidgin ALGOL.

 

[Evgeny.Makarov]

Could I write [m]write "Move square from pegX to pegY"[/m] ?

in most programming languages things in quotes are constants.

And you want to write the value of $X$, not the letter "X".

P.S. The language I use is called Pidgin ALGOL.

Then you can probably write what you want.

 

[mathmari]

The prof said that we don't have to prove that $2^n-1$ moves are necessary for a specific algorithm, but that $2^n-1$ moves are necessary for each algorithm, even for one that has for example at a step $k$ squares at one peg and $m$ squares at an other. Does the following stand for each algorithm?? If we have one square we have to move it at least once. So, we need at least $1$ move.

When we have $n$ squares, we suppose that we need at least $2^n-1$ moves to move the squares.

When we have $n+1$ squares, we have to do the following:

We have to move the top $n$ squares away from the first peg with at least $2^n-1$ moves.
Then we have to move the largest square, the $n+1^{th}$ at least one, to move it to the right peg.
Then we have to move again the $n$ squares to the largest one with at least $2^n-1$ moves.
So, totally we need at least $(2^n-1)+1+(2^n-1)=2 \cdot 2^n-1=2^{n1}-1$ moves to move $n+1$ squares.

Is this correct?? Does this describe the method of each algorithm?? Or could I improve something?? (Wondering)

 

[Evgeny.Makarov]

I agree with you, and that's what I've been trying to say in post #15.

Then I would remind the reader that to move $k+1$ disks from $U$ to $V$ using $W$, we must move the top $k$ disks from $U$ to $W$ using $V$. This is the only way to move the largest disk from $U$ to $V$. Otherwise, it may not be clear why in the proof you are considering the same algorithm that you used to establish an upper bound on complexity. It may seem at first that there may be a completely different, faster algorithm.

 

[mathmari]

I agree with you, and that's what I've been trying to say in post #15.

So, does the version of post #16 also describe the method of each algorithm?? Or is the version of post #22 more generally?? (Wondering)