Tower 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:

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. The instance family of this problem 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 k-th move in the segment is the final goal state. The length of the plan to be looked at is thus k.

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

Predicates

• Input: steps/1, time/1, disk/1, on0/2, ongoal/2

• Output: put/3

Input format

Input data are stored in a plain text file, The format of the file is as follows:

1. The file starts by specifying the number of steps in which the goal state is to be reached from the initial state using the unary predicate "steps". For example: steps(40).

   b. The file then contains k+1 occurences of the unary predicate "time" that define the steps of the problem. Time starts at 0 and ends at k: time(0). time(1). ... time(40). where moves happen from time 0 to time 39. Time 40 gives the goal state configuration if the goal state configuration can be reachedin 40 steps.

   c. The file then contains n+4 occurrences of the predicate "disk"; this defines the four pegs and n disks. That is, the first four disk(1), disk(2), disk(3), disk(4) are the four pegs. Disks 5, 6, ..., n+4 are the n disks so that disk i is larger than disk j if i < j. For example input might be: disk(1). disk(2). disk(3). disk(4). ... disk(9). Hence, there are 5 disks.

   d. The file then specifies the initial placement of disks on the pegs using the binary predicate on0. on0(x,y) specifies that disk x is placed on top of disk y in the initial configuration. E.g. on0(5,1). ...

   e. The file then specifies the final placement of disks on the pegs using the binary predicate ongoal. ongoal(x,y) specifies that disk x is placed on top of disk y in the goal configuration. E.g. ongoal(5,4). ...

Output format

The solution must be encoded by a ternary predicate put, where put(T,I,J) stands for "at step T, put disk J on top of disk I".

Example(s)

Input:

steps(3). time(0). time(1). time(2). time(3). disk(1). disk(2). disk(3). disk(4). disk(5). disk(6). disk(7). disk(8). disk(9). on0(5,1). on0(6,5). on0(7,6). on0(8,7). on0(9,8). ongoal(5,1). ongoal(6,5). ongoal(7,6). ongoal(8,2). ongoal(9,8).

For the example input given above, the following is a valid solution: put(0,4,9). put(1,2,8). put(2,8,9).

Notes and updates

• In this year's edition, the problem is defined over 4 pegs.

• Training Instances: updated on date 02/02/2011;
• Feb 8th, 2011. Refined problem description.

Author(s)

• Author: Miroslaw Truszczynski
  • Affiliation: University of Kentucky, USA
• Author: Shaden Smith
  • Affiliation: University of Kentucky, USA
• Author: Alex Westlund
  • Affiliation: University of Kentucky, USA