NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.

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.

> It's NP-hard

What is the "n that goes to infinity" for Sudoku? I thought that you could iterate through all possible 9x9 grids and find the ones that satisfy the rules AND are consistent with the "known" numbers. That would make it O(1), not NP-hard.