1 citations · 1 across the 2 of their papers we have counts for
8 papers
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…
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…