Coin-Moving Puzzles

Simple item page
dc.creatorDemaine, Erik D.
dc.creatorDemaine, Martin L.
dc.creatorVerrill, Helena A.
dc.date2002-03-31
dc.date.accessioned2026-07-07T03:18:14Z
dc.date.available2026-07-07T03:18:14Z
dc.descriptionWe 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.
dc.description25 pages, 33 figures. To appear in the book More Games of No Chance edited by Richard Nowakowski and published by MSRI
dc.identifierhttps://arxiv.org/abs/cs/0204002
dc.identifierhttp://arxiv.org/abs/cs/0204002
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31034
dc.subjectDiscrete Mathematics
dc.subjectComputational Geometry
dc.subjectComputer Science and Game Theory
dc.subjectG.2.1; G.2.2; F.2.2; I.3.5
dc.titleCoin-Moving Puzzles
dc.typetext

Files

Collections

arXiv