Library / Computational Thinking DPF
Jump to passage
In this reading

Link to current text

Published source confirmed at last check

Source changed 2026-10-03 02:22:15 UTC · snapshot created 2026-10-03 03:38:22 UTC · last check 2026-10-03 03:50:10 UTC

CMP.4:5.2 - Use a conflict, then revise its assumptions

Three tasks A, B and C must occupy slots 0 or 1. Every pair conflicts, so conflicting tasks must use different slots. After choosing A=0, propagation forces B=1 and leaves C with no allowed slot. The branch is infeasible. Choosing A=1 gives the symmetric conflict. Exhausting these two A choices proves that no assignment exists under these constraints.

If a third slot 2 becomes available, the earlier impossibility no longer applies. The construction A=0, B=1, C=2 is feasible. An implementation reusing conflicts learned under the two-slot domain must retain or reconsider that domain assumption. Searching faster with an obsolete conflict would prevent the useful new answer.