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

+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?
asked Apr 28 in NP-Completeness by shijie Active (276 points)
edited Apr 29 by shijie

Please log in or register to answer this question.

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