3 citations · 5 across the 6 of their papers we have counts for
12 papers
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…
Arithmetic Expression Construction
Leo Alcock, Sualeh Asif, Jeffrey Bosboom +10
When can given numbers be combined using arithmetic operators from a given subset of to obtain a given target number? We study three variations of this pr…
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…
Tatamibari is NP-complete
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine +3
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition…
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…
Losing at Checkers is Hard
Jeffrey Bosboom, Spencer Congero, Erik D. Demaine +2
We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers whe…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw…
Computational Complexity of Generalized Push Fight
Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy
We analyze the computational complexity of optimally playing the two-player board game Push Fight, generalized to an arbitrary board and number of pieces. We prove that the game is…
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP…
Netrunner Mate-in-1 or -2 is Weakly NP-Hard
Jeffrey Bosboom, Michael Hoffmann
We prove that deciding whether the Runner can win this turn (mate-in-1) in the Netrunner card game generalized to allow decks to contain an arbitrary number of copies of a card is…
Even Edge-Matching and Jigsaw Puzzles are Really Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove the computational intractability of rotating and placing square tiles into a array such that adjacent tiles are compatible--either equal edge colors, as i…
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…