Towers of Hanoi
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:
- move one disk at a time.
- only the top disk on a peg can be moved.
- 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
- Miroslaw Truszczynski
- University of Kentucky, USA
- Shaden Smith
- University of Kentucky, USA
- Alex Westlund
- University of Kentucky, USA