Why is my python code so much slower than C++ in Sudoku Solver


  • 0
    H

    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:

    class Solution:

    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[0], p[1], ch, board): # check if it is safe to put number ch here
                board[p[0]][p[1]] = ch # put the number
                if self.solveSudoku(board): # recursion
                    return True
                board[p[0]][p[1]] = '.' # 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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.