[Python] Use priority queue, beat 98%


  • 0

    Use priority queue to maintain a list of empty cells with least possible moves at top. The self-made priority queue can update and remove in O(log n) time.

    class PriorityQueue:
        """
        A priority queue can update and remove in O(log n) time. 
        """
        def __init__(self):
            self.q = []
            self.entries = dict()
    
        def __len__(self):
            return len(self.entries)
    
        def add(self, task, priority=0):
            if task in self.entries:
                self.remove(task)
            entry = [priority, task]
            heapq.heappush(self.q, entry)
            self.entries[task] = entry
    
        def remove(self, task):
            if task not in self.entries:
                return
            self.entries.pop(task)[1] = None
            while self.q and self.q[0][1] is None:
                heapq.heappop(self.q)
    
        def top(self):
            return self.q[0][1]
    
        def pop(self):
            task = self.top()
            self.remove(task)
            return task
    
    class Solution(object):
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            row_nums = [set('123456789') for _ in xrange(9)]
            col_nums = [set('123456789') for _ in xrange(9)]
            box_nums = [set('123456789') for _ in xrange(9)]
            empty_cells = dict()
    
            def box(row, col):
                return row / 3 * 3 + col / 3
    
            for i in xrange(9):
                for j in xrange(9):
                    num = board[i][j]
                    if num == '.':
                        empty_cells[(i, j)] = None
                    else:
                        k = box(i, j)
                        row_nums[i].remove(num)
                        col_nums[j].remove(num)
                        box_nums[k].remove(num)
    
            q = PriorityQueue()
            for i, j in empty_cells:
                k = box(i, j)
                nums = row_nums[i] & col_nums[j] & box_nums[k]
                empty_cells[(i, j)] = nums
                q.add((i, j), len(nums))
    
            def dfs():
                if not empty_cells:
                    return True
                i, j = q.pop()
                nums = empty_cells.pop((i, j))
                for num in nums:
                    changed_cells = fill(i, j, num)
                    if dfs():
                        return True
                    undo(i, j, num, changed_cells)
                empty_cells[(i, j)] = nums
                return False
    
            def fill(row, col, num):
                board[row][col] = num
                changed_cells = []
                for i, j in empty_cells:
                    k = box(i, j)
                    if i == row or j == col or k == box(row, col):
                        nums = empty_cells[(i, j)]
                        if num in nums:
                            nums.remove(num)
                            changed_cells.append((i, j))
                            q.add((i, j), len(nums))
                return changed_cells
    
            def undo(row, col, num, changed_cells):
                board[row][col] = '.'
                for i, j in changed_cells:
                    nums = empty_cells[(i, j)]
                    nums.add(num)
                    q.add((i, j), len(nums))
    
            dfs()
    

Log in to reply
 

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