The goal of the game is to move all the disks from the first rod to the last rod following these rules:

Only one disk may be moved at a time.

Each move consists of taking the top disk from one of the stacks and placing it on top of another stack or an empty rod.

No disk may be placed on top of a disk that is smaller.

Write a program that uses a recursive method to solve the Tower of Hanoi puzzle. The program prompts the user for the number of disks to be used in the game, and then passes the number of disks and the positions of the starting rod $(1),$ the ending rod $(3),$ and the spare rod $(2)$ to the method. When the number of disks is $1,$ display a statement that describes the move from rod to rod$$for example, Move the disk from $1$ to $3.$ When the number of disks is not $1,$ the method calls itself three times using these parameters:

The number of disks minus $1,$ the start position, the spare position, and the end position

$1,$ the start position, the end position, and the spare position

The number of disks minus $1,$ the spare position, the end position, and the start position