Constraint Solving

Map Coloring

A triangle map needs neighboring regions to get different colors. This is CP-SAT-style exhaustive search on tiny data; real solvers use propagation and clause learning.

Example

A triangle map needs neighboring regions to get different colors. 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.

A=R B=G C=Bproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\hlmath{\text{proper triangle coloring}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\hlmath{\text{proper triangle coloring}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloringA=G B=R C=Bproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\text{proper triangle coloring}\\\text{A=G B=R C=B}&\hlmath{\text{proper triangle coloring}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloringA=G B=R C=Bproper triangle coloringA=G B=B C=Rproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\text{proper triangle coloring}\\\text{A=G B=R C=B}&\text{proper triangle coloring}\\\text{A=G B=B C=R}&\hlmath{\text{proper triangle coloring}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloringA=G B=R C=Bproper triangle coloringA=G B=B C=Rproper triangle coloringA=B B=R C=Gproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\text{proper triangle coloring}\\\text{A=G B=R C=B}&\text{proper triangle coloring}\\\text{A=G B=B C=R}&\text{proper triangle coloring}\\\text{A=B B=R C=G}&\hlmath{\text{proper triangle coloring}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloringA=G B=R C=Bproper triangle coloringA=G B=B C=Rproper triangle coloringA=B B=R C=Gproper triangle coloringA=B B=G C=Rproper triangle coloring\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\text{proper triangle coloring}\\\text{A=G B=R C=B}&\text{proper triangle coloring}\\\text{A=G B=B C=R}&\text{proper triangle coloring}\\\text{A=B B=R C=G}&\text{proper triangle coloring}\\\text{A=B B=G C=R}&\hlmath{\text{proper triangle coloring}}\end{array}

Read the table verdict

Compute the highlighted logic-table value.

A=R B=G C=Bproper triangle coloringA=R B=B C=Gproper triangle coloringA=G B=R C=Bproper triangle coloringA=G B=B C=Rproper triangle coloringA=B B=R C=Gproper triangle coloringA=B B=G C=Rproper triangle coloringverdict6 proper colorings\begin{array}{c|c}\text{A=R B=G C=B}&\text{proper triangle coloring}\\\text{A=R B=B C=G}&\text{proper triangle coloring}\\\text{A=G B=R C=B}&\text{proper triangle coloring}\\\text{A=G B=B C=R}&\text{proper triangle coloring}\\\text{A=B B=R C=G}&\text{proper triangle coloring}\\\text{A=B B=G C=R}&\text{proper triangle coloring}\\\text{verdict}&\hlmath{\text{6 proper colorings}}\end{array}
logic-computation Every row is intentionally ordered and pinned to the lesson specification.