We collect all empty cells in a list and try filling them up using only the currently available digits for that cell. As a pre-processing step, we also populate (and later use):
- One set per row to record which digits have already been used in that row.
- One set per col to record which digits have already been used in that column.
- One set per little square to record which digits have already been used in that square.
A digit is available for the empty cell (row, col) only if none of the above three contains the digit.
If there are 
from itertools import product as cartesian
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def get_sq_coord(cell_coord: int) -> int:
return cell_coord // 3
# Little squares have ids like below:
# -----------
# | 0 | 1 | 2|
# ------------
# | 3 | 4 | 5|
# ------------
# | 6 | 7 | 8|
# ------------
# Given the coordinates (row, col) of a cell in the
# bigger square, we map to the little square id
# the cell is located in.
def get_sq_id(row: int, col: int) -> int:
sq_row = get_sq_coord(row)
sq_col = get_sq_coord(col)
return sq_row * 3 + sq_col
# Cannot do [set()] * 9 because all set() has the same ref
used_in_rows = [set() for _ in range(10)]
used_in_cols = [set() for _ in range(10)]
used_in_squares = [set() for _ in range(10)]
empty_cells = []
for r, c in cartesian( range(9), repeat=2 ):
if board[r][c] == ".":
empty_cells.append([r, c])
continue
x = int(board[r][c])
used_in_rows[r].add(x)
used_in_cols[c].add(x)
id = get_sq_id(r, c)
used_in_squares[id].add(x)
def is_used(x: int, row: int, col: int) -> bool:
if x in used_in_rows[row]:
return True
if x in used_in_cols[col]:
return True
id = get_sq_id(row, col)
if x in used_in_squares[id]:
return True
return False
def use_up(x: int, row: int, col: int) -> None:
used_in_rows[row].add(x)
used_in_cols[col].add(x)
id = get_sq_id(row, col)
used_in_squares[id].add(x)
board[row][col] = str(x)
def free_up(x: int, row: int, col: int) -> None:
used_in_rows[row].remove(x)
used_in_cols[col].remove(x)
id = get_sq_id(row, col)
used_in_squares[id].remove(x)
board[row][col] = "."
def try_fill_empty_cell(index) -> bool:
if index >= len(empty_cells):
return True
row, col = empty_cells[index]
for x in range(1, 10):
if is_used(x, row, col):
continue
use_up(x, row, col)
if try_fill_empty_cell(index+1):
return True
free_up(x, row, col)
return False
try_fill_empty_cell(0)
unreasonably effective 
Leave a comment