Quell

We study the computational complexity of the puzzle Quell. The goal is to collect pearls by sliding a droplet of water over them in a map that is a two-dimensional grid. Each cell of the grid is either a free space (possibly with a pearl in it) or an obstacle. In each move, the droplet slides in one of the four directions to the maximal extent, through the free spaces of the map and collecting all pearls along the way, until it is stopped by an obstacle. We show that any-Moves-all-Pearls (deciding whether it is possible to collect all the pearls using any number of moves) can be solved in polynomial time. In contrast, both any-Moves-max-Pearls (finding the maximum number of pearls that can be collected using any number of moves) and min-Moves-all-Pearls (finding the minimum number of moves required to collect all the pearls) are APX-hard, although the corresponding decision problems are in FPT. We also present a simple 2-approximation for any-Moves-max-Pearls, and leave open the question whether min-Moves-all-Pearls admits a polynomial-time constant approximation.