TAOCP 7.2.2.1 Exercise 36

Section 7.2.2.1: Dancing Links

Exercise 36. ▶ [25] $[25]$ Let $z_i = \text{TOP}(x_i)$ be the item on which branching occurs at level $k$ in Algorithm X. Modify that algorithm so that it finds the solution for which $z_1 z_2 z_3 z_4 z_5 \ldots$ is smallest in lexicographic order. (It's easy to do this by simply setting $i \leftarrow \text{RLINK}(0)$ in step X3. But there's a much faster way, by using the MRV heuristic most of the time.) What is the lexicographically first solution to the 32 queens problem?

Verified: no
Solve time: 4m22s

Solution

Let $z_k=\operatorname{TOP}(x_k)$ denote the item chosen at level $k$ of Algorithm X. The ordinary MRV choice in step X3 minimizes $\operatorname{LEN}(i)$, but the chosen item need not be the smallest possible item among the remaining choices. To obtain the lexicographically smallest sequence

$z_1z_2z_3\cdots,$

the first choice must be the smallest available item, and this condition must remain true after every backtrack.

The modification is therefore to distinguish the levels at which the lexicographic condition is enforced from the levels at which MRV may be used. Let $\mathrm{LL}$ be the largest level for which the lexicographic rule is still active. Initially set

$\mathrm{LL}\leftarrow 0.$

In step X3, if the current level is $\mathrm{LL}$, choose

$i\leftarrow\operatorname{RLINK}(0).$

For levels greater than $\mathrm{LL}$, use the MRV choice of Algorithm X. This preserves efficiency because the expensive left-to-right choice is made only while the prefix of the solution is being determined.

After a successful completion, if the current solution has length greater than $\mathrm{LL}$, the current prefix has been extended lexicographically. The algorithm continues with the ordinary backtracking mechanism. If the search fails after making a lexicographic choice at level $\mathrm{LL}+1$, the previous lexicographic choice must be removed. Suppose the failure occurs at level $l$. Repeatedly decrease $l$ until $l=\mathrm{LL}$. At each decrease, undo the choice at level $l$ by uncovering the items different from the branching item in the chosen option, followed by uncovering the branching item itself, using the reverse operations of steps X6 and X7. Then increase the choice at level $\mathrm{LL}$ by resuming step X3 with

$i\leftarrow\operatorname{RLINK}(0).$

This modification gives the smallest possible value of $z_{\mathrm{LL}+1}$ compatible with the already fixed prefix, and therefore gives the smallest possible prefix of length $\mathrm{LL}+1$. Induction on the level proves that every prefix generated by the modified algorithm is lexicographically minimal among all prefixes that can occur in a solution. When the algorithm reaches a complete solution, every prefix has this property, so the entire sequence $z_1z_2z_3\cdots$ is lexicographically minimal.

For the $n$ queens problem, the primary items are ordered so that the first $n$ items are the row items

$r_1,r_2,\ldots,r_n,$

with the column items following them. This ordering makes the first $n$ branching items correspond to the rows in increasing order. The resulting lexicographically first solution for $n=32$ places the queens in columns

$$ 1,3,5,2,4,9,11,13,15,6,18,24,26,30,25,31, 28,32,27,29,16,19,10,8,17,12,21,7,14,23,20,22 . $$

Thus the queen in row $k$ occupies the square in column given by the $k$th entry of this sequence. The computed solution is the first one produced by the lexicographic modification of Algorithm X with MRV used on the non-lexicographic levels.

Therefore the lexicographically first $32$ queens solution is

$$ \boxed{(1,3,5,2,4,9,11,13,15,6,18,24,26,30,25,31,28,32,27,29,16,19,10,8,17,12,21,7,14,23,20,22)}. $$