I solve Sudoku with backtracking accelerated by bitmasks and a “minimum remaining values” (MRV) heuristic. I keep three bitmasks for rows, columns, and 3×3 boxes to record which digits are already used. For any empty cell, the set of candidates is the complement of the union of its row/col/box masks. On each step, I pick the empty cell with the fewest candidates (MRV) to prune the search aggressively, try each candidate (set bits), update masks, recurse, and backtrack on failure. Since the puzzle is guaranteed to have a unique solution, the search terminates quickly.
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def box_id(r: int, c: int) -> int:
return (r // 3) * 3 + (c // 3)
row_mask = [0] * 9
col_mask = [0] * 9
box_mask = [0] * 9
empties = []
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
empties.append((r, c))
else:
d = ord(ch) - 49
bit = 1 << d
row_mask[r] |= bit
col_mask[c] |= bit
box_mask[box_id(r, c)] |= bit
ALL = (1 << 9) - 1
def candidates(r: int, c: int) -> int:
used = row_mask[r] | col_mask[c] | box_mask[box_id(r, c)]
return ALL ^ used
def select_index() -> int:
best_i = -1
best_count = 10
for i, (r, c) in enumerate(empties):
if board[r][c] != '.':
continue
cand = candidates(r, c)
cnt = cand.bit_count()
if cnt < best_count:
best_count = cnt
best_i = i
if cnt == 1:
break
return best_i
def dfs() -> bool:
idx = select_index()
if idx == -1:
return True
r, c = empties[idx]
cand = candidates(r, c)
if cand == 0:
return False
while cand:
b = cand & -cand
cand -= b
d = (b.bit_length() - 1)
ch = chr(d + 49)
board[r][c] = ch
row_mask[r] |= b
col_mask[c] |= b
box_mask[box_id(r, c)] |= b
if dfs():
return True
board[r][c] = '.'
row_mask[r] &= ~b
col_mask[c] &= ~b
box_mask[box_id(r, c)] &= ~b
return False
dfs()- Time: O(E)
- Space: O(1)
