Towers of Hanoi Problem (Question at bottom)

We consider the Towers of Hanoi puzzle which is a standard problem in programming exercise. In this lab, we are

more interested in the mathematics behind the solution to the Towers of Hanoi puzzle.

In general, to move a stack of n disks from post a (source post) to post c

(destination post), the idea is to move (by recursion) the top n 1 disks

from the source post a to post b (temporary post), next move the remaining

one disk from post a to post c, followed by moving (again using recursion)

the n 1 disks from the temporary post b to the destination post c. The

base case is when n = 1; we can move directly the single disk from the source

post to the destination post.

Following is a recursive program for solving the Towers of Hanoi puzzle. In

the program, we denote post a, post b, post c as post 0, post 1 and post 2

respectively.

import java.util.Scanner;

class Lab7

{

public static void makeMoves(int n, int s, int d, int t) {

if (n <= 0) return;

makeMoves(n-1,s,t,d);

System.out.println("move disk "+n+" from post "+s+" to post "+d);

makeMoves(n-1,t,d,s);

}

public static void main(String args[]) {

Scanner scan = new Scanner(System.in);

System.out.println("The program will move disks from post s to post d");

System.out.print("Please input the number of disks: ");

int n = scan.nextInt();

System.out.print("Please input the source post s (enter 0, 1, or 2): ");

int s = scan.nextInt();

System.out.print("Please input the source post d (enter 0, 1, or 2): ");

int d = scan.nextInt();

if (n <= 0 || s < 0 || s > 2 || d < 0 || d > 2 || s == d)

System.out.print("the data entered are improper; program quits ");

else

makeMoves(n,s,d,3-s-d);

}

}

Consider the problem instance makeMoves(3,2,0,1) in which we move 3

disks (named disk 1, disk 2 and disk 3; with disk 1 the smallest and disk

3 the largest) from source post 2 to destination post 0 with post 1 as the

temporary disk. The outputs for this problem instance are as follows:

move disk 1 from post 2 to post 0

move disk 2 from post 2 to post 1

move disk 1 from post 0 to post 1

move disk 3 from post 2 to post 0

move disk 1 from post 1 to post 2

move disk 2 from post 1 to post 0

move disk 1 from post 2 to post 0

We want to develop an iterative method for solving the Towers of Hanoi

puzzle. After inspecting the solutions of some small problem instances, one

can observe an iterative pattern. Take the example of makeMoves(3,2,0,1).

Every alternate move of the 7 moves involves moving disk 1.

move disk 1 from post 2 to post 0 // 1st move

move // 2nd move

move disk 1 from post 0 to post 1 // 3rd move

move // 4th move

move disk 1 from post 1 to post 2 // 5th move

move // 6th move

move disk 1 from post 2 to post 0 // 7th move

We deliberately suppress the 2nd, 4th and 6th moves so as to highlight the

moves that involve disk 1. It is observed that disk 1 moves cyclically from

post 2, to post 0, to post 1, to post 2, and finally to post 0. When n is odd,

the cyclic moves of disk 1 start from source, to destination, to temporary, to

source, to destination, to temporary,...etc, which we call a forward cyclical

sequence. On the other hand, when n is even, the cyclic moves of disk 1

start from source, to temporary, to destination, to source, to temporary, to

destination,...etc, which we call a backward cyclical sequence. When n = 2

as in makeMoves(2,1,0,2), the disk 1 moves are as follows:

move disk 1 from post 1 to post 2 // 1st move

move // 2nd move

move disk 1 from post 2 to post 0 // 3rd move

Note that it is verified that disk 1 moves from source (post 1) to temporary

(post 2), then to destination (post 0).

Once we have determined the trajectory of the moves of disk 1, we can

argue that the rest of the moves are forced. Consider again the 7 moves for

makeMoves(3,2,0,1) as in

move disk 1 from post 2 to post 0 // 1st move

move // 2nd move

move disk 1 from post 0 to post 1 // 3rd move

move // 4th move

move disk 1 from post 1 to post 2 // 5th move

move // 6th move

move disk 1 from post 2 to post 0 // 7th move

Why is the 2nd/4th/6th move forced? The 2nd/4th/6th move does not

involve the post where disk 1 is located, as disk 1 is not being moved, and

no disk can be placed on top of disk 1. From the two other posts (other the

post where disk 1 is located), we can only move in one direction as we cannot

move a larger disk on top of a smaller disk, and all disks are of different sizes.

After the 7th move, all 3 disks are in post 0. This leave both post 1 and

post 2 empty. In that case, the program stops as we cannot make any move

from post 1 to post 2, or vice versa.

B) Consider the sequence of moves returned by the recursive logic.

Use mathematical induction to show that the sequence always starts with a move of disk 1.