Skip to content

Constraint Satisfaction

Problem

Solve constraint satisfaction problems using backtracking with constraint propagation (arc consistency / forward checking).

Approach

Generic CSP framework: variables have domains, constraints link variable pairs. Backtrack with MRV (Minimum Remaining Values) heuristic and forward checking to prune domains early. Includes a Sudoku solver built on the generic framework.

When to Use

Puzzle solving, scheduling, configuration — "Sudoku", "N-Queens via CSP", "timetable generation", "resource assignment with constraints". Backtracking + forward checking prunes aggressively in practice.

Complexity
Time Exponential worst case, but constraint propagation prunes
Space O(n * d) where n = variables, d = max domain size.

Implementation

constraint_satisfaction

Constraint Satisfaction Problem — generic CSP solver with Sudoku example.

Problem

Solve constraint satisfaction problems using backtracking with constraint propagation (arc consistency / forward checking).

Approach

Generic CSP framework: variables have domains, constraints link variable pairs. Backtrack with MRV (Minimum Remaining Values) heuristic and forward checking to prune domains early. Includes a Sudoku solver built on the generic framework.

When to use

Puzzle solving, scheduling, configuration — "Sudoku", "N-Queens via CSP", "timetable generation", "resource assignment with constraints". Backtracking + forward checking prunes aggressively in practice.

Complexity

Time: Exponential worst case, but constraint propagation prunes heavily. Sudoku typically solves in milliseconds. Space: O(n * d) where n = variables, d = max domain size.

CSP

Generic CSP solver using backtracking with forward checking.

Source code in src/algo/dp/constraint_satisfaction.py 
 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
class CSP[T]:
    """Generic CSP solver using backtracking with forward checking."""

    def __init__(
        self,
        variables: Sequence[str],
        domains: dict[str, list[T]],
        neighbors: Mapping[str, Sequence[str]],
        constraint: Constraint[T],
    ) -> None:
        self.variables = list(variables)
        self.domains = {v: list(d) for v, d in domains.items()}
        self.neighbors = neighbors
        self.constraint = constraint

    def solve(self) -> dict[str, T] | None:
        """Return an assignment satisfying all constraints, or None."""
        assignment: dict[str, T] = {}
        return self._backtrack(assignment)

    def _select_unassigned(self, assignment: dict[str, T]) -> str:
        """MRV heuristic: pick variable with fewest remaining values."""
        unassigned = [v for v in self.variables if v not in assignment]
        return min(unassigned, key=lambda v: len(self.domains[v]))

    def _is_consistent(self, var: str, val: T, assignment: dict[str, T]) -> bool:
        for neighbor in self.neighbors.get(var, []):
            if neighbor in assignment and not self.constraint(
                val, assignment[neighbor]
            ):
                return False
        return True

    def _forward_check(
        self, var: str, val: T, assignment: dict[str, T]
    ) -> dict[str, list[T]] | None:
        """Prune neighbor domains. Return removed values or None on wipeout."""
        removed: dict[str, list[T]] = {}
        for neighbor in self.neighbors.get(var, []):
            if neighbor in assignment:
                continue
            to_remove: list[T] = []
            for nval in self.domains[neighbor]:
                if not self.constraint(nval, val):
                    to_remove.append(nval)
            if to_remove:
                removed[neighbor] = to_remove
                for rv in to_remove:
                    self.domains[neighbor].remove(rv)
                if not self.domains[neighbor]:
                    # Domain wipeout -- restore and fail
                    for nb, vals in removed.items():
                        self.domains[nb].extend(vals)
                    return None
        return removed

    def _backtrack(self, assignment: dict[str, T]) -> dict[str, T] | None:
        if len(assignment) == len(self.variables):
            return dict(assignment)

        var = self._select_unassigned(assignment)

        for val in list(self.domains[var]):
            if not self._is_consistent(var, val, assignment):
                continue

            assignment[var] = val
            removed = self._forward_check(var, val, assignment)

            if removed is not None:
                result = self._backtrack(assignment)
                if result is not None:
                    return result
                # Restore pruned domains
                for nb, vals in removed.items():
                    self.domains[nb].extend(vals)

            del assignment[var]

        return None

solve 

solve() -> dict[str, T] | None

Return an assignment satisfying all constraints, or None.

Source code in src/algo/dp/constraint_satisfaction.py 
44
45
46
47
def solve(self) -> dict[str, T] | None:
    """Return an assignment satisfying all constraints, or None."""
    assignment: dict[str, T] = {}
    return self._backtrack(assignment)

solve_sudoku 

solve_sudoku(board: Grid) -> Grid | None

Solve a 9x9 Sudoku board in-place and return it, or None if unsolvable.

board is a 9x9 list of ints where 0 represents an empty cell.

board = [ ... [5, 3, 0, 0, 7, 0, 0, 0, 0], ... [6, 0, 0, 1, 9, 5, 0, 0, 0], ... [0, 9, 8, 0, 0, 0, 0, 6, 0], ... [8, 0, 0, 0, 6, 0, 0, 0, 3], ... [4, 0, 0, 8, 0, 3, 0, 0, 1], ... [7, 0, 0, 0, 2, 0, 0, 0, 6], ... [0, 6, 0, 0, 0, 0, 2, 8, 0], ... [0, 0, 0, 4, 1, 9, 0, 0, 5], ... [0, 0, 0, 0, 8, 0, 0, 7, 9], ... ] result = solve_sudoku(board) result is not None True

Source code in src/algo/dp/constraint_satisfaction.py 
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
def solve_sudoku(board: Grid) -> Grid | None:
    """Solve a 9x9 Sudoku board in-place and return it, or None if unsolvable.

    *board* is a 9x9 list of ints where 0 represents an empty cell.

    >>> board = [
    ...     [5, 3, 0, 0, 7, 0, 0, 0, 0],
    ...     [6, 0, 0, 1, 9, 5, 0, 0, 0],
    ...     [0, 9, 8, 0, 0, 0, 0, 6, 0],
    ...     [8, 0, 0, 0, 6, 0, 0, 0, 3],
    ...     [4, 0, 0, 8, 0, 3, 0, 0, 1],
    ...     [7, 0, 0, 0, 2, 0, 0, 0, 6],
    ...     [0, 6, 0, 0, 0, 0, 2, 8, 0],
    ...     [0, 0, 0, 4, 1, 9, 0, 0, 5],
    ...     [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ... ]
    >>> result = solve_sudoku(board)
    >>> result is not None
    True
    """
    domains: dict[str, list[int]] = {}
    variables: list[str] = []

    for r in range(9):
        for c in range(9):
            cell = f"R{r}C{c}"
            if board[r][c] != 0:
                domains[cell] = [board[r][c]]
            else:
                domains[cell] = list(range(1, 10))
            variables.append(cell)

    def not_equal(a: int, b: int) -> bool:
        return a != b

    csp: CSP[int] = CSP(variables, domains, _NEIGHBORS, not_equal)
    solution = csp.solve()

    if solution is None:
        return None

    for r in range(9):
        for c in range(9):
            board[r][c] = solution[f"R{r}C{c}"]
    return board
tests/dp/test_constraint_satisfaction.py
"""Tests for constraint satisfaction / Sudoku solver."""

import copy

from algo.dp.constraint_satisfaction import CSP, solve_sudoku


class TestCSP:
    def test_simple_coloring(self) -> None:
        """Graph coloring: 3 nodes in a triangle, 3 colors."""
        variables = ["A", "B", "C"]
        domains: dict[str, list[str]] = {
            "A": ["R", "G", "B"],
            "B": ["R", "G", "B"],
            "C": ["R", "G", "B"],
        }
        neighbors = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}

        def not_equal(a: str, b: str) -> bool:
            return a != b

        csp: CSP[str] = CSP(variables, domains, neighbors, not_equal)
        result = csp.solve()
        assert result is not None
        assert result["A"] != result["B"]
        assert result["A"] != result["C"]
        assert result["B"] != result["C"]

    def test_unsolvable(self) -> None:
        """Two connected variables with one color each (same color)."""
        variables = ["A", "B"]
        domains: dict[str, list[str]] = {"A": ["R"], "B": ["R"]}
        neighbors = {"A": ["B"], "B": ["A"]}

        def not_equal(a: str, b: str) -> bool:
            return a != b

        csp: CSP[str] = CSP(variables, domains, neighbors, not_equal)
        assert csp.solve() is None


class TestSolveSudoku:
    def test_valid_puzzle(self) -> None:
        board = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ]
        result = solve_sudoku(board)
        assert result is not None
        # Check all rows have 1-9
        for row in result:
            assert sorted(row) == list(range(1, 10))
        # Check all columns have 1-9
        for c in range(9):
            col = [result[r][c] for r in range(9)]
            assert sorted(col) == list(range(1, 10))

    def test_already_solved(self) -> None:
        board = [
            [5, 3, 4, 6, 7, 8, 9, 1, 2],
            [6, 7, 2, 1, 9, 5, 3, 4, 8],
            [1, 9, 8, 3, 4, 2, 5, 6, 7],
            [8, 5, 9, 7, 6, 1, 4, 2, 3],
            [4, 2, 6, 8, 5, 3, 7, 9, 1],
            [7, 1, 3, 9, 2, 4, 8, 5, 6],
            [9, 6, 1, 5, 3, 7, 2, 8, 4],
            [2, 8, 7, 4, 1, 9, 6, 3, 5],
            [3, 4, 5, 2, 8, 6, 1, 7, 9],
        ]
        original = copy.deepcopy(board)
        result = solve_sudoku(board)
        assert result == original

    def test_preserves_given_values(self) -> None:
        board = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ]
        original = copy.deepcopy(board)
        result = solve_sudoku(board)
        assert result is not None
        for r in range(9):
            for c in range(9):
                if original[r][c] != 0:
                    assert result[r][c] == original[r][c]

Implement it yourself

Run: just challenge dp constraint_satisfaction

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

constraint_satisfaction

Constraint Satisfaction Problem — generic CSP solver with Sudoku example.

Problem

Solve constraint satisfaction problems using backtracking with constraint propagation (arc consistency / forward checking).

Approach

Generic CSP framework: variables have domains, constraints link variable pairs. Backtrack with MRV (Minimum Remaining Values) heuristic and forward checking to prune domains early. Includes a Sudoku solver built on the generic framework.

When to use

Puzzle solving, scheduling, configuration — "Sudoku", "N-Queens via CSP", "timetable generation", "resource assignment with constraints". Backtracking + forward checking prunes aggressively in practice.

Complexity

Time: Exponential worst case, but constraint propagation prunes heavily. Sudoku typically solves in milliseconds. Space: O(n * d) where n = variables, d = max domain size.

CSP

Generic CSP solver using backtracking with forward checking.

Source code in src/algo/dp/constraint_satisfaction.py 
 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
class CSP[T]:
    """Generic CSP solver using backtracking with forward checking."""

    def __init__(
        self,
        variables: Sequence[str],
        domains: dict[str, list[T]],
        neighbors: Mapping[str, Sequence[str]],
        constraint: Constraint[T],
    ) -> None:
        self.variables = list(variables)
        self.domains = {v: list(d) for v, d in domains.items()}
        self.neighbors = neighbors
        self.constraint = constraint

    def solve(self) -> dict[str, T] | None:
        """Return an assignment satisfying all constraints, or None."""
        assignment: dict[str, T] = {}
        return self._backtrack(assignment)

    def _select_unassigned(self, assignment: dict[str, T]) -> str:
        """MRV heuristic: pick variable with fewest remaining values."""
        unassigned = [v for v in self.variables if v not in assignment]
        return min(unassigned, key=lambda v: len(self.domains[v]))

    def _is_consistent(self, var: str, val: T, assignment: dict[str, T]) -> bool:
        for neighbor in self.neighbors.get(var, []):
            if neighbor in assignment and not self.constraint(
                val, assignment[neighbor]
            ):
                return False
        return True

    def _forward_check(
        self, var: str, val: T, assignment: dict[str, T]
    ) -> dict[str, list[T]] | None:
        """Prune neighbor domains. Return removed values or None on wipeout."""
        removed: dict[str, list[T]] = {}
        for neighbor in self.neighbors.get(var, []):
            if neighbor in assignment:
                continue
            to_remove: list[T] = []
            for nval in self.domains[neighbor]:
                if not self.constraint(nval, val):
                    to_remove.append(nval)
            if to_remove:
                removed[neighbor] = to_remove
                for rv in to_remove:
                    self.domains[neighbor].remove(rv)
                if not self.domains[neighbor]:
                    # Domain wipeout -- restore and fail
                    for nb, vals in removed.items():
                        self.domains[nb].extend(vals)
                    return None
        return removed

    def _backtrack(self, assignment: dict[str, T]) -> dict[str, T] | None:
        if len(assignment) == len(self.variables):
            return dict(assignment)

        var = self._select_unassigned(assignment)

        for val in list(self.domains[var]):
            if not self._is_consistent(var, val, assignment):
                continue

            assignment[var] = val
            removed = self._forward_check(var, val, assignment)

            if removed is not None:
                result = self._backtrack(assignment)
                if result is not None:
                    return result
                # Restore pruned domains
                for nb, vals in removed.items():
                    self.domains[nb].extend(vals)

            del assignment[var]

        return None

solve 

solve() -> dict[str, T] | None

Return an assignment satisfying all constraints, or None.

Source code in src/algo/dp/constraint_satisfaction.py 
44
45
46
47
def solve(self) -> dict[str, T] | None:
    """Return an assignment satisfying all constraints, or None."""
    assignment: dict[str, T] = {}
    return self._backtrack(assignment)

solve_sudoku 

solve_sudoku(board: Grid) -> Grid | None

Solve a 9x9 Sudoku board in-place and return it, or None if unsolvable.

board is a 9x9 list of ints where 0 represents an empty cell.

board = [ ... [5, 3, 0, 0, 7, 0, 0, 0, 0], ... [6, 0, 0, 1, 9, 5, 0, 0, 0], ... [0, 9, 8, 0, 0, 0, 0, 6, 0], ... [8, 0, 0, 0, 6, 0, 0, 0, 3], ... [4, 0, 0, 8, 0, 3, 0, 0, 1], ... [7, 0, 0, 0, 2, 0, 0, 0, 6], ... [0, 6, 0, 0, 0, 0, 2, 8, 0], ... [0, 0, 0, 4, 1, 9, 0, 0, 5], ... [0, 0, 0, 0, 8, 0, 0, 7, 9], ... ] result = solve_sudoku(board) result is not None True

Source code in src/algo/dp/constraint_satisfaction.py 
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
def solve_sudoku(board: Grid) -> Grid | None:
    """Solve a 9x9 Sudoku board in-place and return it, or None if unsolvable.

    *board* is a 9x9 list of ints where 0 represents an empty cell.

    >>> board = [
    ...     [5, 3, 0, 0, 7, 0, 0, 0, 0],
    ...     [6, 0, 0, 1, 9, 5, 0, 0, 0],
    ...     [0, 9, 8, 0, 0, 0, 0, 6, 0],
    ...     [8, 0, 0, 0, 6, 0, 0, 0, 3],
    ...     [4, 0, 0, 8, 0, 3, 0, 0, 1],
    ...     [7, 0, 0, 0, 2, 0, 0, 0, 6],
    ...     [0, 6, 0, 0, 0, 0, 2, 8, 0],
    ...     [0, 0, 0, 4, 1, 9, 0, 0, 5],
    ...     [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ... ]
    >>> result = solve_sudoku(board)
    >>> result is not None
    True
    """
    domains: dict[str, list[int]] = {}
    variables: list[str] = []

    for r in range(9):
        for c in range(9):
            cell = f"R{r}C{c}"
            if board[r][c] != 0:
                domains[cell] = [board[r][c]]
            else:
                domains[cell] = list(range(1, 10))
            variables.append(cell)

    def not_equal(a: int, b: int) -> bool:
        return a != b

    csp: CSP[int] = CSP(variables, domains, _NEIGHBORS, not_equal)
    solution = csp.solve()

    if solution is None:
        return None

    for r in range(9):
        for c in range(9):
            board[r][c] = solution[f"R{r}C{c}"]
    return board