# [Python] Use priority queue, beat 98%

• 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)

heapq.heappush(self.q, entry)

return
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):
``````
``````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

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))
return changed_cells

def undo(row, col, num, changed_cells):
board[row][col] = '.'
for i, j in changed_cells:
nums = empty_cells[(i, j)]