12 papers
Coin-Moving Puzzles
Erik D. Demaine, Martin L. Demaine, Helena A. Verrill
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 positi…
The Complexity of Clickomania
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine +3
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player…
Enumerating Foldings and Unfoldings between Polygons and Polytopes
Erik D. Demaine, Martin L. Demaine, Anna Lubiw +1
We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous quest…
When Can You Fold a Map?
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +4
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence…
Phutball Endgames are Hard
Erik D. Demaine, Martin L. Demaine, David Eppstein
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game.…
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
Erik D. Demaine, Martin L. Demaine, Anna Lubiw +1
We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope…