Coin-Moving Puzzles
<|reference_start|>Coin-Moving Puzzles: 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.<|reference_end|>
@article{demaine2002coin-moving,
    title={Coin-Moving Puzzles},
    author={Erik D. Demaine, Martin L. Demaine, Helena A. Verrill},
    journal={arXiv preprint arXiv:cs/0204002},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0204002},
    primaryClass={cs.DM cs.CG cs.GT}
}