15-Puzzle Optimization Version

Problem description

This problem modifies its corresponding decision problem by minimizing the number of instances of "move" in a solution. For a maximum time stamp m, the objective function to minimize is as follows:

sum { move(s,x,y) : 1 ≤ x,y ≤ 4, 0 ≤ s < m }

Except for the objective function to minimize, the problem description is the same as the one of the corresponding decision problem.

Input format

See corresponding decision problem.

Output format

See corresponding decision problem.

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam