Instance: A $n*n$ chess pawn structure (the starting position is $n$ pawns each on their next-to-last row, as usual)
Decision Question: Is this structure legal by playing chess moves, especially sacrificing pawns (including figures promoted from missing pawns)?
Kings are not needed, pass moves are legal. You can also formulate "How many sacrifices are needed to generate this structure?" and put a few sacrificial lambs on the first ranks if needed. (I expect that $O(n^2)$ captures are maximally needed for any problem.)
Is it really as easy as counting captures, i.e., this is a simple polynomial class problem?