Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 3 / d / Solution

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.