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

• 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

• @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.

``````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);
}
};
``````

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

• @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.

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

• 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

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