2 citations · 2 across the 2 of their papers we have counts for
5 papers · 1 filter
The Legend of Zelda: The Complexity of Mechanics
Jeffrey Bosboom, Josh Brunner, Michael Coulombe +4
We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechan…
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
Josh Brunner, Erik D. Demaine, Dylan Hendrickson +1
We prove PSPACE-completeness of two classic types of Chess problems when generalized to n-by-n boards. A "retrograde" problem asks whether it is possible for a position to be reach…
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Josh Brunner, Lily Chung, Erik D. Demaine +4
Consider unit-square blocks in an square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variat…
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
Jeffrey Bosboom, Charlotte Chen, Lily Chung +12
We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, prov…
Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
We build a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining…