Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable?
We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP-complete, and we show their FCP versions are Σ2P-complete. Along the way, we show that the FCP versions of 3SAT, 1-in-3 SAT, Triangle Partition, Planar 3SAT, and Latin Square are all Σ2P-complete. We show that even problems in P have difficult FCP versions, sometimes even Σ2P-complete, though “closed under cluing” problems are in the (presumably) smaller class NP; for example, FCP 2SAT is NP-complete.