Iterative Tower of Hanoi - GeeksforGeeks
Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any poles. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say 'source pole') to another pole (say 'destination pole') with the help of third pole (say auxiliary pole).
The puzzle has the following two rules:
1. You can't place a larger disk onto smaller disk
2. Only one disk can be moved at a time
https://hellosmallworld123.wordpress.com/2014/05/10/tower-of-hanoi-using-stacks/
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.
http://simpledeveloper.com/towers-of-hanoi/
http://www.java2s.com/Tutorial/Java/0100__Class-Definition/TheTowersofHanoi.htm
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
/* Base case */
if (n <= 0) return;
/* move top n - 1 disks from origin to buffer, using destination as a buffer. */
moveDisks(n - 1, origin, buffer, destination);
/* move top from origin to destination
moveTop(origin, destination);
/* move top n - 1 disks from buffer to destination, using origin as a buffer. */
moveDisks(n - 1, buffer, destination, origin);
}
void main(String[] args) {
int n = 3;
Tower[] towers = new Tower[n];
for (int i= 0; i < 3; i++) {
towers[i] = new Tower(i);
}
for (int i= n - 1; i >= 0; i--) {
towers[0].add(i);
}
towers[0].moveDisks(n, towers[2], towers[l]);
}
class Tower {
private Stack<Integer> disks;
private int index;
public Tower(int i) {
disks = new Stack<Integer>();
index = i;
}
public int index() {
return index;
}
public void add(int d) {
if (!disks.isEmpty() && disks.peek() <= d) {
System.out.println("Error placing disk" + d);
} else {
disks.push(d);
}
}
public void moveTopTo(Tower t) {
int top= disks.pop();
t.add(top);
}
public void moveDisks(int n, Tower destination, Tower buffer) {
if (n > 0) {
moveDisks(n - 1, buffer, destination);
moveTopTo( destination);
buffer.moveDisks(n - 1, destination, this);
}
}
}
Read full article from Iterative Tower of Hanoi - GeeksforGeeks
Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any poles. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say 'source pole') to another pole (say 'destination pole') with the help of third pole (say auxiliary pole).
The puzzle has the following two rules:
1. You can't place a larger disk onto smaller disk
2. Only one disk can be moved at a time
For n disks, total 2n – 1 moves are required. T(n)=2T(n-1)+1
http://en.wikipedia.org/wiki/Continuation-passing_style
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
1. Calculate the total number of moves required i.e. "pow(2, n) - 1" here n is number of disks. 2. If number of disks (i.e. n) is even then interchange destination pole and auxiliary pole. 3. for i = 1 to total number of moves: if i%3 == 1: legal movement of top disk between source pole and destination pole if i%3 == 2: legal movement top disk between source pole and auxiliary pole if i%3 == 0: legal movement top disk between auxiliary pole and destination pole
// Function to implement legal movement between
// two poles
void
moveDisksBetweenTwoPoles(
struct
Stack *src,
struct
Stack *dest,
char
s,
char
d)
{
int
pole1TopDisk = pop(src);
int
pole2TopDisk = pop(dest);
// When pole 1 is empty
if
(pole1TopDisk == INT_MIN)
{
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When pole2 pole is empty
else
if
(pole2TopDisk == INT_MIN)
{
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
// When top disk of pole1 > top disk of pole2
else
if
(pole1TopDisk > pole2TopDisk)
{
push(src, pole1TopDisk);
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When top disk of pole1 < top disk of pole2
else
{
push(dest, pole2TopDisk);
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
//Function to show the movement of disks
void
moveDisk(
char
fromPeg,
char
toPeg,
int
disk)
{
printf
(
"Move the disk %d from \'%c\' to \'%c\'\n"
,
disk, fromPeg, toPeg);
}
//Function to implement TOH puzzle
void
tohIterative(
int
num_of_disks,
struct
Stack
*src,
struct
Stack *aux,
struct
Stack *dest)
{
int
i, total_num_of_moves;
char
s =
'S'
, d =
'D'
, a =
'A'
;
//If number of disks is even, then interchange
//destination pole and auxiliary pole
if
(num_of_disks % 2 == 0)
{
char
temp = d;
d = a;
a = temp;
}
total_num_of_moves =
pow
(2, num_of_disks) - 1;
//Larger disks will be pushed first
for
(i = num_of_disks; i >= 1; i--)
push(src, i);
for
(i = 1; i <= total_num_of_moves; i++)
{
if
(i % 3 == 1)
moveDisksBetweenTwoPoles(src, dest, s, d);
else
if
(i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, s, a);
else
if
(i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
https://hellosmallworld123.wordpress.com/2014/05/10/tower-of-hanoi-using-stacks/
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.
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;
}
}
http://simpledeveloper.com/towers-of-hanoi/
If n is 1, move disk 1 from origin to destination. Otherwise:
- Move n – 1 disks (one at a time) from origin to temporary
- Move disk n from origin to destination
- Move n – 1 disks (one at a time) from temporary to destination
http://www.java2s.com/Tutorial/Java/0100__Class-Definition/TheTowersofHanoi.htm
public static void doTowers(int topN, char from, char inter, char to) { if (topN == 1){ System.out.println("Disk 1 from " + from + " to " + to); }else { doTowers(topN - 1, from, to, inter); System.out.println("Disk " + topN + " from " + from + " to " + to); doTowers(topN - 1, inter, from, to); }http://www.ideserve.co.in/learn/tower-of-hanoi-algorithm
4 | public void solve(int n, String srcTower, String intermediateTower, String destTower) |
5 | { |
6 | if (n == 1) |
7 | { |
8 | System.out.println("Move topmost disk from " + srcTower + " to " + destTower); |
9 | |
10 | steps += 1; |
11 | |
12 | return; |
13 | } |
14 | |
15 | |
16 | solve(n-1, srcTower, destTower, intermediateTower); |
17 | |
18 | |
19 | solve(1, srcTower, intermediateTower, destTower); |
20 | |
21 | |
22 | solve(n-1, intermediateTower, srcTower, destTower); |
23 | } |
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
/* Base case */
if (n <= 0) return;
/* move top n - 1 disks from origin to buffer, using destination as a buffer. */
moveDisks(n - 1, origin, buffer, destination);
/* move top from origin to destination
moveTop(origin, destination);
/* move top n - 1 disks from buffer to destination, using origin as a buffer. */
moveDisks(n - 1, buffer, destination, origin);
}
void main(String[] args) {
int n = 3;
Tower[] towers = new Tower[n];
for (int i= 0; i < 3; i++) {
towers[i] = new Tower(i);
}
for (int i= n - 1; i >= 0; i--) {
towers[0].add(i);
}
towers[0].moveDisks(n, towers[2], towers[l]);
}
class Tower {
private Stack<Integer> disks;
private int index;
public Tower(int i) {
disks = new Stack<Integer>();
index = i;
}
public int index() {
return index;
}
public void add(int d) {
if (!disks.isEmpty() && disks.peek() <= d) {
System.out.println("Error placing disk" + d);
} else {
disks.push(d);
}
}
public void moveTopTo(Tower t) {
int top= disks.pop();
t.add(top);
}
public void moveDisks(int n, Tower destination, Tower buffer) {
if (n > 0) {
moveDisks(n - 1, buffer, destination);
moveTopTo( destination);
buffer.moveDisks(n - 1, destination, this);
}
}
}
Read full article from Iterative Tower of Hanoi - GeeksforGeeks