TAOCP 7.2.1.1 Exercise 7
Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73).
Section 7.2.1.1: Generating All n-Tuples
Exercise 7. [20] [20] Figure 30(b) shows the Gray binary code for a disk that is divided into 16 sectors. What would be a good Gray-like code to use if the number of sectors were 12 or 60 (for hours or minutes on a clock), or 360 (for degrees in a circle)?
Verified: no
Solve time: 5m29s
Solution
Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73). Any valid coloring induces $24$ equivalent assignments obtained by permuting the four color names, since every permutation $\pi \in S_4$ applied uniformly to all vertex colors preserves adjacency constraints.
To remove this redundancy, it suffices to eliminate all but one representative from each orbit under the action of $S_4$ on colorings. A direct way is to impose a canonical ordering on the use of colors based on first occurrence along a fixed enumeration of the vertices.
Let the vertices be ordered as $v_1,\dots,v_n$. Introduce additional constraints that enforce the following rule: when scanning vertices in increasing index order, the first vertex $v_1$ receives color $0$, and whenever a new color appears for the first time, it must be the least unused color.
Formally, define for each $i$ the predicate that records whether a color has appeared earlier:
$$ U_k(i) \equiv \bigvee_{j<i} (x_j = k), \quad k \in {0,1,2,3}. $$
Then enforce the canonical constraints:
$$ x_1 = 0, $$
and for each $i>1$, if $x_i = k$, then either $k$ is already used among $x_1,\dots,x_{i-1}$ or $k$ equals the least index not yet used. This is enforced by requiring
$$ x_i \le 1 + \sum_{k=0}^{3} U_k(i), $$
together with the implication that if a color $k$ has not appeared yet, no larger color can appear for the first time before it.
Equivalently, one may impose the sequential normalization rule: the first time a new color is introduced along the ordering $v_1,\dots,v_n$, it must be $0$, then $1$, then $2$, then $3$, with no gaps. This forces a unique renaming of every equivalence class of size $24$.
In BDD terms, this is implemented by augmenting $\text{COLOR}$ with a small deterministic automaton tracking which colors have appeared so far and rejecting any assignment that introduces a new color out of order. The resulting restricted function $\widehat{\text{COLOR}}$ satisfies that each valid coloring corresponds to exactly one satisfying assignment, eliminating all $4!$ permutations.
This completes the construction of a symmetry-breaking formulation removing the redundancy. ∎