2 citations · 2 across the 5 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
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…
cs.CC2020
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…
cs.CC2020
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…