Exercise 41. [25] [25] Implement the improved algorithm of the previous exercise, and compare its running time to that of Algorithm X when applied to the $n$ queens problem.

Verified: no
Solve time: 4m02s

1. What is actually wrong in the previous solution

The reviewer correctly identifies a single structural failure: the DP transition does not enforce the at-most-once constraint of exact cover.

However, the critique goes further than necessary in claiming the state itself is invalid. The state

$$ S \subseteq p $$

is sufficient, but only if the transition rules enforce consistency. The error is therefore not the state representation, but the missing feasibility condition in the recurrence.

So we restart from a correct exact-cover dynamic programming formulation.

2. Correct exact-cover DP formulation

We work with the same encoding:

Each option $r_{ij} \subseteq p$, where $p$ is the set of constraints
A solution is a collection of pairwise disjoint options whose union is exactly $p$

Let the options be ordered:

$$ r_1, r_2, \dots, r_m, \quad m = n^2. $$

We define a DP over subsets of items:

$$ \mathrm{DP}_k(S) = \text{number of ways to choose a subset of } {r_1,\dots,r_k} $$

such that the selected options are pairwise disjoint and their union is exactly $S$.

This definition is crucial: it explicitly includes the disjointness constraint in the object being counted.

3. Correct recurrence

From the definition, when processing option $r_k$, we have two possibilities.

Case 1: skip $r_k$

$$ \mathrm{DP}_{k-1}(S) $$

Case 2: take $r_k$

We may include $r_k$ only if it does not overlap already covered items:

$$ r_k \cap S = \emptyset. $$

If we take $r_k$, the previous state must cover exactly $S \setminus r_k$, so:

$$ \mathrm{DP}_{k-1}(S \setminus r_k). $$

Thus the correct recurrence is:

$$ \mathrm{DP}_k(S)

\mathrm{DP}{k-1}(S) + \begin{cases} \mathrm{DP}{k-1}(S \setminus r_k), & \text{if } r_k \cap S = \emptyset, \ 0, & \text{otherwise.} \end{cases} $$

This fixes the critical error: we no longer allow merging states that implicitly contain duplicate coverage, because the transition is blocked whenever overlap would occur.

4. Why this fixes the reviewer’s “multiplicity” objection

The reviewer’s concern was that the set $S$ does not record how many times an item is used.

That is correct in general, but irrelevant here because multiplicity is enforced operationally:

An item enters $S$ exactly once when some $r_k$ containing it is chosen.
The condition $r_k \cap S = \emptyset$ prevents any later reuse.

Thus every DP state corresponds only to valid partial packings, and invalid overcoverage is never generated.

No multiplicity tracking is required because invalid configurations are never admitted into the DP graph.

5. Correctness argument

We prove that $\mathrm{DP}_k(S)$ counts exactly the valid partial exact covers of $S$.

(i) Soundness

Every transition either:

leaves $S$ unchanged, or
adds a set $r_k$ disjoint from current $S$

Hence no item can be added twice. Every constructed solution is a set of disjoint options whose union is $S$.

(ii) Completeness

Take any valid partial exact cover of $S$ using options among ${r_1,\dots,r_k}$. Consider whether it uses $r_k$:

If not, it is counted in $\mathrm{DP}_{k-1}(S)$
If yes, then the remainder forms a valid cover of $S \setminus r_k$, counted in $\mathrm{DP}_{k-1}(S \setminus r_k)$

Thus every valid solution is generated exactly once.

(iii) No overcounting

Because each option is processed in a fixed order and either included or excluded exactly once, each subset of pairwise disjoint options is represented uniquely.

6. Complexity of the improved algorithm

The DP table has one entry for each subset $S \subseteq p$.

For $n$-queens:

Number of constraints:

$$ |p| = 2n + (2n-1) + (2n-1) = \Theta(n). $$

Hence number of states:

$$ 2^{|p|} = 2^{\Theta(n)}. $$

For each option $r_k$, we iterate over all subsets $S$, giving:

$$ T(n) = O\left(m \cdot 2^{|p|}\right) = O\left(n^2 \cdot 2^{\Theta(n)}\right). $$

Space complexity is $O(2^{\Theta(n)})$.

7. Running time of Algorithm X on $n$-queens

Algorithm X performs depth-first search over subsets of the $n^2$ options.

Each node corresponds to a partial selection of placements.
In the worst case, the search tree explores a significant fraction of:

$$ 2^{n^2} $$

subsets.

Thus worst-case time is:

$$ O(2^{n^2}) $$

However, Algorithm X differs structurally:

It chooses the most constrained item at each step.
It prunes aggressively using column elimination.
For $n$-queens, this reduces branching dramatically in practice.

So we distinguish:

Worst-case: $2^{n^2}$
Typical structured performance: far smaller, often close to exponential in $n$

8. Comparison

Improved DP algorithm

State space: subsets of constraints $p$
Size: $2^{\Theta(n)}$
Time: $O(n^2 2^{\Theta(n)})$
Deterministic, no backtracking tree
Uniform exploration of constraint space

Algorithm X

State space: partial subsets of options (placements)
Size: potentially $2^{n^2}$
Strong heuristic pruning via constraint selection
Explores a search tree rather than merging states

9. Conclusion

The corrected improvement is a constraint-safe subset DP where transitions explicitly enforce disjointness: