TAOCP 7.1.4 Exercise 216
An 8×8 chessboard is partitioned into 32 dominoes in a perfect covering.
Section 7.1.4: Binary Decision Diagrams
Exercise 216. ▶ [30] [30] Figure 29(b) shows a chessboard covered with red, white, and blue domi- noes, in such a way that no two dominoes of the same color are next to each other. a) In how many ways can this be done? b) How many of the 12,988,816 domino coverings are 3-colorable?
Verified: no
Solve time: 2m04s
Setup
An 8×8 chessboard is partitioned into 32 dominoes in a perfect covering. Let $\mathcal{M}$ denote the set of all such domino coverings; it is given that
$|\mathcal{M}| = 12{,}988{,}816.$
For a fixed covering $M \in \mathcal{M}$, define a graph $G(M)$ whose vertices are the 32 dominoes of $M$. Two vertices are adjacent if and only if the corresponding dominoes share a common edge of the chessboard (that is, two distinct dominoes occupy two unit squares that are orthogonally adjacent).
A “3-colorable covering” is a pair consisting of a domino covering $M$ together with a function
$c : V(G(M)) \to {1,2,3}$
such that for every edge $uv$ of $G(M)$, one has $c(u) \neq c(v)$.
The task is to determine:
a) the number of such pairs $(M,c)$ over all domino coverings $M \in \mathcal{M}$;
b) the number of coverings $M \in \mathcal{M}$ for which at least one proper 3-coloring of $G(M)$ exists.
The second part depends only on whether $G(M)$ is 3-colorable; since every graph on at most 32 vertices with maximum degree at most 4 arising from a planar grid adjacency admits a 3-coloring whenever it is not a complete obstruction, the enumeration reduces to counting all coverings weighted by the number of proper 3-colorings of $G(M)$.
Solution
Fix a domino covering $M$. Each vertex of $G(M)$ corresponds to a domino, hence to an edge of the grid graph $P_8 \square P_8$ that is used in the perfect matching.
Two dominoes are adjacent in $G(M)$ exactly when their corresponding matching edges are incident to opposite endpoints of a unit grid edge not used by the matching. Equivalently, each adjacency in $G(M)$ corresponds bijectively to a unit edge of the grid that is not covered internally by a domino.
The 8×8 grid has
$8 \cdot 7 + 8 \cdot 7 = 112$
unit edges. Each domino occupies exactly one unit edge internally, and there are 32 dominoes, so exactly 32 unit edges are internal to dominoes and do not contribute to adjacency between distinct dominoes. Hence every covering induces a graph $G(M)$ with exactly
$112 - 32 = 80$
edges. This edge count is independent of $M$.
Let $P_{G(M)}(3)$ denote the number of proper 3-colorings of $G(M)$. The desired quantity in part (a) is
$\sum_{M \in \mathcal{M}} P_{G(M)}(3).$
For any finite graph $G$, the chromatic polynomial satisfies
$P_G(3) = \sum_{F \subseteq E(G)} (-1)^{|F|} 3^{c(F)},$
where $c(F)$ is the number of connected components of the spanning subgraph $(V(G),F)$. Applying this identity to each $G(M)$ yields
= \sum_{M \in \mathcal{M}} \sum_{F \subseteq E(G(M))} (-1)^{|F|} 3^{c(F)}.$$ Interchanging summations produces a sum over pairs $(M,F)$ where $F$ is a subset of adjacency edges induced by $M$. Each such pair can be encoded purely as a selection of grid edges together with a perfect matching, hence as a configuration on the fixed 8×8 lattice with local constraints only. The crucial structural fact is that both $|E(G(M))|$ and the local incidence structure