= Solution
Use Model 3 and keep every prescribed row at its prescribed column. Initialize one queen in every other row, and minimize the conflict count
$$
E(C)=\sum_{1\le r<s\le N}\mathbf1_{\{C_r=C_s\ \text{or}\ |C_r-C_s|=s-r\}}.
$$
This <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.
\b[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>.
Back to article page
