Towers of Hanoi P85288


Statement
 

pdf   zip

html

[r]

The Towers of Hanoi is a game that consists of three rods and n disks of different sizes that can slide onto any rod. The game starts with the disks stacked in order of size on the left rod, the biggest disk at the bottom. The aim of the game is to move all the disks from the left rod (A) to the right rod (C), using the middle rod (B) as auxiliary. All the moves have to follow these rules:

  • In each step, only one disk can be moved.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, over the other disks that may already be present on that rod.
  • No disk can be placed over a smaller disk.

Write a program that solves the game of the Towers of Hanoi, using the minimal number of movements.

Input

Input consists of a single natural number n between 1 and 18.

Output

Print the shortest sequence of movements for the given n. Follow the format of the examples.

Public test cases

  • Input

    1

    Output

    A => C

  • Input

    2

    Output

    A => B
A => C
B => C

  • Input

    3

    Output

    A => C
A => B
C => B
A => C
B => A
B => C
A => C
    • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Java Python
    User solutions
    C C++ Haskell Java Python Rust