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 leftmost peg. The goal is to move all n disks to the rightmost 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 leftmost peg to the rightmost peg consists of 2^n1 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^n1. 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 
Encodings 1  5 of 5 
