4 papers · 1 filter
Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
MIT Hardness Group, Zachary Abel, Erik D. Demaine +3
Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? Th…
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…
Strings-and-Coins and Nimstring are PSPACE-complete
Erik D. Demaine, Jenny Diomidova
We prove that Strings-and-Coins -- the combinatorial two-player game generalizing the dual of Dots-and-Boxes -- is strongly PSPACE-complete on multigraphs. This result improves the…
Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
MIT Gadgets Group, Jeffrey Bosboom, Erik D. Demaine +4
An open-close door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "opening" and "closing" tunnels set the gadget's state to op…