I have read @rajan.buha's C++ code here. https://oj.leetcode.com/discuss/13337/what-is-the-algorithm-of-this-problem
The method is clear: 1.Check if there is still any blank to fill, if not, return true and end. 2. If a blank is found, try 1-9 to check if it is safe to put the number here(according to the sudoku rules) .3, If it's safe, go back to 1 and continue, else, step back and cancel the number in pre-step, then try the next number.
Base on this method, I wrote my own Python method. It got accepted, but cost about 3200ms to run while the C++ only cost about 200ms.
I know that Python is slower than C++, but does it really that slow? Could anyone explain this, or is it because of my code?
Here is my code:
def solveSudoku(self, board): if not self.findUnassigned(board): return True p = self.findUnassigned(board) # find a unsigned cell, or check it as the end chars = ['1','2','3','4','5','6','7','8','9'] for ch in chars: if self.safeHere(p, p, ch, board): # check if it is safe to put number ch here board[p][p] = ch # put the number if self.solveSudoku(board): # recursion return True board[p][p] = '.' # if not right, step back and mark it as unassigned def safeHere(self, r, c, ch, board): for i in range(9): #check if it is safe for row and column if board[r][i] == ch or board[i][c] ==ch: return False for i in range(3 * (r/3), 3 * (r/3) + 3): # check if it is safe for small 3X3 box for j in range(3 * (c/3), 3 * (c/3) + 3): if board[i][j] == ch: return False return True def findUnassigned(self, board): # find the cell mark as '.', or no '.' exist as the end position =  for i in range(9): for j in range(9): if board[i][j] == '.': position = [i, j] return position return False