Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up. Are there any natural puzzles that are PPAD-complete? What about other similar classes, like PPA, PPADS etc?
If we don't insist on natural, then of course practically any PPAD-complete problem would be a puzzle, just during the puzzle you would need to run the some Turing machine a couple of times. What I have in mind would be for example finding another Hamiltonian cycle in a cubic graph, which is known to be in PPA, just now known to be complete.