Sudoku Solver — Backtracking in Action

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def propagate_naked_singles(domains):
    """
    Find and propagate all naked singles.
    A naked single is a cell with only one possible value.
    
    Returns:
        True if propagation succeeded
        False if contradiction detected (empty domain created)
    """
    changed = True
    
    while changed:
        changed = False
        
        for row in range(9):
            for col in range(9):
                if len(domains[row][col]) == 1:
                    # This is a naked single - propagate it
                    value = next(iter(domains[row][col]))
                    
                    # Remove this value from all peers
                    for peer_r, peer_c in get_peers(row, col):
                        if value in domains[peer_r][peer_c]:
                            domains[peer_r][peer_c].discard(value)
                            changed = True
                            
                            # Check for contradiction
                            if len(domains[peer_r][peer_c]) == 0:
                                return False  # Contradiction!
    
    return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

def propagate_hidden_singles(domains):
    """
    Find and propagate all hidden singles.
    A hidden single: value can only go in one cell within a unit.
    
    This is more powerful than naked singles - it finds forced
    moves that aren't obvious from individual cell domains.
    """
    changed = True
    
    while changed:
        changed = False
        
        # Check each unit (rows, columns, boxes)
        for unit in all_units():  # Returns list of 27 units
            for value in range(1, 10):
                # Find cells in this unit that can contain this value
                possible_cells = []
                
                for row, col in unit:
                    if value in domains[row][col]:
                        possible_cells.append((row, col))
                
                if len(possible_cells) == 0:
                    # Value cannot be placed - contradiction
                    # (unless already placed, which we handled)
                    pass
                elif len(possible_cells) == 1:
                    # Hidden single: only one cell can have this value
                    row, col = possible_cells[0]
                    
                    if len(domains[row][col]) > 1:
                        # Set domain to singleton
                        domains[row][col] = {value}
                        changed = True
                        
                        # Propagate this as a naked single
                        if not propagate_from_cell(domains, row, col, value):
                            return False
    
    return True
 
def all_units():
    """Generate all 27 Sudoku units (9 rows + 9 columns + 9 boxes)."""
    units = []
    
    # Rows
    for r in range(9):
        units.append([(r, c) for c in range(9)])
    
    # Columns
    for c in range(9):
        units.append([(r, c) for r in range(9)])
    
    # Boxes
    for box_r in range(3):
        for box_c in range(3):
            box = []
            for r in range(box_r * 3, box_r * 3 + 3):
                for c in range(box_c * 3, box_c * 3 + 3):
                    box.append((r, c))
            units.append(box)
    
    return units

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

def find_naked_pairs(domains, unit):
    """
    Find and apply naked pairs within a unit.
    
    A naked pair: two cells with identical 2-value domains.
    Effect: remove those two values from all other cells in unit.
    
    Args:
        domains: 9x9 array of domain sets
        unit: list of (row, col) tuples forming a unit
    
    Returns:
        True if any domain was reduced
    """
    changed = False
    
    # Find all cells with exactly 2 candidates
    pairs = []
    for row, col in unit:
        if len(domains[row][col]) == 2:
            pairs.append((row, col, frozenset(domains[row][col])))
    
    # Look for matching pairs
    seen = {}
    for row, col, domain in pairs:
        if domain in seen:
            # Found a naked pair!
            pair_row, pair_col = seen[domain]
            pair_values = domain
            
            # Remove these values from all OTHER cells in unit
            for other_row, other_col in unit:
                if (other_row, other_col) not in [(row, col), (pair_row, pair_col)]:
                    for val in pair_values:
                        if val in domains[other_row][other_col]:
                            domains[other_row][other_col].discard(val)
                            changed = True
        else:
            seen[domain] = (row, col)
    
    return changed
 
def find_naked_triples(domains, unit):
    """
    Find and apply naked triples within a unit.
    
    A naked triple: three cells whose combined candidates are
    exactly 3 values (each cell has 2-3 of these values).
    
    Example: cells with {1,2}, {2,3}, {1,3} form a naked triple
    for values 1, 2, 3.
    """
    from itertools import combinations
    
    changed = False
    
    # Find cells with 2-3 candidates
    candidates = []
    for row, col in unit:
        if 2 <= len(domains[row][col]) <= 3:
            candidates.append((row, col))
    
    # Try all combinations of 3 cells
    for triple in combinations(candidates, 3):
        # Get union of all domains
        combined = set()
        for row, col in triple:
            combined |= domains[row][col]
        
        if len(combined) == 3:
            # This is a naked triple!
            triple_values = combined
            triple_cells = set(triple)
            
            # Remove these values from other cells
            for row, col in unit:
                if (row, col) not in triple_cells:
                    for val in triple_values:
                        if val in domains[row][col]:
                            domains[row][col].discard(val)
                            changed = True
    
    return changed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def order_values_lcv(domains, row, col):
    """
    Order candidate values by Least Constraining Value heuristic.
    
    For each value in the cell's domain, count how many times it
    appears in peer domains. Values appearing less frequently in
    peers are less constraining and tried first.
    
    Returns: list of values sorted from least to most constraining
    """
    candidates = list(domains[row][col])
    
    if len(candidates) <= 1:
        return candidates  # No ordering needed
    
    # Count constraint impact for each candidate
    def constraint_count(value):
        count = 0
        for peer_r, peer_c in get_peers(row, col):
            if value in domains[peer_r][peer_c]:
                count += 1
        return count
    
    # Sort by ascending constraint count (least constraining first)
    candidates.sort(key=constraint_count)
    
    return candidates
 
def solve_with_lcv(board, domains):
    """Solver using both MRV (variable) and LCV (value) ordering."""
    cell = find_cell_mrv(board, domains)
    
    if cell is None:
        return True  # Solved
    
    row, col = cell
    
    if len(domains[row][col]) == 0:
        return False  # Contradiction
    
    # Order values by LCV heuristic
    ordered_values = order_values_lcv(domains, row, col)
    
    for value in ordered_values:
        saved_domains = deep_copy(domains)
        
        board[row][col] = value
        domains[row][col] = {value}
        
        if propagate(domains, row, col, value):
            if solve_with_lcv(board, domains):
                return True
        
        board[row][col] = 0
        domains = restore_from(saved_domains)
    
    return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

def preprocess_puzzle(puzzle):
    """
    Preprocess a Sudoku puzzle before search.
    
    Returns:
        (board, domains, is_solved, is_solvable)
        - board: updated board with forced values filled
        - domains: 9x9 array of domain sets
        - is_solved: True if preprocessing solved the puzzle
        - is_solvable: False if contradiction detected
    """
    board = [row[:] for row in puzzle]
    domains = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
    
    # Step 1: Initialize domains from given clues
    for r in range(9):
        for c in range(9):
            if board[r][c] != 0:
                value = board[r][c]
                domains[r][c] = {value}
                
                # Remove from peers
                for peer_r, peer_c in get_peers(r, c):
                    domains[peer_r][peer_c].discard(value)
    
    # Step 2: Cascade propagation until no progress
    progress = True
    while progress:
        progress = False
        
        # Propagate naked singles
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0 and len(domains[r][c]) == 1:
                    value = next(iter(domains[r][c]))
                    board[r][c] = value
                    progress = True
                    
                    # Remove from peers
                    for peer_r, peer_c in get_peers(r, c):
                        if value in domains[peer_r][peer_c]:
                            domains[peer_r][peer_c].discard(value)
                            
                            if len(domains[peer_r][peer_c]) == 0:
                                return board, domains, False, False  # Unsolvable
        
        # Propagate hidden singles
        for unit in all_units():
            for value in range(1, 10):
                possible_cells = [(r, c) for r, c in unit 
                                  if board[r][c] == 0 and value in domains[r][c]]
                
                if len(possible_cells) == 0:
                    # Value already placed or impossible
                    if not any(board[r][c] == value for r, c in unit):
                        return board, domains, False, False  # Unsolvable
                elif len(possible_cells) == 1:
                    r, c = possible_cells[0]
                    if len(domains[r][c]) > 1:
                        domains[r][c] = {value}
                        progress = True
    
    # Step 3: Check if solved
    is_solved = all(board[r][c] != 0 for r in range(9) for c in range(9))
    
    return board, domains, is_solved, True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

# DLX is complex; here's the conceptual structure
 
class DLXNode:
    """
    Doubly-linked node in all 4 directions.
    Enables O(1) removal and restoration.
    """
    def __init__(self):
        self.left = self.right = self
        self.up = self.down = self
        self.column = None
        self.row_id = None
 
class DLXColumn(DLXNode):
    """Column header with size tracking."""
    def __init__(self, name):
        super().__init__()
        self.name = name
        self.size = 0  # Number of nodes in this column
 
def cover(column):
    """
    Remove a column and all rows that intersect it.
    This is the key operation that makes DLX efficient.
    """
    # Remove column header from header list
    column.right.left = column.left
    column.left.right = column.right
    
    # For each row in this column, remove from other columns
    row = column.down
    while row != column:
        node = row.right
        while node != row:
            node.down.up = node.up
            node.up.down = node.down
            node.column.size -= 1
            node = node.right
        row = row.down
 
def uncover(column):
    """
    Restore a column and all its rows.
    Simply reverses cover operations in reverse order.
    """
    row = column.up
    while row != column:
        node = row.left
        while node != row:
            node.column.size += 1
            node.down.up = node
            node.up.down = node
            node = node.left
        row = row.up
    
    column.right.left = column
    column.left.right = column
 
def algorithm_x(header, solution=None):
    """
    Algorithm X with DLX implementation.
    Recursively covers columns until all are covered (solution found)
    or no valid choice remains (backtrack).
    """
    if solution is None:
        solution = []
    
    # Base case: all columns covered
    if header.right == header:
        return solution.copy()  # Solution found!
    
    # Choose column with minimum size (MRV analogue)
    column = None
    min_size = float('inf')
    c = header.right
    while c != header:
        if c.size < min_size:
            min_size = c.size
            column = c
        c = c.right
    
    if min_size == 0:
        return None  # Dead end: uncoverable column
    
    cover(column)
    
    # Try each row that covers this column
    row = column.down
    while row != column:
        solution.append(row.row_id)
        
        # Cover all other columns this row satisfies
        node = row.right
        while node != row:
            cover(node.column)
            node = node.right
        
        # Recursive search
        result = algorithm_x(header, solution)
        if result is not None:
            return result
        
        # Backtrack: uncover columns in reverse order
        solution.pop()
        node = row.left
        while node != row:
            uncover(node.column)
            node = node.left
        
        row = row.down
    
    uncover(column)
    return None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

class OptimizedSudokuSolver:
    """
    Production-grade Sudoku solver integrating all optimizations.
    """
    
    def __init__(self):
        self.board = None
        self.row_mask = [0] * 9
        self.col_mask = [0] * 9
        self.box_mask = [0] * 9
        self.empty_cells = []
        self.nodes_explored = 0
    
    def solve(self, puzzle):
        """Main entry point."""
        self.nodes_explored = 0
        
        # Phase 1: Preprocessing
        self.board = [row[:] for row in puzzle]
        self._initialize_masks()
        
        # Phase 2: Initial propagation
        if not self._initial_propagation():
            return None  # Unsolvable
        
        # Phase 3: Check if already solved
        self._compute_empty_cells()
        if not self.empty_cells:
            return self.board  # Solved by propagation
        
        # Phase 4: Backtracking search with optimizations
        if self._search():
            return self.board
        return None
    
    def _initialize_masks(self):
        """Initialize bitset masks from puzzle."""
        for r in range(9):
            for c in range(9):
                if self.board[r][c] != 0:
                    self._place(r, c, self.board[r][c])
    
    def _get_valid_mask(self, row, col):
        """Get bitmask of valid values for a cell."""
        used = self.row_mask[row] | self.col_mask[col] | self.box_mask[self._box(row, col)]
        return (~used) & 0x3FE  # Bits 1-9
    
    def _box(self, row, col):
        return (row // 3) * 3 + (col // 3)
    
    def _place(self, row, col, value):
        bit = 1 << value
        self.row_mask[row] |= bit
        self.col_mask[col] |= bit
        self.box_mask[self._box(row, col)] |= bit
        self.board[row][col] = value
    
    def _remove(self, row, col, value):
        bit = ~(1 << value)
        self.row_mask[row] &= bit
        self.col_mask[col] &= bit
        self.box_mask[self._box(row, col)] &= bit
        self.board[row][col] = 0
    
    def _initial_propagation(self):
        """Propagate singles until no progress."""
        progress = True
        while progress:
            progress = False
            
            for r in range(9):
                for c in range(9):
                    if self.board[r][c] == 0:
                        valid = self._get_valid_mask(r, c)
                        
                        if valid == 0:
                            return False  # Contradiction
                        
                        if bin(valid).count('1') == 1:
                            # Naked single
                            value = (valid & -valid).bit_length() - 1
                            self._place(r, c, value)
                            progress = True
        
        return True
    
    def _compute_empty_cells(self):
        """Compute empty cells sorted by MRV (precomputed)."""
        self.empty_cells = []
        for r in range(9):
            for c in range(9):
                if self.board[r][c] == 0:
                    count = bin(self._get_valid_mask(r, c)).count('1')
                    self.empty_cells.append((count, r, c))
        
        # Sort by ascending count (MRV)
        self.empty_cells.sort()
    
    def _search(self):
        """Backtracking search with MRV and propagation."""
        self.nodes_explored += 1
        
        # Dynamic MRV: find cell with fewest options
        best_cell = None
        min_count = 10
        
        for r in range(9):
            for c in range(9):
                if self.board[r][c] == 0:
                    valid = self._get_valid_mask(r, c)
                    count = bin(valid).count('1')
                    
                    if count == 0:
                        return False  # Contradiction
                    
                    if count < min_count:
                        min_count = count
                        best_cell = (r, c, valid)
                        
                        if count == 1:
                            break  # Can't do better than 1
        
        if best_cell is None:
            return True  # All cells filled = solved
        
        row, col, valid = best_cell
        
        # Try each valid value
        while valid:
            # Extract lowest set bit
            bit = valid & -valid
            value = bit.bit_length() - 1
            valid ^= bit  # Remove this bit
            
            self._place(row, col, value)
            
            if self._search():
                return True
            
            self._remove(row, col, value)
        
        return False