That's not really constant time is it? Constant time implies that the time taken to solve the problem is not a function of the input size (input in this case being the sudoku board). For a board size of 9x9 it's O(9!x9!).

The paper which showed that the general case of Sudoku is NP-complete was apparently this one [1] (Linked from wikipedia)

[1] http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf