Section 7.2.2.1: Dancing Links

Exercise 38. [M25] $[M25]$ Devise an efficient way to compute the sequence $\langle g_n \rangle$ of exercise 37.

Verified: yes
Solve time: 2m31s

---

Let $g_n$ be defined as in exercise 37: a greedy placement of nonattacking queens on the infinite board, with $g_n$ the column of the queen in row $n$.

We restate the constraints in the standard form:

$$ g_i \ne g_j,\qquad g_i - i \ne g_j - j,\qquad g_i + i \ne g_j + j \quad (i \ne j). $$

Correct formulation of forbidden values

Assume $g_1,\dots,g_n$ are already chosen. A candidate $k$ for $g_{n+1}$ is admissible iff it avoids all conflicts with previous queens.

Define

$$ C_n = {g_1,\dots,g_n}, \quad D_n^- = {g_i - i : 1 \le i \le n}, \quad D_n^+ = {g_i + i : 1 \le i \le n}. $$

Then $k$ is forbidden exactly in the following three cases:

1. Column conflict:

$$ k \in C_n. $$

1. “$-$” diagonal conflict:

If $g_i - i = d \in D_n^-$, then

$$ k - (n+1) = d ;;\Longleftrightarrow;; k = d + (n+1). $$

1. “$+$” diagonal conflict:

If $g_i + i = d \in D_n^+$, then

$$ k + (n+1) = d ;;\Longleftrightarrow;; k = d - (n+1). $$

Hence the forbidden set for $k$ is

$$ F_{n+1}

C_n ;\cup; {d + (n+1) : d \in D_n^-} ;\cup; {d - (n+1) : d \in D_n^+}. $$

Each element of $D_n^-$ and $D_n^+$ contributes at most one integer, so

$$ |F_{n+1}| \le n + n + n = 3n. $$

Existence of an admissible choice

Since $F_{n+1}$ contains at most $3n$ integers, consider the initial segment

$$ {1,2,\dots,3n+1}. $$

This set has $3n+1$ elements, so at least one integer $k \le 3n+1$ is not in $F_{n+1}$. Hence the greedy choice

$$ g_{n+1} = \min { k \ge 1 : k \notin F_{n+1} } $$

is well defined.

Efficient computation

The bound $g_{n+1} \le 3n+1$ yields a direct implementation strategy.

Maintain three boolean structures:

• $C[k]$: whether column $k$ is occupied,
• $D^-[s]$: whether a diagonal value $s = g_i - i$ is occupied,
• $D^+[t]$: whether a diagonal value $t = g_i + i$ is occupied.

At step $n+1$, to test a candidate $k$, we check:

$$ C[k], \quad D^-[k-(n+1)], \quad D^+[k+(n+1)]. $$

Then scan $k = 1,2,\dots,3n+1$ until an admissible value is found. By the previous argument, success is guaranteed within this range.

After choosing $g_{n+1}$, update:

$$ C[g_{n+1}] \leftarrow 1,\quad D^-[g_{n+1}-(n+1)] \leftarrow 1,\quad D^+[g_{n+1}+(n+1)] \leftarrow 1. $$

Correctness and efficiency summary

• The diagonal constraints are now derived correctly from the definitions $g_i - i$ and $g_i + i$.
• The forbidden set is shown to have size at most $3n$, ensuring the existence of a valid $g_{n+1}$.
• The bound $g_{n+1} \le 3n+1$ gives a finite search region, making each step $O(n)$ time with constant-time membership tests, and total cost $O(n^2)$ for computing $g_1,\dots,g_N$.

This completes the corrected construction. ∎