Cracking Coding Interview - 8.6 Towers of Hanoi

Towers of Hanoi: In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one).You have the following constraints:

1. Only one disk can be moved at a time.
2. A disk is slide off the top of one tower onto another tower.
3. A disk cannot be placed on top of a smaller disk.

Write a program to move the disks from the first tower to the last using stacks.

Hints: #144, #224, #250, #272, #318

解法

用S1、S2、S3代表3个Stack，S1初始有disks，S2和S3为空。现在我们要把S1的disk移到S3中：

1. 当S1=（1）的时候，直接把1移动到S3
2. 当S2=（1，2）的时候，把1移动到S2，把2移动到S3，把S1移动到S3
3. 当S3=（1，2，3）的时候，把（1，2）移动到S2，把3移动到S3，把（1，2）移动到S3

所以可以看到，把S1移动到S3的步骤是：

1. 把除了最后一个的disk都移动到S2。在这一步里，S1是src、S2是dest、S3是tmp
2. 把最后一个disk移动到S3。在这一步里，S1是src、S3是dest。
3. 把S2的移动到S3。在这一步里，S2是src、S3是dest、S1是tmp。

在第1步里递归执行1-3，在第2步里也是递归执行1-3。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public void hanoi(Stack src, Stack dest, Stack tmp) {
  // 把除最后一个移动到tmp中
  hanoi(src.size() - 1, src, tmp, dest);
  // 把最后一个移动到dest中
  dest.push(src.pop());
  // 把除最后一个移动到dest中
  hanoi(src.size() - 1, tmp, dest, src);
}

// amount: 要移动的disk的数量
public void hanoi(int amount, Stack src, Stack dest, Stack tmp) {
  if (amount <= 0) {
    return;
  }
  // 把除最后一个移动到tmp中
  hanoi(amount - 1, src, tmp, dest);
  // 把最后一个移动到dest中
  dest.push(src.pop());
  // 把除最后一个移动到dest中
  hanoi(amount - 1, tmp, dest, src);
}