Technically, Sudoku as normally defined can't be in any complexity class because there are only a finite number of 3x3 Sudoku. People say "Sudoku is NP-hard" to mean a generalized NxN Sudoku would be NP-hard. But no one would expect that to be easy.

Another interesting NP-complete problem is minesweeper and closer to true since minesweeper problems can have variable size by their definition.