Search and Optimization

Pigeonhole Infeasible

Three pigeons cannot fit into two holes with at most one per hole. This is CP-SAT-style exhaustive search on tiny data; real solvers use propagation and clause learning.

Example

Three pigeons cannot fit into two holes with at most one per hole. 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.

pigeons=(0, 0, 0)max_in_hole=3 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\hlmath{\text{max\_in\_hole=3 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=nopigeons=(1, 0, 0)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 0)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=nopigeons=(1, 0, 0)max_in_hole=2 ok=nopigeons=(1, 0, 1)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 1)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=nopigeons=(1, 0, 0)max_in_hole=2 ok=nopigeons=(1, 0, 1)max_in_hole=2 ok=nopigeons=(1, 1, 0)max_in_hole=2 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 1, 0)}&\hlmath{\text{max\_in\_hole=2 ok=no}}\end{array}

Build the concrete table

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=nopigeons=(1, 0, 0)max_in_hole=2 ok=nopigeons=(1, 0, 1)max_in_hole=2 ok=nopigeons=(1, 1, 0)max_in_hole=2 ok=nopigeons=(1, 1, 1)max_in_hole=3 ok=no\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 1, 1)}&\hlmath{\text{max\_in\_hole=3 ok=no}}\end{array}

Read the table verdict

Compute the highlighted logic-table value.

pigeons=(0, 0, 0)max_in_hole=3 ok=nopigeons=(0, 0, 1)max_in_hole=2 ok=nopigeons=(0, 1, 0)max_in_hole=2 ok=nopigeons=(0, 1, 1)max_in_hole=2 ok=nopigeons=(1, 0, 0)max_in_hole=2 ok=nopigeons=(1, 0, 1)max_in_hole=2 ok=nopigeons=(1, 1, 0)max_in_hole=2 ok=nopigeons=(1, 1, 1)max_in_hole=3 ok=noverdictUNSAT: every row violates a hole capacity\begin{array}{c|c}\text{pigeons=(0, 0, 0)}&\text{max\_in\_hole=3 ok=no}\\\text{pigeons=(0, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(0, 1, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 0, 1)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 1, 0)}&\text{max\_in\_hole=2 ok=no}\\\text{pigeons=(1, 1, 1)}&\text{max\_in\_hole=3 ok=no}\\\text{verdict}&\hlmath{\text{UNSAT: every row violates a hole capacity}}\end{array}
logic-computation Every row is intentionally ordered and pinned to the lesson specification.