Today I read a paper titled “Coin-Moving Puzzles”
The abstract is:
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..