Lab: Sudoku CSP Solver

def _initialize_domains(self):
    """
    Set up initial domains for all cells.

    For empty cells (board value == 0): domain = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    For filled cells (board value != 0): domain = {board_value}

    Store domains in self.domains as a dict: {(row, col): set_of_values}

    TODO: Implement using nested loops over range(self.size)
    """
    pass

def get_neighbors(self, cell):
    """
    Return the set of all cells that share a constraint with `cell`.

    Neighbors include all cells in:
    - The same row
    - The same column
    - The same 3×3 box

    Parameters:
        cell (tuple): (row, col)

    Returns:
        set: All (row, col) tuples that constrain this cell (excluding cell itself)

    TODO: Implement using three loops (row, column, box)
    """
    pass

def is_consistent(self, cell, value):
    """
    Return True if assigning `value` to `cell` is consistent with all
    currently assigned neighbors.

    A value is consistent if no neighbor with a fixed domain of size 1
    already has the same value.

    Parameters:
        cell (tuple): (row, col) to potentially assign
        value (int): Value to check

    Returns:
        bool: True if consistent, False if conflict detected

    TODO: Iterate over neighbors; check if any neighbor is assigned
          the same value
    """
    pass

def select_unassigned_variable_basic(self):
    """
    Return the first unassigned cell (domain size > 1).
    Scan cells in row-major order: (0,0), (0,1), ..., (8,8).

    Returns:
        tuple: (row, col) of first unassigned cell, or None if all assigned

    TODO: Scan all cells and return the first with domain size > 1
    """
    pass

def backtracking_search(self):
    """
    Main backtracking search entry point.
    Uses select_unassigned_variable_basic() and is_consistent().

    Returns:
        bool: True if solution found, False if no solution exists

    When a value is assigned:
    - Set self.domains[cell] = {value}
    - Recurse
    - If recursion fails, restore the original domain (backtrack)

    TODO: Implement recursive backtracking
    """
    return self._backtrack_basic()

def _backtrack_basic(self):
    """Recursive backtracking helper."""
    pass

def select_unassigned_variable_mrv(self):
    """
    Return the unassigned cell with the fewest legal values (MRV heuristic).
    Break ties by choosing the cell with the most neighbors that are
    unassigned (degree heuristic).

    Returns:
        tuple: (row, col) of the most constrained unassigned cell,
               or None if all cells are assigned.

    TODO: Find the minimum domain size among unassigned cells,
          then apply degree heuristic tiebreaking.
    """
    pass

def revise(self, xi, xj):
    """
    Make arc (xi → xj) arc-consistent.

    Remove from xi's domain any value that has no support in xj's domain.
    A value `x` in xi's domain has "support" if there exists some `y` in xj's
    domain such that x != y (the all-different constraint).

    Parameters:
        xi (tuple): (row, col) of the variable whose domain may be reduced
        xj (tuple): (row, col) of the neighbor variable

    Returns:
        bool: True if any value was removed from xi's domain, False otherwise

    TODO: For each value in xi's domain, check if it has any support in xj's
          domain. Remove values with no support.
    """
    pass

def ac3(self):
    """
    Enforce arc consistency across the entire CSP using the AC-3 algorithm.

    Initialize the queue with all arcs (xi, xj) for every constrained pair.
    Process arcs: if REVISE reduces xi's domain, add all arcs (xk, xi) back.

    Returns:
        bool: True if arc-consistent (no empty domains), False if contradiction

    TODO: Implement using a deque (collections.deque).
          Initialize queue with all (xi, xj) pairs where xi and xj are neighbors.
    """
    pass

def solve_sudoku(self):
    """
    Solve the Sudoku puzzle using the full pipeline:

    1. Run AC-3 as preprocessing (reduce domains before search)
    2. If AC-3 returns False, the puzzle has no solution
    3. If all domains have size 1 after AC-3, puzzle is solved
    4. Otherwise, run backtracking with MRV heuristic

    Returns:
        bool: True if solved successfully, False if no solution exists

    TODO: Implement the two-phase solver
    """
    pass