90% Python Solution


  • 0
    S
    from heapq import heappush, heappop
    
    class Sudoku(object):
    	def __init__(self, board):
    		rows = []
    		for row in range(len(board)):
    			rows.append(set(range(10))-set([0 if board[row][col] == '.' else int(board[row][col]) for col in range(len(board))]))
    		cols = []
    		for col in range(len(board[0])):
    			cols.append(set(range(10))-set([0 if board[row][col] == '.' else int(board[row][col]) for row in range(len(board[0]))]))
    		blks = []
    		for rblk in range(len(board)//3):
    			for cblk in range(len(board[0])//3):
    				blk = set()
    				for r in range(3):
    					for c in range(3):
    					    value = board[rblk*3+r][cblk*3+c]
    					    blk.add(0 if value == '.' else int(value))
    				blks.append(set(range(10))-blk)
    		blanks = set()
    		sboard = []
    		for row in range(len(board)):
    			sboard.append(board[row])
    			for col in range(len(board[0])):
    				if board[row][col] == '.':
    					blanks.add((row,col))
    		self.board = sboard
    		self.rows = rows
    		self.cols = cols
    		self.blks = blks
    		self.blanks = blanks
    	def updateOneEntry(self, loc, value):
    		row, col = loc
    		values = self.rows[row] & self.cols[col] & self.blks[(row//3)*3+(col//3)]
    		self.rows[row] -= set([value])
    		self.cols[col] -= set([value])
    		self.blks[(row//3)*3+(col//3)] -= set([value])
    		self.blanks -= set([loc])
    		self.board[row] = str(''.join(self.board[row][:col])+str(value)+''.join(self.board[row][col+1:]))
    		return True
    	def createQueue(self):
    		pq = []
    		blanks_list = list(self.blanks)
    		for loc in blanks_list:
    			row, col = loc
    			values = self.rows[row] & self.cols[col] & self.blks[(row//3)*3+(col//3)]
    			if len(values) > 0:
    				entry = [len(values), loc, values]
    				heappush(pq, entry)
    		return pq
    	def calcSolution(self):
    		pq = self.createQueue()
    		while pq:
    			priority, loc, values = heappop(pq)
    			if priority == 1:
    				self.updateOneEntry(loc, values.pop())
    				pq = self.createQueue()
    			else:	# multiple options are found
    				while values:	# test all options
    					value = values.pop()
    					s = Sudoku(self.board)
    					if s.updateOneEntry(loc, value) == False:
    						continue
    					if s.calcSolution():
    						self.board = s.board
    						return True
    				return False
    		if len(self.blanks) == 0:
    			return True
    		return False
    class Solution(object):
    	def solveSudoku(self, board):
    		sdk = Sudoku(board)
    		if sdk.calcSolution():
    		    for row in range(len(board)):
    			    board[row] = sdk.board[row]
    

Log in to reply
 

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