This book explores the underlying mathematical reasons for why games and puzzles are
challenging and so much fun. It shows how games and puzzles can serve as powerful …

Combinatorial games lead to several interesting, clean problems in algorithms and
complexity theory, many of which remain open. The purpose of this paper is to provide an …

We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a
theoretical abstraction of many video games (introduced in 1999). The proof also extends to …

We investigate algorithmic control of a large swarm of mobile particles (such as robots,
sensors, or building material) that move in a 2D workspace using a global input signal such …

We present algorithmic results for the parallel assembly of many micro-scale objects in two
and three dimensions from tiny particles, which has been proposed in the context of …

We investigate algorithmic control of a large swarm of mobile particles (such as robots,
sensors, or building material) that move in a 2D workspace using a global input signal (such …

Micro-and nanorobots are often controlled by global input signals, such as an
electromagnetic or gravitational field. These fields move each robot maximally until it hits a …

We prove NP-hardness of a wide class of pushing-block puzzles similar to the classic
Sokoban, generalizing several previous results [ED Demaine et al., in: Proc. 12th Canad …

It is shown that assembling molecules in the ATOMIX game can be used to simulate finite
automata. In particular, an instance of ATOMIX is constructed that has a solution if and only if …

We prove PSPACE-completeness of a class of pushingblock puzzles similar to the classic
Sokoban, extending several previous results [1, 5, 12]. The puzzles consist of unit square …