« Tower of Hanoi

Problem

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move all disks from source rod to destination rod using third rod (say auxiliary). The rules are :

1. Only one disk can be moved at a time.
2. A disk can be moved only if it is on the top of a rod.
3. No disk can be placed on the top of a smaller disk.

Print the steps required to move n disks from source rod to destination rod.Source Rod is named as 'a', auxiliary rod as 'b' and destination rod as 'c'.

Input Format :

Integer n

Output Format :

Steps in different lines (in one line print source and destination rod name separated by space)

Constraints :

0 <= n <= 20

Sample Input 1 :

2

Sample Output 1 :

a b

a c

b c

Sample Input 2 :

3

Sample Output 2 :

a c

a b

c b

a c

b a

b c

a c

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13void towerOfHanoi(int n, char from_rod, char aux_rod, char to_rod)
14{
15    if (n == 0)
16    {
17        return;
18    }
19    if (n == 1)
20    {
21        cout << from_rod << " " << to_rod << endl;
22        return;
23    }
24    towerOfHanoi(n - 1, from_rod, to_rod, aux_rod);
25    cout << from_rod << " " << to_rod << endl;
26    towerOfHanoi(n - 1, aux_rod, from_rod, to_rod);
27}
28
29int main()
30{
31    int n;
32    cin >> n;
33    towerOfHanoi(n, 'a', 'b', 'c');
34    return 0;
35}