37. Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
Solution: Heap & DFS
Python:
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()
Java:
public class Solution {
public void solveSudoku(char[][] board) {
boolean[][] colUsed = new boolean[9][9];
boolean[][] rowUsed = new boolean[9][9];
boolean[][] boxUsed = new boolean[9][9];
List<Integer[]> emptyCells = new ArrayList<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
emptyCells.add(new Integer[]{i, j});
} else {
int k = i / 3 * 3 + j / 3;
int num = board[i][j] - '1';
rowUsed[i][num] = colUsed[j][num] = boxUsed[k][num] = true;
}
}
}
dfs(board, colUsed, rowUsed, boxUsed, emptyCells, 0);
}
private boolean dfs(char[][] board, boolean[][] colUsed, boolean[][] rowUsed, boolean[][] boxUsed, List<Integer[]> emptyCells, int index) {
if (index == emptyCells.size()) return true;
Integer[] cell = emptyCells.get(index);
int i = cell[0], j = cell[1], k = i / 3 * 3 + j / 3;
for (int num = 0; num < 9; num++) {
if (!rowUsed[i][num] && !colUsed[j][num] && !boxUsed[k][num]) {
rowUsed[i][num] = colUsed[j][num] = boxUsed[k][num] = true;
board[i][j] = (char) ('1' + num);
if (dfs(board, colUsed, rowUsed, boxUsed, emptyCells, index + 1)) return true;
board[i][j] = '.';
rowUsed[i][num] = colUsed[j][num] = boxUsed[k][num] = false;
}
}
return false;
}
}