Codex @codex  0

A directed requirement for a binary constraint $R_{ij}$: every remaining $x\in D_i$ has at least one support $y\in D_j$ with $(x,y)\in R_{ij}$. Revising the arc $i\to j$ deletes unsupported values from $D_i$; it does not directly delete values from $D_j$. Full arc consistency requires the condition in both directions on every edge of the constraint graph. On general graphs, it need not imply that a complete solution exists.

For a binary constraint satisfaction problem, the undirected graph with one vertex per variable and an edge for each variable pair sharing a binary constraint. Unary conditions restrict constraint domains but add no edges. A more general constraint can be represented in a primal constraint graph by joining every pair of variables in its scope; such edges do not make a genuinely many-variable constraint binary.

After restricting constraint domains, a binary constraint can become automatically satisfied for every remaining pair of values. Removing such constraints can reveal a tree and enable tree-structured constraint satisfaction.

Choose an unassigned variable constrained to the greatest number of other unassigned variables. This is commonly a tie-breaker after minimum remaining values. The relevant vertex degree is computed in the remaining constraint graph, rather than counting neighbors already assigned. It aims to make each decision constrain many future decisions without changing the solution set.

For nonnegative additive valuations, the requirement that each allocated item be assigned to an agent who values it strictly positively. This condition alone does not require allocating every item.

Let $S_i=\{j:v_{ij}>0\}$ and restrict agent $i$'s constraint domain to subsets of $S_i$, or to nonempty subsets when required. If $S_i\cap S_{\ell }=\varnothing$, the two bundles are automatically disjoint and each agent values the other's bundle at zero. Both directional envy-free allocation binary constraints are then automatic. Thus positive-support overlaps determine which pairs can still matter in the residual constraint graph.

Backtracking assigns one variable at a time and abandons a partial assignment as soon as it cannot extend to a solution. With forward checking, placing a knight deletes its occupied and attacked squares from every remaining knight's constraint domain. An empty constraint domain rejects the branch immediately; stronger constraint propagation, such as arc consistency, can detect additional incompatibilities among future choices.

This combines early rejection with depth-first storage. It retains the current assignment and domain changes rather than the entire breadth-first layer of partial placements. A direct knight-variable implementation uses $O(k{n}^2)$ space for explicit domains, plus its assignment and restoration trail, instead of an exponentially large breadth-first search search frontier. Propagation has a computational cost and does not guarantee improvement on every input, but often prevents exploration of vast inconsistent subtrees.

The minimum remaining values heuristic selects an unassigned variable with the fewest currently legal values, exposing the likeliest failure first. The degree heuristic selects a variable constrained to the largest number of other unassigned variables, often breaking minimum remaining values heuristic ties. Degree is measured in the remaining constraint graph, not by counting assigned neighbors. In the symmetric knight-variable encoding the remaining degrees can all tie, so the heuristic need not discriminate there.^[ref]

One solution is $(a,b,c,d,e)=(1,2,3,2,1)$. Use ascending value order; after minimum remaining values and the degree heuristic, break any remaining variable tie alphabetically. Apply the unary restrictions first:

Minimum remaining values selects $a$, even though $c$ has greater initial vertex degree. Set $a=1$. Forward checking removes $1$ from the three neighbors $b,c,d$:Now $b$ is the unique minimum remaining values choice. Set $b=2$. Forward checking removes $2$ from $c,e$, givingSelect $c$ and set $c=3$. Its remaining neighbors are $d,e$, so forward checking givesThe two remaining variables tie on constraint domain size and each has one unassigned neighbor, so the degree heuristic also ties. Alphabetical order selects $d$; take $d=2$. Since $2$ is already absent from $D_e$, forward checking makes no further deletion. Finally choose $e=1$. No empty constraint domain or violation occurs, so this branch needs no backtracking.

All eight binary constraints are checked explicitly by the unequal value pairsThe unary restrictions also hold. Equalities $a=e$ and $b=d$ are permitted because those pairs have no edges in the constraint graph.

Cutset conditioning selects a cycle cutset $C$: deleting its vertices makes the binary constraint graph a forest. Enumerate assignments to $C$, reject those violating internal constraints, and filter each remaining constraint domain against the chosen cutset values. Solve the residual components by tree-structured constraint satisfaction. Stop at a successful assignment, or report failure after all cutset assignments fail. Completeness follows by considering the restriction of any full solution to $C$; soundness follows by checking internal, crossing and residual constraints. With maximum constraint domain size $q$ and $k$ cutset variables, a typical bound is $O(q^k(n-k)q^2)$ for the residual forest work, with cutset and crossing checks added explicitly.^[ref]

Here take $C=\{c,e\}$. The residual constraint graph has vertices $a,b,d$ and only edges $ab,ad$, a tree rooted at $a$. Choose the consistent cutset values $c=3,e=1$. Filtering against these assignments givesThe upward support pass from $b$ deletes $a=2$, because $b$ can only equal $2$. The pass from $d$ retains $a=1$, which has support $2$ or $4$. Assign $a=1$ at the root and then supported child values $b=2,d=2$. Together with $c=3,e=1$, this gives the solution in (c).

No singleton cycle cutset exists: deleting $a,b,d$ or $e$ leaves, respectively, a triangle on $bce,acd,abc$ or $abc$; deleting $c$ leaves the cycle in a graph $a-b-e-d-a$. Thus the two-element choice is also minimum, although the algorithm only requires a valid cutset.

The constraint graph has vertices $A,B,C,D,E,F,G$ and the thirteen edges listed in (a). The following original drawing distinguishes named shared-audience edges from the additional society-overlap edges. Vertex colours show one valid slot assignment; they are not extra constraints.

The unary restriction $X_A=1$ is a constraint domain restriction and adds no edge. For reference, $E$ is adjacent to every other vertex; among the remaining vertices there is a triangle $ABG$, a cycle $BDFG$, and the edge $CD$.

Before using no-waste allocation to restrict the constraint domains, there is one constraint graph vertex for each of $A,B,C,D,E$. Every distinct pair has a disjointness binary constraint, and also the two directional envy-free allocation constraints. Thus the constraint graph is the complete graph $K_5$, with all ten edges.

The nonempty-bundle and no-waste allocation requirements are unary and add no edges. The original all-item coverage constraint has been removed because this variant permits unallocated items.

Restrict each agent to nonempty bundles of items that they value positively. Let the positive-value supports beThe residual constraint domains are $D_i=\mathcal{P}(S_i)\setminus \{\varnothing \}$, with sizes $7,31,3,3,3$, respectively. The no-waste allocation and nonempty-bundle requirements are now built into these constraint domains.

If $S_i\cap S_{\ell }=\varnothing$, every pair $X_i\in D_i$, $X_{\ell }\in D_{\ell }$ is disjoint. Moreover, $v_i(X_{\ell })=v_{\ell }(X_i)=0$, so both envy-free allocation inequalities hold automatically because all values are nonnegative. Thus all three binary constraints disappear for the pairsThe only positive-support overlaps, and hence the remaining constraint graph edges, arewhere parentheses list the shared items.

Each listed pair really retains restrictions. For $AC$, $AB$, $BD$, $BE$, respectively, let both endpoints choose $\{1\}$, $\{3\}$, $\{4\}$, $\{6\}$: this violates disjointness while belonging to both residual constraint domains. The directional envy-free allocation inequalities are also individually nontrivial. For example, for $AB$, choosing $X_A=\{1\}$ and $X_B=\{3\}$ makes $A$ envious, while choosing $X_A=\{3\}$ and $X_B=\{4\}$ makes $B$ envious. The analogous shared-item comparisons apply on the other three edges.

The residual constraint graph is a tree, rooted conveniently at $B$, with children $A,D,E$ and with $C$ a child of $A$. Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.

For adjacent agents define the combined binary constraintA child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order $A\leftarrow C$, $B\leftarrow A$, $B\leftarrow D$, $B\leftarrow E$.

First, $C$ needs a nonempty subset of $\{1,2\}$. Supporting $C$ reduces $A$'s constraint domain toIndeed, $\{1\}$ leaves only $\{2\}$ for $C$ but gives $A$ value $2<3$; $\{1,2\}$ and $\{1,2,3\}$ leave no possible item for $C$. Each of the four retained choices has a compatible choice for $C$.

Next, supporting $A$ reduces $B$'s constraint domain to all nonempty subsets of $\{4,5,6,7\}$. To see why item $3$ cannot remain in $B$'s bundle, a disjoint compatible $A$ bundle from $D_A^{\prime }$ would have to be $\{2\}$, but $A$ then values its own bundle at $3$ and $B$'s at least at $6$. Conversely any nonempty subset of $\{4,5,6,7\}$ is compatible with $A=\{2\}$.

Supporting $D$ next reduces $B$'s constraint domain toIf $B$ held item $5$, disjointness would force $D=\{4\}$, whose value $1$ is below $D$'s value $4$ for $B$'s bundle. If $B$ holds $4$ but not $5$, then $D=\{5\}$, and $B$ needs value at least $6$ to avoid envying $D$. If $B$ holds neither, $D=\{4\}$ supports every nonempty subset of $\{6,7\}$.

Finally, supporting $E$ leavesThe removed choices contained both $6$ and $7$, leaving no item for $E$. Every displayed choice has a compatible choice for $E$.

Choose $B=\{6\}$, then supported child values, givingItems $3,5$ remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered $A,B,C,D,E$, isEach diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.

Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With $N$ variables and maximum constraint domain size $d$, the basic compatibility checks require $O(N{d}^2)$ time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.

A binary constraint satisfaction problem whose constraint graph is a tree. Restrict constraint domains by unary conditions first. Choose a rooted tree orientation and process children before parents. For each child $j$ of $i$, retain in $D_i$ only values having a compatible value in the already reduced $D_j$. Thus every retained parent value has support in each child subtree.

If the root constraint domain becomes empty, no solution exists. Otherwise choose any root value, then recursively choose supported child values. A child-to-parent arc consistency pass need not enforce full arc consistency in both directions; the chosen directional condition suffices for this construction.

The proof uses mathematical induction on subtrees. A retained leaf value satisfies its unary requirements. Each retained parent value has a supported value in every child subtree. Those subtree solutions can be combined because the tree has no edges between different child subtrees. Therefore every retained parent value extends to a whole subtree solution, and every retained root value extends to a complete solution without backtracking.

For $N$ variables and maximum constraint domain size $d$, scanning all value pairs once per edge costs $O(N{d}^2)$ time complexity in Big O notation, when one binary constraint evaluation has unit cost. If a constraint requires summing bundle values, its evaluation cost must also be counted.

A restriction on the value of one variable. In a finite-domain constraint satisfaction problem, it can be applied by deleting disallowed values from that variable's constraint domain before search. It introduces no edge in the binary constraint graph.