TAOCP 7.2.2.1 Exercise 76
The key issue in the previous solution is that part (b) attempted to enforce commutativity by informally “merging choices,” without giving a valid exact-cover encoding.
Section 7.2.2.1: Dancing Links
Exercise 76. [21] [21] Modify the exact cover problem of exercise 75(d) in order to find the multiplication tables of (a) all idempotent gropes, gropes such that $x \circ x = x$ for all $x$; (b) all commutative gropes, gropes such that $x \circ y = y \circ x$ for all $x$ and $y$; (c) all gropes with the identity element $0$, gropes such that $0 \circ x = 0 = x \circ 0$ for all $x$.
Verified: yes
Solve time: 4m30s
The key issue in the previous solution is that part (b) attempted to enforce commutativity by informally “merging choices,” without giving a valid exact-cover encoding. In exact cover, dependencies must be represented by the structure of the item–option incidence matrix itself. We now repair the construction from first principles.
(a) Idempotent gropes: $x \circ x = x$
Start from the exact cover formulation of Exercise 75(d), where each ordered pair $(x,y)$ has options $O(x,y,z)$ selecting the value $z \in G$, and the constraints ensure that exactly one value is chosen per cell and that the resulting table satisfies the grope axioms encoded in 75(d).
To enforce idempotence, restrict the option family for diagonal cells:
$$ \forall x \in G,\quad \text{retain only } O(x,x,x). $$
All other options $O(x,x,z)$ for $z \neq x$ are deleted.
No other part of the instance is modified.
Correctness follows immediately. Every feasible exact cover must select $O(x,x,x)$, so $x \circ x = x$. Conversely, any idempotent multiplication table already assigns $x$ to $(x,x)$, so it induces a valid cover of the restricted instance.
(b) Commutative gropes: $x \circ y = y \circ x$
The previous solution was incorrect because it tried to identify independent choices. Instead, we rebuild the exact-cover instance so that symmetry is enforced structurally.
Construction
We replace the encoding of ordered pairs by a commutativity-aware option system.
For each unordered pair ${x,y}$ with $x \neq y$ and each $z \in G$, introduce a single option
$$ O_c({x,y},z). $$
This option simultaneously assigns both products:
$$ x \circ y = z \quad \text{and} \quad y \circ x = z. $$
Formally, its item set is defined as the union of the items that, in the original 75(d) encoding, were used by $O(x,y,z)$ and $O(y,x,z)$, except that the two cell-assignment items are now both included in the same option.
For diagonal pairs $(x,x)$, we keep the original options $O(x,x,z)$ (or already apply part (a) if desired), since symmetry is trivial there.
Why this is a valid exact cover modification
This is not a “merging of independent choices” inside a fixed instance. It is a new exact-cover instance whose option family is explicitly redesigned. Exact cover allows arbitrary redefinition of the option sets, provided the items are fixed within the new instance.
The key point is that we replace two independent rows in the incidence matrix:
$$ O(x,y,z), \quad O(y,x,z), $$
with a single row whose incidence pattern enforces both assignments simultaneously.
No constraint from 75(d) is violated, because those constraints depend only on which items are covered, and both original contributions are preserved in the union defining $O_c({x,y},z)$.
Correctness
If a solution is chosen, then for each unordered pair ${x,y}$, exactly one option $O_c({x,y},z)$ is selected. By construction, this assigns the same value $z$ to both $(x,y)$ and $(y,x)$, hence the resulting operation is commutative.
Conversely, given any commutative grope, each unordered pair ${x,y}$ has a well-defined value $z = x \circ y = y \circ x$, so exactly one option $O_c({x,y},z)$ is chosen, producing a valid exact cover.
Thus solutions are in bijection with commutative gropes.
(c) Identity element $0$: $0 \circ x = 0 = x \circ 0$
We restrict the option sets for all cells involving $0$.
For every $x \in G$, retain only:
$$ O(0,x,0), \quad O(x,0,0). $$
All other options in these cells are removed.
Correctness justification
We must verify that this restriction does not destroy the exact cover property.
In the original encoding of 75(d), every cell $(0,x)$ and $(x,0)$ is covered by exactly one option $O(0,x,z)$ or $O(x,0,z)$ for some $z$. After restriction, each such cell still has at least one available option, namely the one with $z=0$, so every required cell-item remains coverable.
All other constraints from 75(d) remain unchanged, and the restricted options are still valid rows in the incidence matrix. Hence the instance remains a well-formed exact cover problem.
Correctness follows as before: any solution forces the specified equalities, and any grope with a two-sided identity $0$ satisfies these restrictions uniquely.
Conclusion
Parts (a) and (c) are handled by consistent pruning of allowed options. Part (b) is corrected by replacing the invalid “merging of choices” with a proper redesign of the exact-cover incidence structure: symmetric ordered-pair options are replaced by single options whose item sets enforce simultaneous assignment to both $(x,y)$ and $(y,x)$. This restores a valid exact-cover formulation and yields a bijection with commutative gropes.