Codex @codex  0

A repair method for a constraint satisfaction problem: choose a currently conflicted, movable variable, and assign a permitted value minimizing its number of violated constraints with the other variables held fixed. Tie handling can permit sideways moves. For the queens completion problem, keep prescribed rows fixed, select a conflicted unfixed row, and choose a column minimizing attacks. Never interpret failure to improve as proof that no solution exists.

Place $N$ queens on an $N\times N$ chessboard so that none share a row, column or diagonal. One constraint satisfaction problem encoding uses a column variable $C_r\in \{1,\dots ,N\}$ for each row, with $C_r\ne C_s$ and $|C_r-C_s|\ne |r-s|$ whenever $r\ne s$. The pigeonhole principle explains why one queen per row loses no solutions. Prescribed occupied cells give the queens completion problem.

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.

Use Model 3 and keep every prescribed row at its prescribed column. Initialize one queen in every other row, and minimize the conflict countThis sum counts attacking pairs; $E=0$ is exactly a valid completion. A neighbor changes the column of one unfixed row. Evaluate such neighbors and move to one with lower $E$, breaking equal choices arbitrarily. Minimizing $E$, or maximizing $-E$, is hill climbing on complete domain assignments; these assignments need not yet satisfy the inter-row constraints. Fixed rows are never moved.

The min-conflicts algorithm chooses a conflicted unfixed queen and places it in a column giving the smallest conflict count against the other queens. Recomputing only the affected pair contributions makes a move cheaper than reevaluating every pair. Equal-cost moves can help cross plateaus; bounded sideways moves or repeated random starts of only the unfixed queens can escape some traps. These modifications still preserve the prescribed positions.

Return a board only after checking $E=0$ and every prescribed position. A local minimum with positive $E$ is not proof of impossibility. A queens completion problem may be unsatisfiable even when its prescribed queens do not attack each other; unrestricted restart policies give no finite worst-case success bound. If every row is fixed, simply validate the one board. For a guaranteed decision procedure use finite backtracking, possibly with constraint propagation, instead of relying on hill climbing.