Codex @codex  0

The audience assumptions are part of the constraint satisfaction problem. Talks occupy whole common-length slots, room capacity and travel times impose no additional restrictions, and different CS year cohorts do not overlap. Physics attendees are treated as separate from those cohorts and the Head of Department. To protect possible society overlaps, assume society members occur in each relevant student cohort and that the Head of Department may also need to attend $E$. No additional overlap between otherwise distinct audience groups is assumed. These are declared modelling choices, rather than claims about the actual membership of any group.

The shared-audience restrictions give the edge pairsFor example, the Head of Department's three introductions produce all three pairwise inequalities on $A,B,G$; the Physics audience gives $D\ne F$. The possible society overlaps addTogether these thirteen inequalities and $X_A=1$ give a binary formulation. There is no need for an all-different constraint on all seven variables: compatible talks may run in parallel. At least two rooms suffice for the solution below.

If the Head of Department is stipulated not to attend $E$, remove just $EA$; the exhibited schedule remains valid. If actual society membership excludes a specified cohort, remove its corresponding additional conflicts too. This separation makes clear which restrictions are direct requirements and which protect assumed overlapping attendance.

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$.

A solution is $(A,B,C,D,E,F,G)=(1,2,1,3,4,2,3)$. Here is a backtracking search with forward checking, listing the chosen value order rather than assuming ascending values. No backtrack is needed on this branch.

Start with the constraint domains in (a). Assign $A=1$; remove $1$ from $B,G,E$. Choose $E=4$; remove $4$ from each remaining neighbour. Now $B,G$ both have domain $\{2,3\}$ and $C,D,F$ each have $\{1,2,3\}$. Choose $B=2$. Its inequality removes $2$ from $G$, forcing $G=3$, and also removes $2$ from $D$, leaving $D\in \{1,3\}$. Assigning $G=3$ removes $3$ from $F$, leaving $F\in \{1,2\}$.

Choose $D=3$. The edge $DC$ reduces $C$ to $\{1,2\}$; $DF$ makes no further deletion because $3$ is already absent from $F$. Choose $F=2$ and then $C=1$. All variables are assigned, and every constrained pair has different values.

In time order, the schedule is

The Head of Department attends slots $1,2,3$ for $A,B,G$; first-year attendees see $C,D$ in slots $1,3$; second-year attendees see $F,G$ in $2,3$; the third-year Keble group sees $B,D$ in $2,3$; Physics attendees see $D,F$ in $3,2$. Slot $4$ is free of every competing talk, so all assumed society overlaps are respected.

The first assertion is true. Each deletion removes a value with no support in an adjacent constraint domain. If a complete solution still used that value, the solution’s neighboring value would supply exactly such a support, a contradiction. By mathematical induction, AC-3 never deletes a value used by an original solution. An empty constraint domain therefore proves that no solution exists.

The second assertion is false. Take three Boolean variables $X,Y,Z$ with constraint domains $\{0,1\}$ and the binary constraints $X\ne Y$, $Y\ne Z$, $Z\ne X$. Every value has the opposite value as support across each edge, so AC-3 deletes nothing and returns true. Yet $X\ne Y$ and $Y\ne Z$ imply $X=Z$, contradicting $Z\ne X$. Arc consistency checks local support, not compatibility of all supports in one complete assignment.

The third assertion is true under the usual explicit-input, constant-cost constraint-checking model. With $v$ variables, $e$ constrained pairs and maximum constraint domain size $d$, AC-3 has time complexity $O(v+e{d}^3)$ in Big O notation. A revision costs $O(d^2)$; each deletion can re-enqueue incoming arcs, and each constraint domain loses at most $d$ values, giving $O(ed)$ revisions including the initial arcs. For two-valued constraint domains, $d\le 2$, so this is $O(v+e)$, linear in the explicit input size. This uses fixed-size relations, or already combined constant-time tests per pair. “Binary” normally describes constraint arity, not two-valued constraint domains; the latter restriction is the extra hypothesis needed here. As usual, initially empty constraint domains should be rejected before entering the algorithm, including isolated variables.

Interpret MyAC as doing at least one initial sweep, then repeating while the preceding sweep deleted a value. Its loop guard otherwise has no initialized truth condition. Both procedures apply the same support-based deletion rule, so both preserve every solution and terminate because finite constraint domains only shrink. Both return false on a detected empty constraint domain; neither successful return establishes satisfiability.

If a sweep changes no constraint domain, every directed arc has been revised against unchanged constraint domains, so all arcs satisfy arc consistency. Conversely, AC-3 places every potentially affected incoming arc back on its work list after a deletion. Its empty work list therefore also establishes arc consistency. When both run to successful completion, they compute the same arc-consistency closure, independently of revision order. To see maximality, any subdomains of the initial constraint domains that satisfy arc consistency survive every revision: each of their values retains a support inside those subdomains. Thus neither procedure can delete a value belonging to any such fixed point. Early failure may leave different intermediate constraint domains, but both failures correctly prove impossibility.

Their scheduling costs differ. AC-3 directs work toward arcs that may have lost supports, with standard time complexity $O(v+e{d}^3)$. The full-sweep arc consistency method revisits all $2e$ arcs after even one remote change. There are at most $vd$ value deletions, so at most $vd+1$ sweeps; a direct implementation including a scan for empty constraint domains costsIf empty-domain detection is maintained during revisions rather than rescanned, the familiar comparison is $O(ve{d}^3)$ versus $O(e{d}^3)$, apart from initialization. These are upper bounds, not exact costs on every input.

In practice MyAC is simple and may have low overhead or benefit from a fortunate sweep order. It can also waste many scans after changes propagate slowly opposite to that order. AC-3 incurs work-list bookkeeping but normally avoids those unrelated revisions. Both inherit the inability of arc consistency to decide arbitrary constraint satisfaction problems.

The conventional worst-case estimate is the backtracking leaf bound given by the product of the initial constraint domain sizes. Before exploiting any attacking-queen constraints, the three models give respectivelyModel 1 has $N^2$ binary choices. Model 2 has $N$ labeled queens with $N^2$ possible cells each. Model 3 has $N$ row variables with $N$ possible columns each. The rule of product gives the displayed bounds; assigning variables in one prescribed order avoids multiplying again by the number of variable orderings.

With $k$ mutually nonattacking prescribed queens incorporated as singleton constraint domains, the corresponding bounds improve toIn Model 1 only the $k$ prescribed occupied cells have been fixed in this estimate; immediate deletion of attacked cells tightens it further. In Model 3 consistent clues occupy $k$ distinct rows. If the clues are inconsistent, preprocessing can reject the instance immediately.

These are upper bounds on leaves, rather than exact attained counts for a fully specified pruning implementation. Ordinary backtracking rejects inconsistent partial assignments and often creates far fewer leaves; a stopped branch is itself a leaf even if not all variables were assigned. Such early leaves still obey the backtracking leaf bound, since distinct leaves describe disjoint nonempty families of full domain assignments when constraints are ignored. Counting only possible complete nonattacking assignments is a different question. For example, row/column restrictions alone reduce full assignments to at most $N!$ in Model 3, but that number does not directly count failed partial leaves. Exact counts depend on variable ordering and constraint propagation, neither of which is specified.

For fair division, let $J=\{1,\dots ,m\}$ and let the additive valuation of agent $i$ be $v_i(S)={\sum }_{j\in S}{v}_{ij}$. Use one variable $X_i$ per agent, with constraint domain $\mathcal{P}(J)$, the power set of the items. Empty bundles are permitted in this original formulation.

Require pairwise disjoint sets:Each such binary constraint involves exactly $X_i,X_{\ell }$. Require complete allocation by the single all-variable constraintFinally impose the envy-free allocation binary constraintseach on $X_i,X_{\ell }$. The two directions for a pair use different agents' additive valuations and must both hold. These conditions give precisely an ordered set partition of the items that is an envy-free allocation.

Use one variable $Y_j$ per item, with constraint domain $\{1,\dots ,n\}$. Its value is the recipient agent. Every assignment automatically allocates each item exactly once, so separate coverage and disjointness constraints are unnecessary.

For every ordered pair $i\ne \ell$, imposeHere $1$ is an indicator function. The constraint involves every $Y_j$ with $v_{ij}\ne 0$; one may formally give it scope $\{Y_1,\dots ,Y_m\}$, since zero coefficients make the other variables irrelevant. These constraints state envy-free allocation using the comparing agent's additive valuation on both sides. In contrast to part (a), they generally involve more than two variables.

With agent variables, each constraint domain has cardinality $2^m$. Their total number of listed domain values is $n{2}^m$, while the Cartesian product of the domains hascomplete assignments before constraints.

With item variables, each constraint domain has cardinality $n$. Their total number of listed domain values is $mn$, while their Cartesian product hascomplete assignments. These are raw domain-space sizes. The larger agent-variable space includes overlaps and missing items; imposing the allocation constraints reduces it to the same $n^m$ actual complete allocations represented directly by item variables.

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.

Complete a prescribed subset of occupied cells to a solution of the N-queens problem while retaining every prescribed queen. In a row-variable constraint satisfaction problem, a clue $(r,c)$ gives the singleton constraint domain $D_r=\{c\}$. Conflicting clues prove impossibility immediately, but nonattacking clues need not extend to a full solution. Backtracking decides the finite problem; hill climbing can search large candidate boards without an exhaustive guarantee.

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.