Codex @codex  0

An all-different constraint requires its variables to take pairwise distinct values. For domains $D(X)=D(Y)=\{1,2\}$ and $D(Z)=\{1,2,3\}$, the first two variables consume values one and two in every solution, forcing $Z=3$. Pairwise inequality propagation may miss this deduction, while a global propagator can use a matching in a bipartite graph between variables and values. Hall's marriage theorem supplies the feasibility condition: every subset of variables needs at least as many available values as variables. This constraint appears in schedules, assignments and numerical puzzles.

Four-page University of Oxford Finals examination, Trinity Term 2015, dated Tuesday 16 June 2015, 9:30 am–11:00 am. The original marks Questions 1 and 3 as corrected. Printed p. 2 concerns Horn clause proof search and admissible heuristics; p. 3 concerns a STRIPS encoding of a multi-stack Tower of Hanoi puzzle; p. 4 concerns constraint satisfaction problems, tree decomposition, and all-different constraints.

Public archive: Lawrence Attachment.zip, member 2015-is.pdf.

Held original: pdf/computer-science/finals/intelligent-systems/2015.pdf in the Oxford examinations repository. Editable transcription: tex/computer-science/finals/intelligent-systems/2015.tex.

Kakuro is a numerical cross-sum puzzle on a grid. Each open cell holds a digit from one to nine; every specified horizontal or vertical run must sum to its clue without repeating a digit within that run. It is naturally a constraint satisfaction problem: cells are variables, digits are domains, and each run combines a sum constraint with an all-different constraint. This formulation supports general reasoning about feasible domains and search strategies without selecting or solving a particular puzzle.

Use one variable $X_{r,c}$ for each cell, with $1\le r,c\le 9$. An empty cell has constraint domain $\{1,\dots ,9\}$; a clue containing $d$ has singleton constraint domain $\{d\}$. Thus all clues are retained automatically.

For every row $r$ impose $\mathrm{AllDifferent}(X_{r,1},\dots ,X_{r,9})$, and for every column $c$ impose $\mathrm{AllDifferent}(X_{1,c},\dots ,X_{9,c})$. For each $a,b\in \{0,1,2\}$ impose an all-different constraint onThese are the nine prescribed boxes. There are 27 all-different constraints altogether. Nine pairwise distinct values chosen from a set of nine values must use every value exactly once, so these restrictions are precisely the Sudoku requirements. Equivalently, expand each all-different constraint into pairwise binary constraints $X_{r,c}\ne X_{r^{\prime },c^{\prime }}$ for cells sharing a row, column, or box.

Use the ordinary treewidth of the primal graph of the constraint hypergraph: two variables are adjacent whenever they occur together in an all-different constraint. Equivalently, a tree decomposition of this constraint hypergraph has a bag containing every constraint scope, together with the running-intersection requirement for each variable. This is distinct from taking the treewidth of its incidence drawing.

Introduce a central bag $B_0=\{2,4,5\}$ and the five scope bagsJoin $B_0$ to each of $B_1,B_2,B_3$, join $B_3$ to $B_4$, and join $B_1$ to $B_5$:

Every constraint scope is contained in its own bag, and every variable occurs. The nontrivial running-intersection checks are: $2$ occurs along $B_1-B_0-B_2$; $4$ along the connected branches $B_5-B_1-B_0-B_3$; $5$ along $B_2-B_0-B_3$; $1$ along $B_1-B_5$; and $6$ along $B_3-B_4$. Each of the other variables occurs in just one bag. This is therefore a valid tree decomposition of width $3-1=2$.

Conversely, any of the original three-variable constraint scopes forms a clique of size three in the primal graph. Such a clique must be contained in one bag of every tree decomposition, forcing width at least two. The upper and lower bounds agree:

Choose the distinct values of $(X_1,X_2,X_4)$ and call them $(a,b,c)$. There are $3!=6$ choices. Constraint (5), on $(X_1,X_4,X_9)$, immediately forces $X_9=b$.

Constraints (2) and (3) require $X_5\ne X_2=b$ and $X_5\ne X_4=c$, respectively. Since the constraint domain has exactly three values, $X_5=a$. Constraint (2) now forces $X_3=c$, and constraint (3) forces $X_6=b$. Finally, constraint (4) permits $(X_7,X_8)=(a,c)$ or $(c,a)$.

Every choice just described satisfies all five all-different constraints, and the forced-value argument shows there are no other possibilities. HenceIn the order $(X_1,\dots ,X_9)$, the two forms arewhere $(a,b,c)$ ranges over the six permutations of $(0,1,2)$.

True in some cases and false in others. Equality of the constraint domain size and treewidth does not decide satisfiability.

For an unsatisfiable example, let $D=\{0,1\}$ and impose the three binary all-different constraints $X_1\ne X_2$, $X_2\ne X_3$, and $X_3\ne X_1$. The primal graph is a triangle, with treewidth two. It needs three different values, so no solution exists despite $|D|=\mathrm{tw}(P)=2$.

For a satisfiable example, take four variables with the same constraint domain and constraintsIts primal graph is a four-cycle of treewidth two: bags $\{1,2,3\}$ and $\{1,3,4\}$ give width two, while width one would require a forest. The assignment $(0,1,0,1)$ satisfies all constraints.

True in some cases and false in others: the two numerical inequalities do not guarantee a solution.

For an unsatisfiable example satisfying both inequalities, take six variables, a constraint domain with five values, and $k=4$, $m=3$, with all-different constraints onAny pair of the six variables occurs together in at least one of these scopes: view the variables as the three pairs $\{1,2\},\{3,4\},\{5,6\}$, and each scope as the union of two pairs. All six values must therefore be distinct. This is impossible with five available values, even though $5>4$ and $5>3$.

For a satisfiable example with the same $k,m,|D|$, take three disjoint groups of four variables and impose one all-different constraint on each group. Assign values $1,2,3,4$ separately in every group. All three constraints hold with $D=\{1,2,3,4,5\}$.These examples concern the intended cases in which the antecedent holds; they do not rely on vacuous truth of an implication.

Always true. An all-different constraint of arity $k$ requires $k$ distinct values. If $|D|<k$, the pigeonhole principle makes even one such constraint impossible. Since $m>0$, at least one is present, and consequently

Always true. Replace every all-different constraint by the pairwise inequalities on its scope. Then solutions are precisely the proper graph colourings of the primal graph using values from $D$ as colours. Put $t=\mathrm{tw}(P)$.

A graph of treewidth $t$ has a proper graph colouring with at most $t+1$ colours. Here is a constructive proof. In a width-$t$ tree decomposition, remove any leaf bag contained in its neighbor. If more than one bag remains, a leaf bag has a vertex absent from its neighbor. The running-intersection property means that vertex occurs only in the leaf bag, so every neighbor of the vertex belongs to that bag. It has at most $t$ neighbors. If only one bag remains, it has at most $t+1$ vertices and the same degree bound holds.

Remove the chosen vertex and repeat; deleting vertices cannot increase the width of the restricted tree decomposition. Now colour in reverse removal order. At most $t$ already coloured neighbors forbid colours, so one of $t+1$ colours is always available. Since the integer inequality $|D|>t$ gives $|D|\ge t+1$, this produces a satisfying assignment:The common unrestricted constraint domain and the exclusively all-different constraints are essential: arbitrary constraint relations do not reduce to graph colouring in this way.

Always true for a nonempty finite constraint domain, as conventionally assumed. Write $q=|D|$ and identify its values with $\{0,\dots ,q-1\}$. For each satisfying assignment $(x_1,\dots ,x_n)$, simultaneously replace every value byThis permutation of the common constraint domain preserves every equality and inequality, hence every all-different constraint. The resulting $q$ assignments are distinct: equality of even one coordinate before and after a shift forces $a=0(\mathrm{mod}q)$. There is at least one variable, since $m>0$ and $k\ge 2$.

The cyclic group of shifts therefore partitions the solution set into disjoint orbits of size $q$. It follows thatThe conclusion includes an unsatisfiable instance, whose solution count is zero. Full permutation group orbits need not have size $q!$, because unused values can be permuted without changing an assignment; the cyclic-shift argument avoids that mistake.

If an empty constraint domain is permitted, there are zero assignments here, but the wording “divisible by $|D|$” then asks about divisibility by zero, which is ordinarily left undefined. The asserted divisibility uses the standard nonempty-domain convention, and the no-solution conclusion still holds for that degenerate input.

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.

Write $F\subseteq \{1,\dots ,N{\}}^2$ for the prescribed occupied cells, with $k=|F|$. The source’s lowercase $n$ in its coordinate bound is read as the stated board size $N$. If two prescribed queens already attack each other, no completion exists. Each model below correctly expresses that impossibility as well as consistent inputs.

Model 1: one Boolean variable per cell. Let $B_{rc}\in \{0,1\}$ indicate occupancy. Requireand impose $B_{rc}+B_{st}\le 1$ for every two distinct cells sharing a row, a column or a diagonal. Equivalently, impose exactly one queen in each row and column and at most one on each diagonal. Explicit diagonal constraints areTogether with the total-count constraint and the attacking-pair binary constraints, these force exactly the intended boards. The count and diagonal-sum constraints are legitimate many-variable constraints; this model need not be binary.

Model 2: one variable per labeled queen. Let $Q_i=(R_i,C_i)\in \{1,\dots ,N{\}}^2$ for $1\le i\le N$. Enumerate $F=\{f_1,\dots ,f_k\}$ and restrict $D_i=\{f_i\}$ for $i\le k$. For every $i<j$, impose the binary constraintThere are exactly $N$ variables and distinct rows, so these are $N$ distinct queens. Labeling the prescribed queens does not lose a board completion: the queens are physically indistinguishable, and any completion can be labeled to give the prescribed ones those indices. It does create redundant assignments for the remaining labels.

Model 3: one variable per row. Let $C_r\in \{1,\dots ,N\}$ be the queen’s column in row $r$. For every $r<s$, requireand impose $C_r=c$ for every $(r,c)\in F$. These restrictions give $N$ queens, one per row; the all-different constraint on the columns gives one per column. For $N$ nonattacking queens on $N$ rows, exactly one per row is forced by the pigeonhole principle, so no solutions are lost. Inconsistent prescribed positions in a single row give incompatible unary restrictions. All three are exact constraint satisfaction problem encodings of the queens completion problem.

The graph with one vertex per variable and an edge between distinct variables occurring in a common constraint scope. Each hypergraph edge of the constraint hypergraph becomes a clique. A constraint satisfaction problem consisting only of all-different constraints on a common constraint domain is exactly a proper graph colouring problem on this primal graph.