» ASP Competition | |
|
Tower of HanoiProblem 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: Input formatInput 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 formatThe 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 |