The 15 Puzzle consists of 15 squares numbered from 1 to 15 that are placed in a 4 by 4 box with one empty position. The objective of the puzzle is to reposition the squares by sliding them one at a time into a configuration with the numbers in order.
Problem Statement
The 15 Puzzle is a sliding puzzle that consists of a 4 by 4 frame of numbered square tiles in an arbitrary ordering with one space. The objective of the puzzle is to place the tiles in order, as shown in the figure below, by making sliding moves that use the empty space.
Mathematical Formulation
Here we investigate an optimization approach to solving the 15 Puzzle. In particular, we formulate an integer programming model in which the objective is to minimize the number of moves that the empty space makes in the process of positioning the numbered tiles in their respective positions. The constraints in the model define the allowable moves and track the positions of the empty space and the numbered tiles. The empty space (or blank tile) is allowed to move in four directions — up, down, left, and right unless it is along an edge. When the blank tile is along an edge, one or two of the directions will be prohibited.
Sets
\(I = \{i0, i1, i2, \cdots, i15\}\) is the set of tiles in which the blank tile is \(i0\)
\(T\) is the time horizon (set of moves)
Parameters
initial(i) = the starting position of tile \(i\), for all tiles \(i \in I\)
final(i) = the final (target) position of tile \(i\), for all tiles \(i \in I\)
Variables
\(p(i,t)\) = position of tile \(i\) at time \(t\), integer
\(x(t)\) = \(x\)-coordinate of the blank tile at time \(t\), integer
\(y(t)\) = \(y\)-coordinate of the blank tile at time \(t\), integer
\(z(i,t) = \left\{ \begin{array}{ll}
1 & \mbox{if tile \(i\) moves at time \(t\), \(\forall i \in I\), \(\forall t \in T\)} \\
0 & \mbox{otherwise}
\end{array} \right. \)
\(u(t) = \left\{ \begin{array}{ll}
1 & \mbox{if the blank tile moves up at time \(t\), \(\forall t \in T\)} \\
0 & \mbox{otherwise}
\end{array} \right. \)
\(d(t) = \left\{ \begin{array}{ll}
1 & \mbox{if the blank tile moves down at time \(t\), \(\forall t \in T\)} \\
0 & \mbox{otherwise}
\end{array} \right. \)
\(l(t) = \left\{ \begin{array}{ll}
1 & \mbox{if the blank tile moves left at time \(t\), \(\forall t \in T\)} \\
0 & \mbox{otherwise}
\end{array} \right. \)
\(r(t) = \left\{ \begin{array}{ll}
1 & \mbox{if the blank tile moves right at time \(t\), \(\forall t \in T\)} \\
0 & \mbox{otherwise}
\end{array} \right. \)
15 Puzzle Integer Programming Formulation
Minimize \( \sum_{t \in T} z(i0,t) \)
subject to: blank tile can make only one move at a time
\( u(t) + d(t) + l(t) + r(t) = z(i0,t) \quad \forall t \in T\)
subject to: update the position of the blank tile after each move
\( p(i0,t+1) = p(i0,t) – 4u(t) + 4d(t) – l(t) + r(t) \quad \forall t \in T\)
subject to: update the position of the numbered tile if it moved
\( p(i,t+1) – p(i0,t) + 16 z(i,t) \leq 16, \quad \forall i \in I, \forall t \in T\)
\( p(i,t+1) – p(i0,t) – 16 z(i,t) \geq -16, \quad \forall i \in I, \forall t \in T\)
subject to: define the x and y coordinates of the blank tile
\( p(i0,t) = x(t) + 4y(t), \quad \forall t \in T\)
subject to: restrict the movement of the blank tile at the top edge
\( 5u(t) \le p(i0,t), \quad \forall t \in T\)
subject to: restrict the movement of the blank tile at the bottom edge
\( 4d(t) \le 16 – p(i0,t), \quad \forall t \in T\)
subject to: restrict the movement of the blank tile at the left edge
\( l(t) \le x(t) – 1, \quad \forall t \in T \)
subject to: restrict the movement of the blank tile at the right edge
\( r(t) \le 4 – x(t), \quad \forall t \)
subject to: ensure that every tile is assigned a position at every time
\( \sum_{i \in I} p(i,t) = 1 + 2 + … + 16, \quad \forall t \in T \)
subject to: ensure that one of the numbered tiles moves if the blank tile moves
\( z(i0,t) = \sum_{i \ne i0 } z(i,t), \quad \forall t \in T\)
subject to: maintain the position of the numbered tiles if the blank tile does not move
\( p(i,t) – p(i,t+1) + 4 z(i,t) \geq 0, \quad \forall i \in I, t \in T\)
\( p(i,t) – p(i,t+1) – 4 z(i,t) \leq 0, \quad \forall i \in I, t \in T\)
subject to: bound restrictions on the variables
\( 1 \le p(i,t) \le 16, \quad \forall i \in I, \forall t \in T\)
\( 1 \le x(t) \le 4, \quad \forall t \in T\)
\( 0 \le y(t) \le 3, \quad \forall t \in T\)
subject to: initial positions
\( p(i,1) = initial(i), \quad \forall i \in I\)
subject to: final positions
\( p(i,|T|) = final(i), \quad \forall i \in I\)
Different instances of the model can be created by specifying different values in the vector initial(i). To solve an instance, we can use one of the NEOS Solvers in the Mixed Integer Linear Programming category.
In order to solve an instance of the model, we need to specify an upper bound on \(T\), the number of steps required to solve the puzzle. Clearly, we want the upper bound to be as small as possible. Brüngger et al. (1999) proved computationally that the hardest initial configurations required 80 steps to solve. Therefore, in the general case, we can define \(T = \{1, \cdots, 80\}\), but the computation time required to solve those hardest initial configurations is extensive. For the Java applet here, we make two simplifications in order to provide a user-friendly experience . First, we limit the set of available starting positions to those that can be solved within 60 seconds. Second, we have the solver return the first integer solution that it finds. This solution may not be optimal in the sense that there may be a shorter sequence of steps, however, this approach eliminates the (potentially lengthy) time spent by the solver proving the optimality of the solution.
GAMS Model
Here is a GAMS model for an instance in which the initial configuration is the following:
(i5, i1, i2, i3, i9, i6, i7, i4, i13, i10, i11, i8, i14, i15, i0, i12).
sets
i tile number /i0*i15/
t move number /0*80/
parameter
*Optimal solution is 11 moves
initial(i) /i1 2, i2 3, i3 4, i4 8, i5 1, i6 6, i7 7, i8 12, i9 5, i10 10, i11 11, i12 16, i13 9, i14 13, i15 14, i0 15/
final(i) /i1 1, i2 2, i3 3, i4 4, i5 5, i6 6, i7 7, i8 8, i9 9, i10 10, i11 11, i12 12, i13 13, i14 14, i15 15, i0 16/;
integer variables
p(i,t), x(t), y(t);
binary variables
z(i,t), u(t), d(t), l(t), r(t);
variable
obj;
equations
c_blank(t)
c_move(t)
c_move2_1(i,t)
c_move2_2(i,t)
c_pos(t)
c_up(t)
c_down(t)
c_left(t)
c_right(t)
c_no_repeat(t)
c1(t)
c2_1(i,t)
c2_2(i,t)
calc_obj
;
c_blank(t).. u(t) + d(t) + l(t) + r(t) =E= z(‘i0′,t);
c_move(t)\$(not sameas(t,’80’)).. p(‘i0’,t+1) =E= p(‘i0′,t) – 4*u(t) + 4*d(t) – l(t) + r(t);
c_move2_1(i,t)\$(not sameas(i,’i0’)).. p(i,t+1) – p(‘i0′,t) + 16*z(i,t) =L= 16 + 0;
c_move2_2(i,t)\$(not sameas(i,’i0’)).. p(i,t+1) – p(‘i0’,t) – 16*z(i,t) =G= -16 + 0;
c_up(t).. 5*u(t) =L= p(‘i0’,t);
c_down(t).. 4*d(t) =L= 16 – p(‘i0’,t);
c_left(t).. l(t) =L= x(t) – 1;
c_right(t).. r(t) =L= 4 – x(t);
c_pos(t).. p(‘i0’,t) =E= 4*y(t) + x(t);
c_no_repeat(t).. sum(i, p(i,t)) =E= sum(i, ord(i));
c1(t).. z(‘i0′,t) =E= sum(i\$(not sameas(i,’i0′)), z(i,t));
c2_1(i,t)\$(not sameas(t,’80’)).. -4*z(i,t) =L= p(i,t) – p(i,t+1);
c2_2(i,t)\$(not sameas(t,’80’)).. p(i,t) – p(i,t+1) =L= 4*z(i,t);
calc_obj.. obj =E= sum(t, z(‘i0′,t));
p.lo(i,t) = 1; p.up(i,t) = 16;
x.lo(t) = 1; x.up(t) = 4;
y.lo(t) = 0; y.up(t) = 3;
p.fx(i,’1′) = initial(i);
p.fx(i,’80’) = final(i);
model puzzle4 /all/;
solve puzzle4 using mip minimizing obj
Acknowledgments and References
Wai Kit Ong and Yachao Dong contributed the original version of this case study, which was completed as part of the CS/ISyE 635 taught course by Professor Jeff Linderoth at UW-Madison in Spring 2012.
- Brüngger, A., Marzetta, A., Fukuda, K., and Nievergelt, J. 1999. The Parallel Search Bench ZRAM and Its Applications. Annals of Operations Research 90, 45-63, 1999.
- Johnson, W., and Story, W. 1879. Notes on the “15” Puzzle. American Journal of Mathematics, 397-404.
- Korf, R., and Schultze, P. 2005. Large-scale parallel breadth-first search. In Proceedings of the 20th National Conference of Artificial Intelligence (AAAI-05), 1380-1385.