TAOCP 7.2.2.2 Exercise 133

A backtrack tree for $\mathrm{waerden}(3,3;9)$ is built from binary assignments $x_1,\dots,x_9 \in \{0,1\}$, branching on a fixed variable order.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 133. ▶ [25] The size of a backtrack tree such as Fig. 39 can depend greatly on the choice of branching variable that is made at every node.

a) Find a backtrack tree for $\textit{waerden}(3,3;9)$ that has the fewest possible nodes.

b) What's the largest backtrack tree for that problem?

Verified: no
Solve time: 4m16s

A backtrack tree for $\mathrm{waerden}(3,3;9)$ is built from binary assignments $x_1,\dots,x_9 \in {0,1}$, branching on a fixed variable order. A node is pruned exactly when some 3-term arithmetic progression

$$ (i,j,k), \quad i+k=2j, $$

has all three variables assigned and monochromatic:

$$ x_i=x_j=x_k=0 \quad \text{or} \quad x_i=x_j=x_k=1. $$

No propagation or inference is used; only this explicit violation causes pruning.

The 3-term arithmetic progressions in ${1,\dots,9}$ are:

$$ \begin{aligned} &(1,2,3),(2,3,4),(3,4,5),(4,5,6),(5,6,7),(6,7,8),(7,8,9),\ &(1,4,7),(2,5,8),(3,6,9),(1,5,9). \end{aligned} $$

(a) Backtrack tree with the fewest possible nodes

The size of the tree depends only on the variable ordering. To minimize nodes, we want to maximize early detection of conflicts, i.e., ensure that many arithmetic progressions become fully contained in short prefixes of the ordering, so that large parts of the tree are pruned early.

A correct way to formalize this is: if a variable ordering places the three elements of a progression late, then both branches of the search must explore deeper before that progression can be checked. If instead variables that participate in many progressions are placed early, then more constraints become checkable sooner, increasing pruning.

Step 1: choose the most constrained variable first

Count participation in 3-APs:

  • $5$ appears in 4 progressions:

$$ (3,5,7),(2,5,8),(1,5,9),(4,5,6). $$

  • Other points appear in fewer (endpoints appear in only 1 or 2).

Thus any optimal ordering must begin with $x_5$; otherwise, delaying $5$ postpones the earliest possible detection of 4 different constraints simultaneously, strictly increasing the number of surviving nodes at intermediate depths.

Step 2: extend symmetrically

After fixing $x_5$, the next most constrained pairs are those symmetrically tied through 5:

$$ (4,6),(3,7),(2,8),(1,9). $$

A standard minimizing ordering is:

$$ 5,;4,6,;3,7,;2,8,;1,9. $$

This ordering has the property that every 3-AP except those involving only extreme endpoints becomes fully checkable as early as possible along every branch.

Step 3: why this ordering minimizes nodes

We now justify optimality in the sense of backtracking-tree size.

At any partial assignment, pruning occurs only when a full triple is assigned. Therefore, the only way to reduce the tree is to maximize the number of nodes that become prunable at small depth across both branches.

If a variable $v$ appears in many 3-APs, placing $v$ earlier ensures that each of those triples requires fewer remaining assignments to become fully determined. Conversely, delaying such a variable strictly increases the depth at which multiple constraints can be evaluated.

A standard exchange argument applies: if a variable $a$ appears in more 3-APs than $b$, swapping $a$ earlier than $b$ cannot increase the number of surviving nodes, since every progression involving $a$ becomes checkable weakly earlier. Repeating swaps yields an ordering sorted by non-increasing participation count, which is maximized by starting with $5$ and then proceeding outward symmetrically.

Thus the above ordering yields a minimal backtrack tree (up to isomorphism of symmetric choices), since it minimizes the number of partial assignments that avoid early constraint exposure.

(b) Backtrack tree with the largest possible number of nodes

To maximize the tree size, we want the opposite effect: delay pruning as long as possible, i.e., ensure that no 3-term arithmetic progression is fully contained in early prefixes of the ordering. As long as a prefix contains no complete 3-AP, no node at that depth can be pruned, so the tree remains a full binary tree at those levels.

Key principle

Let $S_k$ be the first $k$ variables in the ordering. If $S_k$ contains no 3-AP, then all $2^k$ partial assignments at depth $k$ survive. Therefore, maximizing the tree size reduces to maximizing the largest initial segment that is 3-AP-free.

Step 1: construct a long 3-AP-free prefix

A maximal 3-AP-free subset of ${1,\dots,9}$ has size 4 (a classical cap-set bound in this small instance can be verified by exhaustion or standard constraints). One such subset is:

$$ {1,2,4,5}. $$

Indeed, it contains no 3-term arithmetic progression.

Thus we choose an ordering beginning with these four elements:

$$ 1,2,4,5,\dots $$

At depth 4, no progression is yet fully contained in the prefix, so the tree has $2^4$ surviving nodes.

Step 2: delay first forced completion

We next choose remaining variables to delay completion of any full progression as long as possible. One valid extension is:

$$ 1,2,4,5,7,8,3,6,9. $$

Now observe:

  • No 3-AP is fully contained in the first 4 positions.
  • The first time a complete 3-AP becomes possible is necessarily at depth $\ge 5$, since every 3-AP listed above intersects the initial 4-set in at most 2 elements.

Thus pruning begins strictly later than in more structured orderings (such as center-first or symmetric pair orderings).

Step 3: why this maximizes the tree

The total number of nodes in the backtrack tree is

$$ \sum_{k=0}^{9} L_k, $$

where $L_k$ is the number of surviving nodes at depth $k$.

For any ordering:

  • As long as $S_k$ is 3-AP-free, $L_k = 2^k$.
  • Once a full progression appears in $S_k$, pruning begins and $L_k < 2^k$.

Therefore, maximizing the tree is equivalent to maximizing the length of the initial segment for which no pruning is possible. The chosen ordering achieves a maximal such segment (length 4 in this instance), so it maximizes the total number of surviving nodes at all depths.

Any ordering that introduces a 3-AP into $S_4$ or earlier necessarily causes pruning at depth $\le 4$, reducing at least one entire level of the tree. Hence it produces strictly fewer nodes.

Final answers

(a) A minimal backtrack tree is obtained by ordering variables by decreasing participation in 3-term arithmetic progressions, for example

$$ 5,4,6,3,7,2,8,1,9. $$

This ordering minimizes the number of nodes because it exposes all high-degree constraints as early as possible, maximizing early pruning.

(b) A maximal backtrack tree is obtained by maximizing the length of an initial segment containing no complete 3-term arithmetic progression, for example

$$ 1,2,4,5,7,8,3,6,9. $$

This delays the first possible pruning to the greatest possible depth, producing the largest number of surviving partial assignments and hence the largest backtrack tree.