Sudoku Solver — Deep Dive

A line-by-line explanation of my backtracking solver using row/col/box sets.

Goals

• Explain data structures: rows, cols, boxes.
• Walk through backtracking & undo.
• Discuss typical vs worst-case complexity.

Key snippet

# Choose next empty, try digits, recurse, undo on fail
def backtrack(index):
    if index == len(empty_cells): return True
    i, j = empty_cells[index]; b = (i//3)*3 + (j//3)
    for d in '123456789':
        if d not in rows[i] and d not in cols[j] and d not in boxes[b]:
            board[i][j] = d
            rows[i].add(d); cols[j].add(d); boxes[b].add(d)
            if backtrack(index + 1): return True
            rows[i].remove(d); cols[j].remove(d); boxes[b].remove(d)
            board[i][j] = '.'
    return False

(Add your commentary here — e.g., why sets are O(1), choosing order of cells, MRV heuristic ideas, etc.)