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 be

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 http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf