Towers of Hanoi
Given 3 rods (left - 1, middle - 2, and right - 3), there are
n round disks on the first rod or different sizes. The disks are placed in increasing order of size from top to bottom. You are allowed to move the top disk from one rod to another and place it on top of another larger disk. So, you’re not allowed to place a larger disk on top of a smaller one. You are asked to print all the operations that would lead to moving all the disks from the first rod to the third one. The number of moves needs to be minimal.
Input
The input contains a single integer
n (1 ≤ n ≤ 16) the number of disks on the first rod.Output
The program should print all the operations required to move the disks from the first rod to the third one while making sure that all the disks on a rod are smaller than the ones below. The output should not contain more than operations.
Examples
Input | Output |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB