welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: ProblemsDescription / HanoiTower

Towers of Hanoi

Contents

  1. Towers of Hanoi
    1. Problem Description
    2. Input format
    3. Output format
    4. Example
    5. Authors

Problem Description

The classic Towers of Hanoi (ToH) problem has three pegs and n disks. In this problem we consider the problem of 4 pegs and n disks. Initially, all n disks are on the left-most peg. The goal is to move all n disks to the right-most peg with the help of the two middle pegs. The rules are:

  1. move one disk at a time.
  2. only the top disk on a peg can be moved.
  3. larger disk cannot be placed on top of a smaller one.

It is known that, for a classic ToH problem with n disks, the plan of moving all n disks from the left-most peg to the right-most peg consists of 2^n-1 moves. However, when 4 pegs are present there is not a known formula for solution length. There is no proven algorithm for optimally solving a Hanoi puzzle with 4 or more pegs. This suite is based on the Frame-Stewart algorithm that solves ToH problem with 4 pegs in what is conjectured (no proof has been found) to be an optimal number of steps.

We generate instances of ToH as follows. We fix the number of disks. We pick a continuous segment of moves of length k in the sequence of moves produced by the Frame-Stewart algorithm. Then the configuration of the disks before the first move in the segment is the initial state of an instance and the configuration of the disks after the kth move in the segment is the final goal state. The length of the plan is thus k.

We note that the action of moving a disk to its original place has no effect. However, such dummy actions are never needed to solve the competition instances.

Input format

Output format

Example

Authors