2002/03/31 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +3
Computer Science · #Computational Geometry (cs.CG) #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #I.3.5 #cs.CG #cs.DM #cs.GT
paper · pdf · doi:10.48550/arxiv.cs/0204002
25 pages, 33 figures. To appear in the book More Games of No Chance edited by Richard Nowakowski and published by MSRI
arxiv created 2002/03/31 · arxiv updated 2009/11/30
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.