Erik D. Demaine, Martin L. Demaine, and Helena A. Verrill, “Coin-Moving Puzzles”, in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405–431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.
Abstract:
We introduce a new family of one-player games, involving the movement of coins
from one configuration to another. Moves are restricted so that a coin can be
placed only in a position that is adjacent to at least two other coins. The
goal of this paper is to specify exactly which of these games are solvable.
By introducing the notion of a constant number of extra coins, we give tight
theorems characterizing solvable puzzles on the square grid and
equilateral-triangle grid. These existence results are supplemented by
polynomial-time algorithms for finding a solution.