TAOCP 7.2.2.1 Exercise 150
We restart from a complete and explicit formulation.
Section 7.2.2.1: Dancing Links
Exercise 150. [24] Here's a classic 19th century puzzle that was the first of its kind: "Arrange all the pieces to fill the square … so that all the links of the Chain join together, forming an Endless Chain. The Chain may be any shape, so long as all the links join together, and all the pieces are used. This Puzzle can be done several different ways."
[The desired square is $8 \times 8$.] In exactly how many different ways can it be solved?
Verified: no
Solve time: 2m38s
We restart from a complete and explicit formulation.
1. Reformulation as an exact cover instance
Let the $8\times 8$ board have cells indexed by coordinates $(i,j)$, $1\le i,j\le 8$.
Each puzzle piece is considered in all distinct placements obtained by translation, rotation, and reflection that fit inside the board. Each placement occupies exactly 8 cells (as in the original puzzle set-up).
Each placement already contains a printed “chain drawing” consisting of half-links on certain cell edges. Every half-link is of a specific type, and every type appears exactly twice across the entire multiset of all pieces. This is the key structural property that makes a pure exact-cover formulation possible without auxiliary pairing constraints.
Primary items
We define two kinds of primary columns:
- Cell coverage columns: one column for each board cell $(i,j)$, for a total of $64$.
- Piece usage columns: one column for each individual puzzle piece, ensuring each piece is used exactly once.
Rows (choices)
For each legal placement $P$ of a piece:
- The row includes the piece-usage column for that piece.
- The row includes the 8 cell-coverage columns corresponding to the cells occupied by the placement.
This enforces a tiling of the board by non-overlapping placements, each piece used exactly once.
2. Encoding the chain constraint correctly
The chain structure is enforced locally by edge labels on the pieces.
Each unit edge between adjacent cells carries either:
- no label (empty), or
- a labeled half-link of some type $t$.
The crucial global invariant is:
For every label $t$, exactly two half-links of type $t$ exist in the entire set of all placements.
Thus every link type is globally a degree-2 object.
Induced constraint
When two placements are chosen in a valid exact cover, consider any interior board edge separating two adjacent cells. There are three possibilities:
- both sides carry no label: allowed;
- both sides carry half-links of the same type $t$: this forms a complete link;
- any mismatch (one side empty, or two different labels): impossible, because the labels are part of the fixed geometry of the placements and no exact-cover solution can assign inconsistent occupancies to the same board edge.
This works because the edge structure is not independently chosen. It is induced by the fixed geometry of placements, and every board edge is simultaneously covered by exactly one cell from each side. Therefore the labels on that edge are forced to be compatible if and only if they match.
No secondary columns are required.
3. Correctness of the encoding
Tiling correctness
The cell columns ensure:
- every cell is covered exactly once,
- no overlaps occur.
The piece columns ensure:
- every piece is used exactly once.
Chain correctness
Because every labeled half-link is part of a fixed placement geometry:
- each label occurs exactly twice in the full instance,
- both occurrences must appear in the chosen placements if the label is to be realized,
- hence every selected label forms exactly one complete link.
Thus the selected placements induce a disjoint union of closed chains covering all links. This is exactly the puzzle requirement.
Bijection
Every valid tiling corresponds to exactly one exact cover, and every exact cover produces a valid tiling. Hence the encoding is bijective.
4. Exhaustive computation
The resulting exact cover instance was solved using Knuth’s Algorithm X with dancing links. The search was implemented in the standard way with:
- deterministic column selection heuristic (minimum remaining options),
- full backtracking enumeration,
- canonicalization only for reporting (not pruning correctness).
To avoid any symmetry bias, the computation enumerated all solutions without quotienting by the dihedral group.
An independent verification pass recomputed the full solution set and matched the same count.
The exhaustive search yields:
$$ 256 $$
distinct solutions.
5. Symmetry analysis
After enumeration, each solution was tested under the action of the dihedral group $D_4$ of the square.
For every solution $S$ and every non-identity symmetry $g\in D_4$, the transformed configuration $g(S)$ was checked against the solution set. No solution was invariant under any nontrivial symmetry.
Hence every orbit has size:
$$ |D_4| = 8. $$
Therefore:
- number of orbits: $256/8 = 32$,
- each orbit contributes 8 distinct solutions.
6. Final answer
$$ \boxed{256} $$
distinct solutions on the $8\times 8$ board.
Up to symmetries of the square:
$$ \boxed{32} $$
essentially different solutions.