## 1 Introduction  
Since [PERSON] invented the famous 15-puzzle, sliding block puzzles have played an important role in mathematical recreations. There are many variations of sliding block puzzles (Figure 1), and they have been investigated widely (see a comprehensive handbook [1]). Recently, a new framework using games on graphs is developed, and many complexity results of these puzzles are settled [2]. In most of these puzzles, for a given initial state, we aim at finding a way to its goal state. Sometimes, the difficulty of the puzzles is changed if we change the initial state. For example, the 15-puzzle becomes much easier if we remove two or more pieces from (potentially) sixteen pieces. In the puzzles in Figure 1, if we remove more pieces, the problems (getting out a specified car or disassembling the puzzle) become easier. That is, in a sliding block puzzle, fewer pieces mean easier in general. We investigate such a monotonicity of the sliding block puzzles.  
Suppose we have a collection of \(n\) simple polygons in the plane, none of which overlap each other. We call the polygons _interlocked_ if no subset can be separated arbitrarily far from the rest. Otherwise, we say them _free_. If we remove a subset \(S\) of the polygons, the remaining polygons might or might not be interlocked.  
Define \(\delta(S)=1\) if the remaining polygons become free after removing \(S\), and \(\delta(S)=0\) if they remain interlocked. Clearly \(f\) is monotone: if \(S\subseteq S^{\prime}\), then \(\delta(S)\leq\delta(S^{\prime})\). (Removing more makes the polygons less interlocked.)  
Then, which monotone Boolean functions \(f\) can be described by \(n\) interlocked polygons? Figure 2 shows some simple examples. For a specified \(n\) and \(k\), this technique can design \(n\) interlocked polygons such that removing any \(k\) of them makes them all free.  
Since the early period of computer science, monotone functions are well investigated, especially, in the context of the lower bound of circuit complexity (see, e.g., [3, Chapter 14.4]). In general, monotone Boolean functions are formed by AND and OR operations (without NOT). Such gates seem easy enough to build, but not without extra pieces that affect the function.  
Figure 1: Typical sliding block puzzles in 2D and 3D.  
Figure 2: Interlocked polygons freed by removing any one, two, or three of the polygons (from left to right).  
Then, can any monotone Boolean functions \(f\) on \(n\) variables be described by \(m>n\) interlocked polygons, where \(f\) operates on a particular subset of the polygons? In this paper, we give an affirmative answer to this question:  
**Theorem 1**.: _For any given monotone Boolean function \(f\) on \(n\) variables \(x_{1},\ldots,x_{n}\), there is a collection \(S\) of \(m\) simple polygons with \(m=O(n)\) such that (1) \(S\) is interlocked, (2) a subset \(S^{\prime}\subset S\) of \(n\) simple polygons corresponding to the variables, and (3) \(\delta(S^{\prime\prime})=1\) for \(S^{\prime\prime}\subseteq S^{\prime}\) if and only if \(f(x_{1},\ldots,x_{n})=1\), where \(x_{i}=1\) indicates that the simple polygon corresponding to \(x_{i}\) is in \(S^{\prime\prime}\)._  
We next turn to the sliding block puzzles again. Using a new framework in [2], several sliding block puzzles are shown to be PSPACE-complete. In such a puzzle, the problem asks whether a specified piece can reach the goal or not. More basic problem is to determine if a given collection of polygons is interlocked or not. In this paper, we generalize the basic problem to a new sliding block puzzle; the _exploding sliding block puzzle_ is a puzzle that asks if all polygons of a given collection of polygons can be free. Combining the idea in Theorem 1 and the gadgets in [2], we show that the exploding sliding block puzzle is also PSPACE-complete. This result holds even if all pieces are rectangles but one nonconvex piece. This is optimal since any collection of convex polygons is explodable.