Tower of Hanoi

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 by specifying 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 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 and no further move.

c. The file then contains n+3 occurences of the predicate "disk"; this defines the three pegs and n disks. 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 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". For the example input given above, the following is a valid solution:

put(0,3,4). put(1,1,6). put(2,4,5).

Author: Gayathri Namasivayam, Miroslaw Truszczynski and Giorgio Terracina