Fill a Sudoku Grid
Problem
A 9 by 9 puzzle grid holds digits as the characters "1" to "9" and "." for empty cells. Fill the empty cells in place so that every row, every column and every 3 by 3 box contains each digit exactly once, and return True. If the givens already clash or no filling exists, return False.
Examples
Input: grid = ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79"]
Output: True, grid becomes ["534678912", "672195348", "198342567", ...]Input: the first row is "11......." and the rest are empty
Output: False
Why: edge case, the givens already break the row rule, so no search is neededHints
0 / 3
Fill the empty cells one at a time. For each cell, a digit is allowed only if its row, its column and its box do not already contain it.
Checking a row, column and box by scanning them costs 27 reads per try. Keep a set of used digits for every row, every column and every box so that each check is a lookup.
List the empty cells. Recurse on the index of the next empty cell: try each allowed digit, record it in the grid and the three sets, and recurse. If the recursion fails, erase the digit from all four places and try the next. Reaching the end of the list means the grid is solved.
Solution
This is the same place-check-undo pattern as placing queens row by row, with three constraint families instead of columns and diagonals. Sets of used digits for each row, column and box make a legality check three lookups, and the givens are loaded into them once, which is also where a clash among the givens shows up. The search fills the empty cells in order, trying only digits that the three sets allow, and undoes a placement in the grid and the sets as soon as the branch below it fails. The worst case is exponential in the number of empty cells, at most 9 choices each, but the constraints prune real puzzles to a small fraction of that; the extra space is O(1) for a fixed 9 by 9 grid.
def solve_sudoku(grid):
rows, cols, boxes = ([set() for _ in range(9)] for _ in range(3))
empty = []
for r in range(9):
for c in range(9):
d, b = grid[r][c], r // 3 * 3 + c // 3
if d == ".": empty.append((r, c)); continue
if d in rows[r] or d in cols[c] or d in boxes[b]: return False
rows[r].add(d); cols[c].add(d); boxes[b].add(d)
def fill(i):
if i == len(empty): return True
r, c = empty[i]; b = r // 3 * 3 + c // 3
for d in "123456789":
if d in rows[r] or d in cols[c] or d in boxes[b]: continue
grid[r][c] = d; rows[r].add(d); cols[c].add(d); boxes[b].add(d)
if fill(i + 1): return True
grid[r][c] = "."; rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
return False # nothing fits: undo above
return fill(0)
g = [list(r) for r in ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79"]]
print(solve_sudoku(g), "".join(g[0]), "".join(g[8])) # -> True 534678912 345286179
bad = [list("11......."), *[list(".........") for _ in range(8)]]
print(solve_sudoku(bad)) # -> FalseStuck on the idea rather than the code? N-Queens covers it.