> 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.