Background The following puzzle was invented by Edouard Lucas in 1883. We are gi

Question

Background

The following puzzle was invented by Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller one.

Exercise

Create a Java method (recursive) that solves the tower puzzle with any number of disks in a step-by-step fashion. This is, your method should print a sequence of moves that lead to a solution.

Example

Suppose that initially we have the three pegs P1, P2, and P3 where there are three disks A < B < C disks in P1, leading to a conguration

[A,B,C]P1 []P2 []P3

Note that following sequence of moves solves the problem:

1. Move top of P1 to P2: [B,C]P1 [A]P2 []P3

2. Move top of P1 to P3: [C]P1 [A]P2 [B]P3

3. Move top of P2 to P3: [C]P1 []P2 [A,B]P3

4. Move top of P1 to P2: []P1 [C]P2 [A,B]P3

5. Move top of P3 to P1: [A]P1 [C]P2 [B]P3

6. Move top of P3 to P2: [A]P1 [B,C]P2 []P3

7. Move top of P1 to P2: []P1 [A,B,C]P2 []P3

Print the status of the problem at the beginning and show how each step aects the state of the towers.

Note: Can somebody help me with this Java program. It is for Intro to Computer Science. Your help is greatly appreciated. Thank you.

Explanation / Answer

Assumption disk number is considered as disk weight

Stacks are used to print the status of pegs at any time

CODE

import java.util.Scanner;

import java.util.Stack;

public class TowersOfHanoi {

static Stack<Integer> A = new Stack<Integer>();

static Stack<Integer> B = new Stack<Integer>();

static Stack<Integer> C = new Stack<Integer>();

public void solve(int n, Stack<Integer> start, String s, Stack<Integer> auxiliary, String a, Stack<Integer> end,

String e) {

if (n == 1) {

// System.out.println(start + " -> " + end);

{

System.out.println("disk " + start.peek() + " is moved from " + s + " to " + e);

end.add(start.pop());

System.out.println("status of pegs ---->A " + A + " B " + B + " C " + C);

}

} else {

solve(n - 1, start, s, end, e, auxiliary, a);

// System.out.println(start + " -> " + end);

System.out.println("disk " + start.peek() + " is moved from " + s + " to " + e);

end.add(start.pop());

System.out.println("status of pegs ---->A " + A + " B " + B + " C " + C);

solve(n - 1, auxiliary, a, start, s, end, e);

}

}

public static void main(String[] args) {

TowersOfHanoi towersOfHanoi = new TowersOfHanoi();

System.out.print("Enter number of discs: ");

Scanner scanner = new Scanner(System.in);

int discs = scanner.nextInt();

//inserting disks into peg A in the order of decresing size

for (int i = discs; i >= 1; i--)

A.add(i);

System.out.println("status of pegs ---->A " + A + " B " + B + " C " + C);

towersOfHanoi.solve(discs, A, "A", B, "B", C, "C");

}

}

Sample output

Enter number of discs: 3
status of pegs ---->A [3, 2, 1] B [] C []
disc 1 is moved from A to C
status of pegs ---->A [3, 2] B [] C [1]
disc 2 is moved from A to B
status of pegs ---->A [3] B [2] C [1]
disc 1 is moved from C to B
status of pegs ---->A [3] B [2, 1] C []
disc 3 is moved from A to C
status of pegs ---->A [] B [2, 1] C [3]
disc 1 is moved from B to A
status of pegs ---->A [1] B [2] C [3]
disc 2 is moved from B to C
status of pegs ---->A [1] B [] C [3, 2]
disc 1 is moved from A to C
status of pegs ---->A [] B [] C [3, 2, 1]

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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