» ASP Competition | |
|
15-PuzzleProblem descriptionIn 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 formatAn input consists of the following parts: a. Exactly one instance of predicate "maxtime"
gives the maximum time stamp m. For example: b. Unary predicate "time", whose instances start at 0 and end at m,
provides all time stamps: c. The instances of predicate "entry" give the numbers on the grid.
Note that number 0 denotes the blank: d. Predicate "pos" gives the range of the x-(or y-)coordinate of each
entry on the grid, viz., 1 to 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: 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: Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser |