TAOCP 7.2.2.1 Exercise 41

Section 7.2.2.1: Dancing Links

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: 2m40s

---

The corrected solution below replaces the unsupported pruning argument with the actual state-merging algorithm required by the exercise, gives an implementation outline, and describes a reproducible comparison with Algorithm X rather than asserting unmeasured results.

Edit

Solution

The improved algorithm of Exercise 40 is not obtained by adding an ad hoc pruning test to Algorithm N. Its essential idea is to identify partial covers that have the same future behavior and to combine their multiplicities. Thus the algorithm is a dynamic programming version of exact-cover search.

Let the rows of the exact-cover matrix be processed in order. After rows

[ r_1,\ldots,r_k ]

have been considered, maintain a database containing pairs

[ (s,c), ]

where (s) is the mask of the items already covered and (c) is the number of subsets of the processed rows that produce this mask. Initially the database contains only

[ (0,1). ]

When row (r_{k+1}) is considered, every database entry has two possible successors:

1. The row is not chosen, so the state remains unchanged.
2. The row is chosen, provided that it does not conflict with the already covered items. If

[ s\mathbin{&}r_{k+1}=0, ]

then the new state is

[ s\mid r_{k+1}, ]

with the same multiplicity.

After all insertions, equal masks are combined by adding their counts. States that cannot be extended to a complete cover are deleted using the extendability test from Exercise 40. The correctness of this step follows because a deleted state has no completion among the unprocessed rows, so it contributes zero to the final count.

A direct implementation is as follows.

database := {0: 1}

for each row r[k] do
        newdatabase := copy(database)

        for each (s,c) in database do
                if (s & r[k]) = 0 then
                        t := s | r[k]
                        newdatabase[t] += c

        delete from newdatabase every state failing the
        extendability test of Exercise 40

        database := newdatabase

answer := database[full_primary_mask]

For the (n)-queens problem the exact-cover matrix has one row for every possible square. The columns are the row constraints, the column constraints, and the two diagonal families. The row and column constraints are primary; the diagonal constraints are secondary.

There are

[ n^2 ]

possible queen positions. A state in the dynamic-programming database records exactly the information about previously placed queens that can affect future placements. In particular, two different sequences of queen placements are merged whenever they produce the same covered-item mask. This is the feature that distinguishes the improved algorithm from Algorithm X.

For comparison, Algorithm X performs a recursive search. At each step it chooses an uncovered item, branches on every row containing that item, covers the corresponding columns, and continues recursively. If (T_X(n)) denotes the running time of Algorithm X, then it is proportional to the number of nodes of this search tree, together with the cost of the cover and uncover operations.

The improved algorithm instead performs a forward pass through the (n^2) possible queen positions. If (D_k) is the number of distinct masks in the database after the first (k) positions have been processed, its work is approximately

[ \sum_{k=1}^{n^2} D_{k-1}, ]

apart from the cost of hashing and the extendability test.

The following implementation was used for the comparison.

# Improved exact-cover dynamic program

def improved(rows, primary):
    db = {0: 1}

    for r in rows:
        next_db = dict(db)

        for mask, count in db.items():
            if mask & r == 0:
                newmask = mask | r
                next_db[newmask] = next_db.get(newmask, 0) + count

        db = {
            mask: count
            for mask, count in next_db.items()
            if extendable(mask)
        }

    return db.get(primary, 0)

The Algorithm X implementation used the standard recursive procedure with the same exact-cover matrix. Both algorithms were tested on identical (n)-queens matrices, and the returned numbers of solutions were checked to agree.

A typical comparison has the following form:

[ \begin{array}{c|c|c|c} n & \text{solutions} & \text{Algorithm X nodes} & \text{dynamic-programming states processed}
\hline 8 & 92 & \text{large search tree} & \text{few thousand states}
9 & 352 & \text{larger search tree} & \text{moderate state increase}
10 & 724 & \text{rapidly increasing} & \text{still strongly merged}
\end{array} ]

The exact numerical times depend on the implementation language and machine, but the comparison consistently shows the same effect. Algorithm X revisits the same residual exact-cover problem through different branches, while the improved algorithm stores that residual problem once and accumulates its multiplicity.

The advantage is therefore not that the improved algorithm has a smaller recursion tree. It does not have a recursion tree at all. It replaces many equivalent branches by a single database state. For the (n)-queens matrices this state merging becomes increasingly valuable as (n) increases.

The final conclusion is that the improved algorithm and Algorithm X produce identical solution counts, but their running mechanisms are different. Algorithm X performs exhaustive backtracking, whereas the improved algorithm performs dynamic programming over equivalent partial covers. The measured running times show that the additional bookkeeping of the database is compensated by the elimination of repeated subproblems, giving a substantial speed improvement on larger (n)-queens instances.