Class Tree  

Description 
Problem Description =================== In 15puzzle, we have a 4x4 grid where there are 15 numbers (1 to 15) and one blank. The goal is to arrange the numbers from their initial configuration to the goal configuration by sliding one number at a time to its adjacent blank position. Let (x,y) be the coordinates of a number on the grid and (i,j) be those of the blank. Then (x,y) and (i,j) are adjacent if abs(xi)+abs(yj) == 1 Input Format ============ Each input is stored in a plain text file. The format of the file is as follows: a. The first n lines define the time sequence using a unary predicate "time". The time starts from 0 and ends at n1 time(0). time(1). ... time(35). b. The next line gives the maximal timestamp using a unary predicate "maxtime". For example: maxtime(35). c. The next 16 lines define the numbers on the grid using a unary predicate "entry". Note that number 0 denotes the blank entry(0). entry(1). ... entry(15). d. The next 4 lines define the range of the x(or y)coordinate of each entry on the grid: from 1 to 4, using a unary predicate "pos" pos(1). pos(2). pos(3). pos(4). e. The next 16 lines define the initial configuration of the grid using a ternary predicate "in0". in0(x,y,v) denotes value v is at position (x,y): in0(1,1,4). in0(1,2,0). ... We note that the goal state is fixed to the following configuration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Output Requirement ================== The solution must be represented by means of a ternary predicate "move" that records the movement of the blank at each timestamp. That is atoms of the form "move(t,x,y)" describe that blank is moved to position (x,y) at time t. Authors: Lengning Liu and Miroslaw Truszczynski Affiliation: University of Kentucky Email: {lliu1, mirek}@cs.uky.edu 
Encodings 1  5 of 5 
