Encoding Class 15-PuzzleCompetition

Class Tree
Description Problem Description
In 15-puzzle, 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(x-i)+abs(y-j) == 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 n-1

b. The next line gives the maximal timestamp using a unary predicate
"maxtime". For example:

c. The next 16 lines define the numbers on the grid using a unary predicate
"entry". Note that number 0 denotes the blank

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"

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

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

1 - 5 of 5