Rectangular Spiral Galaxies are still hard

Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called , the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just , , and rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape.