Coin-Moving Puzzles
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
25 pages, 33 figures. To appear in the book More Games of No Chance edited by Richard Nowakowski and published by MSRI
25 pages, 33 figures. To appear in the book More Games of No Chance edited by Richard Nowakowski and published by MSRI