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.

BibTeX

@InCollection{GameTheory2000,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Helena A. Verrill},
  TITLE         = {Coin-Moving Puzzles},
  BOOKTITLE     = {More Games of No Chance},
  BOOKURL       = {http://www.msri.org/publications/books/Book42/},
  PUBLISHER     = {Cambridge University Press},
  EDITOR        = {R. J. Nowakowski},
  YEAR          = 2002,
  PAGES         = {405--431},
  NOTE          = {Collection of papers from the MSRI Combinatorial Game Theory
                   Research Workshop, Berkeley, California, July 24--28, 2000.},

  LENGTH        = {25 pages},
  COMMENTS      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.DM/0204002">
                   arXiv:cs.DM/0204002</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.
                   <P>
                   The paper is also available from the
                   <A HREF="http://www.msri.org/publications/books/Book42/contents.html">book's website</A>
                   as <A HREF="http://www.msri.org/publications/books/Book42/files/decoins.ps.gz">http://www.msri.org/publications/books/Book42/files/decoins.ps.gz</A>.
                   <P>
                   The talk is available from MSRI in
                   <A HREF="http://msri.org/publications/ln/msri/2000/gametheory/demaine/1/">streaming video</A>.},
  UPDATES       = {Ivars Peterson wrote an article describing these results,
                   &ldquo;<A HREF="http://www.sciencenews.org/20030201/mathtrek.asp">Sliding-Coin
                   Puzzles</A>&rdquo;,
                   <I><A HREF="http://www.sciencenews.org/">Science
                   News</A></I> 163(5), February 1, 2003.},
  webpages      = {fonts/coinsliding},
}

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