+1 vote
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?
in NP-Completeness by Active (276 points)
edited by

2 Answers

0 votes
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).
by AlgoMeister (1.6k points)
0 votes
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.
by AlgoMeister (964 points)

Related questions

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...