15-Puzzle
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 swapping one number at a time with 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 |x-i|+|y-j| = 1.
Input format
An input consists of the following parts:
a. Exactly one instance of predicate "maxtime"
gives the maximum time stamp m. For example:
maxtime(35).
b. Unary predicate "time", whose instances start at 0 and end at m,
provides all time stamps:
time(0).
time(1).
...
time(35).
c. The instances of predicate "entry" give the numbers on the grid.
Note that number 0 denotes the blank:
entry(0).
entry(1).
...
entry(15).
d. Predicate "pos" gives the range of the x-(or y-)coordinate of each
entry on the grid, viz., 1 to 4:
pos(1).
pos(2).
pos(3).
pos(4).
e. Finally, instances in0(x,y,n) of predicate "in0"
specify that entry n is at position (x,y) in the initial grid configuration:
in0(1,1,4).
in0(1,2,0).
...
For further illustration, compare the instances available at asparagus.
Output format
A solution is represented by means of a ternary predicate "move"
that records the movement of the blank at each time stamp smaller than the maximum time stamp.
That is, instances of the form move(t,x,y) describe that
blank is swapped with the number located at position (x,y) in the
grid configuration at time stamp t, where
the blank cannot be swapped with itself.
The sequence of swaps is consecutive, that is,
there are s+1 instances of "move" for time stamps 0,...,s, where s < m
for maximum time stamp m.
Note that s < m-1 (and even s = -1) is allowed,
but the goal configuration, shown below, must be reached with the last swap:
We count
rows x vertically from the top to the bottom, and
columns y horizontally from the left to the right.
The contents n of a grid cell (x,y) gives the entry at (x,y) in the goal configuration, viz.,
entry 0 at (1,1), 1 at (1,2), ..., 14 at (4,3), and 15 at (4,4).
In particular, observe that the blank must be at position (1,1).
Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam