Fill in a partially completed 9 x 9 Sudoku board so that every row, every column and every 3 x 3 box contains each digit from 1 to 9 exactly once. Empty cells are shown as ".". Modify board in place; the method returns nothing. The input is guaranteed to have a solution.
- board.length == 9 and board[i].length == 9
- board[i][j] is a digit 1 to 9 or "."
- The puzzle has at least one solution
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying all 9^k fillings of k empty cells and checking the board at the end is hopeless. Backtracking fills one cell at a time and checks the rules immediately, so most wrong choices die within a step or two. The key is fast checking: keep a set (or a bitmask) of digits used in each row, column and box, so a candidate digit is tested in O(1) and undone in O(1) when we backtrack. Returning true as soon as the last cell is filled stops the search and leaves the solved board in place.
Algorithm
- Scan the board once: record used digits per row, column and box, and collect the list of empty cells.
- Define
solve(i): ifiequals the number of empty cells, returntrue. - For cell
(r, c)= empties[i], try each digit not used inrows[r],cols[c]orboxes[b]. - Place it, mark it used, and if
solve(i + 1)is true return true; otherwise unmark it. - If no digit works, reset the cell to
"."and returnfalse.
O(9^k) in the worst case for k empty cells, far less in practiceSpace: O(81) for the tables and recursionclass Solution: def solveSudoku(self, board: List[List[str]]) -> None: rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] empties = [] for r in range(9): for c in range(9): v = board[r][c] if v == ".": empties.append((r, c)) else: rows[r].add(v); cols[c].add(v); boxes[r // 3 * 3 + c // 3].add(v)Β def solve(i): if i == len(empties): return True # every cell is filled r, c = empties[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 board[r][c] = d rows[r].add(d); cols[c].add(d); boxes[b].add(d) if solve(i + 1): return True rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d) # undo board[r][c] = "." return FalseΒ solve(0)