Constraint Solving

Constraint Filter Table

A constraint removes rows that do not satisfy it. This is CP-SAT-style exhaustive search on tiny data; real solvers use propagation and clause learning.

Example

A constraint removes rows that do not satisfy it. 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=0x+y=0 keep=no\begin{array}{c|c}\text{x=0 y=0}&\hlmath{\text{x+y=0 keep=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=no\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\hlmath{\text{x+y=1 keep=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yes\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\hlmath{\text{x+y=2 keep=yes}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=no\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\hlmath{\text{x+y=1 keep=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yes\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\hlmath{\text{x+y=2 keep=yes}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yesx=1 y=2x+y=3 keep=no\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\text{x+y=2 keep=yes}\\\text{x=1 y=2}&\hlmath{\text{x+y=3 keep=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yesx=1 y=2x+y=3 keep=nox=2 y=0x+y=2 keep=yes\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\text{x+y=2 keep=yes}\\\text{x=1 y=2}&\text{x+y=3 keep=no}\\\text{x=2 y=0}&\hlmath{\text{x+y=2 keep=yes}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yesx=1 y=2x+y=3 keep=nox=2 y=0x+y=2 keep=yesx=2 y=1x+y=3 keep=no\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\text{x+y=2 keep=yes}\\\text{x=1 y=2}&\text{x+y=3 keep=no}\\\text{x=2 y=0}&\text{x+y=2 keep=yes}\\\text{x=2 y=1}&\hlmath{\text{x+y=3 keep=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yesx=1 y=2x+y=3 keep=nox=2 y=0x+y=2 keep=yesx=2 y=1x+y=3 keep=nox=2 y=2x+y=4 keep=no\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\text{x+y=2 keep=yes}\\\text{x=1 y=2}&\text{x+y=3 keep=no}\\\text{x=2 y=0}&\text{x+y=2 keep=yes}\\\text{x=2 y=1}&\text{x+y=3 keep=no}\\\text{x=2 y=2}&\hlmath{\text{x+y=4 keep=no}}\end{array}

Read the table verdict

Compute the highlighted logic-table value.

x=0 y=0x+y=0 keep=nox=0 y=1x+y=1 keep=nox=0 y=2x+y=2 keep=yesx=1 y=0x+y=1 keep=nox=1 y=1x+y=2 keep=yesx=1 y=2x+y=3 keep=nox=2 y=0x+y=2 keep=yesx=2 y=1x+y=3 keep=nox=2 y=2x+y=4 keep=noverdictkept rows: (0,2), (1,1), (2,0)\begin{array}{c|c}\text{x=0 y=0}&\text{x+y=0 keep=no}\\\text{x=0 y=1}&\text{x+y=1 keep=no}\\\text{x=0 y=2}&\text{x+y=2 keep=yes}\\\text{x=1 y=0}&\text{x+y=1 keep=no}\\\text{x=1 y=1}&\text{x+y=2 keep=yes}\\\text{x=1 y=2}&\text{x+y=3 keep=no}\\\text{x=2 y=0}&\text{x+y=2 keep=yes}\\\text{x=2 y=1}&\text{x+y=3 keep=no}\\\text{x=2 y=2}&\text{x+y=4 keep=no}\\\text{verdict}&\hlmath{\text{kept rows: (0,2), (1,1), (2,0)}}\end{array}
logic-computation Every row is intentionally ordered and pinned to the lesson specification.