What's the time complexity for solving Sudoku with backtrack method?

Question

We have a 9x9 Sudoku like this

8       0       0       0       0       0       0       0       0

0       0       3       6       0       0       0       0       0

0       7       0       0       9       0       2       0       0

0       5       0       0       0       7       0       0       0

0       0       0       0       4       5       7       0       0

0       0       0       1       0       0       0       3       0

0       0       1       0       0       0       0       6       8

0       0       8       5       0       0       0       1       0

0       9       0       0       0       0       4       0       0

Zero means empty, which needs to be filled.

We may guess the number from 1 to 9 in Matrix[i][j] , and we also need to check if there is any repeated number in i row and j column. If it is not qualified at [i][j], we need to back trace to the previous empty. So we can guess the whole Sudoku with this method. What's the time complexity? How to prove it?

Answer 1

If we backtrack, the time complexity recurrence relation will look like: T(n) = n T(n-1).

So, the overall time complexity is like n!, which is like O(n^n).

Answer 2

Can be optimized, the goal is to choose the location that is most prioritized, and choose the number that can retain the maximum success rate.