Paper by Erik D. Demaine

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]


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 25, 2017 by Erik Demaine.