**Reference**:- 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.
**Comments**:- This paper is also available as arXiv:cs.DM/0204002 of the Computing Research Repository (CoRR).
The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/decoins.ps.gz.

The talk is available from MSRI in streaming video.

**Updates**:- Ivars Peterson wrote an article describing these results, “Sliding-Coin Puzzles”,
*Science News*163(5), February 1, 2003. **Length**:- The paper is 25 pages.
**Availability**:- The paper is available in PostScript (633k), gzipped PostScript (141k), and PDF (303k).
- See information on file formats.
- [Google Scholar search]
**Related webpages**:- Coin Sliding Font

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.