  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 reached from a natural starting position, i.e.,
whether the position is "valid" or "legal" or "reachable". Most real-world
retrograde Chess problems ask for the last few moves of such a sequence; we
analyze the decision question which gets at the existence of an exponentially
long move sequence. A "helpmate" problem asks whether it is possible for a
player to become checkmated by any sequence of moves from a given position. A
helpmate problem is essentially a cooperative form of Chess, where both players
work together to cause a particular player to win; it also arises in regular
Chess games, where a player who runs out of time (flags) loses only if they
could ever possibly be checkmated from the current position (i.e., the helpmate
problem has a solution). Our PSPACE-hardness reductions are from a variant of a
puzzle game called Subway Shuffle.
