Constraint Solving

Domains and Assignment Space

A constraint model starts as a finite list of candidate assignments. This is CP-SAT-style exhaustive search on tiny data; real solvers use propagation and clause learning.

Example

A constraint model starts as a finite list of candidate assignments. This is an exhaustive-search view on tiny data; unlike a real CP-SAT solver, it does not propagate constraints or learn clauses.

highlighted = computed this step

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignmentx=1 y=2candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\text{candidate assignment}\\\text{x=1 y=2}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignmentx=1 y=2candidate assignmentx=2 y=0candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\text{candidate assignment}\\\text{x=1 y=2}&\text{candidate assignment}\\\text{x=2 y=0}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignmentx=1 y=2candidate assignmentx=2 y=0candidate assignmentx=2 y=1candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\text{candidate assignment}\\\text{x=1 y=2}&\text{candidate assignment}\\\text{x=2 y=0}&\text{candidate assignment}\\\text{x=2 y=1}&\hlmath{\text{candidate assignment}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignmentx=1 y=2candidate assignmentx=2 y=0candidate assignmentx=2 y=1candidate assignmentx=2 y=2candidate assignment\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\text{candidate assignment}\\\text{x=1 y=2}&\text{candidate assignment}\\\text{x=2 y=0}&\text{candidate assignment}\\\text{x=2 y=1}&\text{candidate assignment}\\\text{x=2 y=2}&\hlmath{\text{candidate assignment}}\end{array}

Read the table verdict

Compute the highlighted logic-table value.

x=0 y=0candidate assignmentx=0 y=1candidate assignmentx=0 y=2candidate assignmentx=1 y=0candidate assignmentx=1 y=1candidate assignmentx=1 y=2candidate assignmentx=2 y=0candidate assignmentx=2 y=1candidate assignmentx=2 y=2candidate assignmentverdict9 assignments before constraints\begin{array}{c|c}\text{x=0 y=0}&\text{candidate assignment}\\\text{x=0 y=1}&\text{candidate assignment}\\\text{x=0 y=2}&\text{candidate assignment}\\\text{x=1 y=0}&\text{candidate assignment}\\\text{x=1 y=1}&\text{candidate assignment}\\\text{x=1 y=2}&\text{candidate assignment}\\\text{x=2 y=0}&\text{candidate assignment}\\\text{x=2 y=1}&\text{candidate assignment}\\\text{x=2 y=2}&\text{candidate assignment}\\\text{verdict}&\hlmath{\text{9 assignments before constraints}}\end{array}
logic-computation Every row is intentionally ordered and pinned to the lesson specification.