How can you implement the tower of Hanoi game.

First look at the optimized solution of tower of hanoi.

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case: (from wikipedia)

For an even number of disks:

make the legal move between pegs A and B

make the legal move between pegs A and C

make the legal move between pegs B and C

repeat until complete

For an odd number of disks:

make the legal move between pegs A and C

make the legal move between pegs A and B

make the legal move between pegs C and B

repeat until complete

In each case, a total of 2n-1 moves are made.

Implemented with stack

public class TowerOfHanoi { Stack<Integer> A = new Stack<Integer>(); Stack<Integer> B = new Stack<Integer>(); Stack<Integer> C = new Stack<Integer>(); int diskNum; public TowerOfHanoi(int n) { for (int i = n; i >= 1; i--) { A.push(i); } diskNum = n; } public int solve() { int moves = 0; if (diskNum%2 == 1) {// odd number while(C.size() != diskNum) { if (C.isEmpty() || (!A.isEmpty() && A.peek() < C.peek())) { C.push(A.pop()); } else { A.push(C.pop()); } moves++; if (C.size() == diskNum) break; if (B.isEmpty() || (!A.isEmpty() && A.peek() < B.peek())) { B.push(A.pop()); } else { A.push(B.pop()); } moves++; if (B.isEmpty() || (!C.isEmpty() && C.peek() < B.peek())) { B.push(C.pop()); } else { C.push(B.pop()); } moves++; } } else { // even number while(C.size() != diskNum) { if (B.isEmpty() || (!A.isEmpty() && A.peek() < B.peek())) { B.push(A.pop()); } else { A.push(B.pop()); } moves++; if (C.isEmpty() || (!A.isEmpty() && A.peek() < C.peek())) { C.push(A.pop()); } else { A.push(C.pop()); } moves++; if (C.size() == diskNum) break; if (B.isEmpty() || (!C.isEmpty() && C.peek() < B.peek())) { B.push(C.pop()); } else { C.push(B.pop()); } moves++; } } return moves; } }

Advertisements