TAOCP 7.2.2.1 Exercise 232

Section 7.2.2.1: Dancing Links

Exercise 232. [20] The costs supplied to Algorithm X$^8$ must be integers. Does it matter that $d(i,j)$ in the 16 queens problem of Fig. 74 is never an integer. Is it OK to use $\lfloor 8d(i,j) \rfloor$ instead of $8d(i,j)$ for the cost of placing a queen in cell $(i,j)$?

Verified: yes
Solve time: 1m43s

---

Solution

Let a placement of 16 queens be an option set $S$ consisting of 16 chosen cells $(i,j)$, and let its cost under Algorithm $X^8$ be

$w(S)=\sum_{(i,j)\in S} 8d(i,j).$

Since multiplication by the positive constant $8$ does not change ordering, minimizing $w(S)$ is equivalent to minimizing

$W(S)=\sum_{(i,j)\in S} d(i,j).$

Thus the non-integrality of $d(i,j)$ alone is irrelevant to correctness, because Algorithm $X^8$ depends only on comparisons of total option costs, not on any arithmetic property requiring integrality of the intermediate values.

Now replace each term by

$\tilde{d}(i,j)=\lfloor 8d(i,j)\rfloor,$

and define the modified cost

$\tilde{w}(S)=\sum_{(i,j)\in S}\lfloor 8d(i,j)\rfloor.$

For each term,

$8d(i,j)-1 < \lfloor 8d(i,j)\rfloor \le 8d(i,j),$

so for every solution $S$ with 16 queens,

$w(S)-16 < \tilde{w}(S) \le w(S).$

Consider two feasible placements $S$ and $T$. Their true cost difference is

$w(S)-w(T),$

while the transformed difference satisfies

$\tilde{w}(S)-\tilde{w}(T)=\bigl(w(S)-w(T)\bigr)-\varepsilon,$

where

$\varepsilon=\sum_{(i,j)\in S}\bigl(8d(i,j)-\lfloor 8d(i,j)\rfloor\bigr)-\sum_{(i,j)\in T}\bigl(8d(i,j)-\lfloor 8d(i,j)\rfloor\bigr).$

Each fractional error term lies in $[0,1)$, so

$|\varepsilon|<16.$

No structural constraint of the 16-queens exact cover formulation forces $w(S)-w(T)$ to be separated by at least $16$ for all distinct feasible solutions. Therefore a pair of solutions can satisfy

$w(S)>w(T) \quad\text{while}\quad \tilde{w}(S)<\tilde{w}(T),$

because a real advantage smaller than $16$ can be reversed by accumulated flooring error.

This shows that replacing $8d(i,j)$ by $\lfloor 8d(i,j)\rfloor$ does not preserve the ordering of feasible solutions in general, hence it does not preserve correctness of a minimization procedure that depends on exact cost comparisons.

The integrality requirement in Algorithm $X^8$ is therefore not about the irrationality of $d(i,j)$, but about avoiding discretization that can change relative costs.

Scaling by a positive constant such as $8$ is harmless, since it preserves all comparisons:

$w(S)<w(T);\Longleftrightarrow;8w(S)<8w(T).$

Flooring destroys this equivalence, so it is not acceptable.

$\boxed{\text{No, flooring }8d(i,j)\text{ can change the optimal solution; only positive scaling is safe.}}$