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?