# Python Solution Using Backtracking(Beats 93.66% users of python)

• ``````class Solution(object):
"""docstring for Solution"""
#Generate the possible solution of the input board
def methodGenerator(self, board, arr, array, methods, level):
if level == 9:
methods.append(copy.deepcopy(array))
return
if arr[level] != -1:
self.methodGenerator(board, arr, array, methods, level + 1)
return
for num in range(0, 9):
#num presents the column，level presents the row
if board[level][num] != '.':
continue
flag = True
for index in range(0, 9):
if index == level or array[index] == -1:
continue
if num == array[index] or (num // 3 == array[index] // 3 and level // 3 == index // 3):
flag = False
break
if flag:
array[level] = num
self.methodGenerator(board, arr, array, methods, level + 1)
array[level] = -1

def reback(self, board, numMap, table, num):
if num == 9:
return board
number, methods = int(numMap[num][0]), []
self.methodGenerator(board, table[number - 1], copy.deepcopy(table[number - 1]), methods, 0)
for method in methods:
boardcopy = copy.deepcopy(board)
for i in range(9):
tempList = list(boardcopy[i])
tempList[method[i]] = chr(number + ord('0'))
boardcopy[i] = ''.join(tempList)
returnList = self.reback(boardcopy, numMap, table, num + 1)
if len(returnList) != 0:
return returnList
return []

def solveSudoku(self, board):
#table saves the postion of each kind of numbers
table = [[], [], [], [], [], [], [], [], []]
for ele in table:
for _ in range(0, 9):
ele.append(-1)
numMap = {'1' : 0, '2' : 0, '3' : 0,
'4' : 0, '5' : 0, '6' : 0,
'7' : 0, '8' : 0, '9' : 0}
#Get the number of occurrences of 1-9
for col in range(0,9):
for row in range(0,9):
char = board[col][row]
if char != '.':
numMap[char] += 1
table[int(char) - 1][col] = row
numMap = sorted(numMap.items(), key=lambda x : x[1], reverse=True)
temp = self.reback(board, numMap, table, 0)
for i in range(0, 9):
board[i] = temp[i]
``````

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