Sudoku Solver

def solveSudoku(board):
    rows, cols, boxes = [[set() for _ in range(9)] for _ in range(3)]
    empty = []
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.': empty.append((r, c))
            else: rows[r].add(d); cols[c].add(d); boxes[r//3*3 + c//3].add(d)

    def solve(k):
        if k == len(empty): return True
        r, c = empty[k]; 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(k + 1): return True
            board[r][c] = '.'
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
        return False

    solve(0)

Sudoku Solver. Fill a nine by nine board so every row, column and three by three box holds the digits one to nine exactly once. There's exactly one solution.

Here's LeetCode's board: thirty clues and fifty-one empty cells. The top row already has five, three and seven, so its other cells can't take those.

The naive way tries every digit in every empty cell: nine to the fifty-first power fillings, a number with forty-nine digits. Hopeless.

Instead, backtrack, like a gardener planting numbered seeds. Keep a set for every row, column and box, so checking a seed is instant. Plant a digit that fits in the next empty planter. If a planter has nothing left, dig up the last seed and try its next digit.

In code: load the clues into the sets and list the empty cells. Solve skips any digit already in the row, column or box, places it, and recurses. If that fails, it removes the digit and tries the next.

On the example, the top row gets one, two, four, eight and nine. But the last cell is stuck: the row only lacks six, and its column has one. So dig up nine, then eight. Nine there jams the next cell too, so back up to the four and try six. After four thousand two hundred and eight placements and four thousand one hundred and fifty-seven undos, it's solved.

The worst case is exponential, and space is order eighty-one. Picking the cell with the fewest options first prunes far more: here, fifty-one placements and no undos.

Plant, check, and dig up when stuck. That's Sudoku Solver.