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…