Passed by local test, but constantly got Time Exceed Error per OJ


  • 0

    I assume this Soduko sovler is just use backtracking based on previous 36 valid sudoku.

    My code follows as below:

    Spoiler

    class Solution(object):

    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
    
        board_shape = 9  # we can change this variant when board is not 9*9
    
    
        # check the whole board shape
        if len(board) != board_shape or len(board[0]) != board_shape:
            return False
        # check board rows
        if any(not self.completeNumSet(row) for row in board):
            return False
    
        # check board cols
        if any(not self.completeNumSet(col) for col in zip(*board)):
            return False
    
        # check 3*3 cubes
        if any(not self.completeNumSet(board[i][j] for i in range(r, r+board_shape/3) for j in range(c, c+board_shape/3)) for r in xrange(0, board_shape, board_shape/3) for c in xrange(0, board_shape, board_shape/3)):
            return False
    
        return True
    
    def completeNumSet(self, nums):
        # to check whether given list nums contains repeated numbers or not
        # if len(cleans_nums) = len(set(clean_nums)), then only unique numbers in the list
        # return True
        clean_nums = [i for i in nums if i != '.']
        return len(clean_nums) == len(set(clean_nums))
    
    
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def solveSudokuHelper(board):
            for i in xrange(len(board)):
                for j in xrange(len(board[0])):
                    if (board[i][j] == '.'):
                        for val in xrange(1,10):
                            #board[i][j] = str(val)
                            board_cell_tmp = list(board[i])
                            board_cell_tmp[j] = str(val)
                            board[i] = ''.join(board_cell_tmp)
                            if self.isValidSudoku(board) and solveSudokuHelper(board):
                                return True
                            #board[i][j] = '.'
                            board_cell_tmp = list(board[i])
                            board_cell_tmp[j] = '.'
                            board[i] = ''.join(board_cell_tmp)
                        return False
            return True
        solveSudokuHelper(board)
    

    The way to test it on my local laptop is :
    if name == 'main':
    board = ["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]
    print Solution().solveSudoku(board) # to verify whether ':rtype: void Do not return anything'. Should be 'None'
    print board # Should be a filled board

    The local result is :
    None
    ['519748632', '783652419', '426139875', '357986241', '264317598', '198524367', '975863124', '832491756', '641275983']
    [Finished in 3.3s]

    I aasume 3.3s (3300ms) should be an acceptable result. However, I constantly got "Time Exceed Error" per OJ. I also tried to use "Run code" to test the local test case perOJ, the expected result should be a list of string, as above, but actually blank.

    I guess maybe I call the method in a wrong way, but I am now really stuck and don't know how to make it correct per OJ

    Call for help! thanks


  • 0

    @coder42 Your solution is indeed quite inefficient, there is a way we can just record the taken position easily by array and then each time we can just set, check and then unset them when traversing around.

    B.T.W. your running time locally cannot represent that in the OJ, you should always understand that.

    For your convenience, here is my solution in C++ which just adopt what I mentioned above and get the best time cost.

    class Solution {
    private:
        bool search(vector<vector<char>>& board, int r, int c, bool rTakens[][9], bool cTakens[][9], bool subTakens[][9])
        {
            if(r == 9) return true;
            if(c == 9) return search(board, r+1, 0, rTakens, cTakens, subTakens);
            if(board[r][c] != '.') return search(board, r, c+1, rTakens, cTakens, subTakens);
            for(char a = '1'; a <= '9'; ++a)
            {
                int num = a -'0', k = r/3*3+c/3;
                if(!(rTakens[r][num] || cTakens[c][num] || subTakens[k][num]))
                {
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                    board[r][c] = a;
                    if(search(board, r, c+1, rTakens, cTakens, subTakens)) return true;
                    board[r][c] = '.';
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = false;
                }
            }
            return false;
        }
    public:
        void solveSudoku(vector<vector<char>>& board) {
            bool rTakens[9][9]{{false}}, cTakens[9][9]{{false}}, subTakens[9][9]{{false}};
            for(int r = 0; r < 9; ++r)
            for(int c = 0; c < 9; ++c)
                    if(board[r][c] != '.')
                    {
                        int num = board[r][c] -'0', k = r/3*3+c/3;
                        rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                    }
            search(board, 0, 0, rTakens, cTakens, subTakens);
        }
    };
    

  • 0

    @LHearen said in Passed by local test, but constantly got Time Exceed Error per OJ:

    my solution in C++ which [...] get the best time cost

    What do you mean? I just submitted it five times, got accepted in 4ms, 13ms, 4ms, 4ms and 4ms. And submissions with 0ms exist.


  • 0

    @StefanPochmann

    # check board rows
        if any(not self.completeNumSet(row) for row in board):
            return False
    
        # check board cols
        if any(not self.completeNumSet(col) for col in zip(*board)):
            return False
    
        # check 3*3 cubes
        if any(not self.completeNumSet(board[i][j] for i in range(r, r+board_shape/3) for j in range(c, c+board_shape/3)) for r in xrange(0, board_shape, board_shape/3) for c in xrange(0, board_shape, board_shape/3)):
            return False
    

    Each time encountering a cell, he is trying to check it by this logic which I think we can just use space for better time cost as presented in my C++ solution.


  • 0

    @LHearen I don't see how that answers my question, now I'm even more confused than before :-P


  • 0

    @LHearen

    Yes. You are right about "Each time encountering a cell, he is trying to check it by this logic ".

    For every cell ,I checked the whole board. I think this is one of reason you mentioned "inefficiency". Instead of checking the whole board, I could "record the taken position easily by array and then each time we can just set, check and then unset them when traversing around."

    I will try to implement yours first to see how it is going.

    @StefanPochmann I think @LHearen 's words means that his solution is better about time/space complexity, compared to mine, not the 'Best' one compared to all :)

    Thanks!! @LHearen @StefanPochmann


Log in to reply
 

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