Instance Class TowersOfHanoiCompetition

Class Tree
Description Problem Description
===================
The classic Tower of Hanoi (ToH) problem has three 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 middle peg. 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.

In this suite, we generate instances of ToH as follows. We fix the number
of disks. Then we look at the complete plan of length 2^n-1. We pick a
continuous segment of moves of length k. 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.

Input Format
============
Input data are stored in a plain text file, The format of the file is
as follows:
a. The file starts with a single line that specifies the number of steps
required to reach the goal state from the initial state using the
unary predicate "steps". For example:
steps(40).

b. The file then contains k+1 lines that define the steps of the problem
using the unary predicate "time". 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 and no further move.

c. The file then contains n+3 lines that define the three pegs and n disks
using predicate "disk". That is, the first three disks (1, 2, 3) are
the three pegs. 4, 5, ..., n+3 are the n disks so that disk i is larger
than disk j if i < j. For example:
disk(1).
disk(2).
disk(3).
disk(4).
...
disk(9).

Hence, there are 6 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 y is placed on
top of disk x in the initial configuration.
on0(1,4).
...

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

Example input:
steps(3).
time(0).
time(1).
time(2).
time(3).
disk(1).
disk(2).
disk(3).
disk(4).
disk(5).
disk(6).
on0(1,4).
on0(2,5).
on0(5,6).
ongoal(3,4).
ongoal(4,5).
ongoal(1,6).

Output Requirement
==================
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".

For the example input given above, the following is a valid solution:
put(0,3,4) put(1,1,6) put(2,4,5)

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky
Email: {gayathri, mirek}@cs.uky.edu
Submitter Martin Gebser
Compatible Encodings
Output Predicates
  • disk/1
  • on0/2
  • ongoal/2
  • steps/1
  • time/1
Instances
1 - 20 of 33