1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
Towers of Hanoi
The towers of hanoi is a mathematical puzzle invented by Edouard Lucas in 1883. The puzzle consists of three posts and a number of concentric disks of different sizes which can slide onto the posts. In the initial position, all of the disks are stacked in ascending order of size on one post with the smallest disk at the top as seen in the following picture.
The object of the puzzle is to move the entire stack to another post subject to the following simple rules.
1. A move consists of taking the topmost disk from one post and moving it to the top of another post.
2. No disk may be placed on top of a smaller disk.
For example, label the posts from left to right as A, B, and C. Consider the three disk puzzle where all the disks are initially on post A and we want to move them to post C as illustrated in the following picture.
We can solve this puzzle by making the following sequence of moves.
1. Move the red disk from A to C
2. Move the green disk from A to B
3. Move the red disk from C to B
4. Move the blue disk from A to C
5. Move the red disk from B to A
6. Move the green disk from B to C
7. Move the red disk from A to C.
It's not obvious how to come up with an iterative algorithm that solves this problem but there is a very natural and simple recursive solution. Suppose we want to move N disks from post A to post C. First, we can (recursively) move the top N-1 disks from A to B. Then move the largest/bottom disk from A to C. Then we recursively move the N-1 disks from B to C. Thus, we have the following simple recursive algorithm
// move n disks from "from" to "to" using "intermed"
// as the intermediate tower.
void hanoi( int n, Tower &from, Tower &to, Tower &intermed )
{
if (n == 0) return; // base case
hanoi( n-1, from, intermed, to );
move disk from "from" to "to"
hanoi( n-1, intermed, to, from );
The Programming Task
The assignment is to write a C++ program that solves the N disk towers of hanoi problem using the above recursive algorithm. The value of N comes from user input. Your program should print out the current state of the puzzle after each move. For example, the state of your puzzle might look like the following (where the larger the number, the larger the disk)
4 1
5 2 3
= = =
A B C
Extra credit for prettier output that prints out an ascii "picture" of the disks using dashes, equal signs, or whatever you think looks best (this is more involved than it sounds). Printing out the towers nicely will be the most involved part of the project.
A post/tower will be represented by an array stack. For printing, you will need an additional stack function that takes an index and returns the stack item at that index. A post/tower will also need a character or string to identify which post it is. The reason you need this is that the recursive calls keeps switching the order of the posts.
When testing your program, don't use too large of a value of N. The 5 disk puzzle takes 31 moves to solve which is as large as you could possibly need for testing purposes. The 10 disk puzzles takes over 1000 moves to solve!
|
