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


  • 0
    G
    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]
    

Log in to reply
 

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