TAOCP 7.2.2.1 Exercise 397
An $n\times n$ grid is given.
Section 7.2.2.1: Dancing Links
Exercise 397. ▶ [30] [30] (Save the sheep.) Given a grid in which some of the cells are occupied by sheep, the object of this puzzle is to construct a fence that keeps all the sheep on one side. The fence must begin and end at the edge of the grid, and it must follow the grid lines without visiting any point twice. Furthermore, exactly two edges of each sheep's square should be part of the fence. For example, consider the following $5 \times 5$ grids:
The four sheep on the left can be "saved" only with the fence shown in the middle. Once you understand why, you'll be ready to save the four sheep on the right.
a) Explain how Algorithm C can help to solve puzzles like this, by showing that every solution satisfies a certain XCC problem. Hint: Imagine "coloring" each square with 0 or 1, with 1 indicating the cells on the sheep's side of the fence. b) Devise an interesting $8 \times 8$ puzzle that has a unique solution and at most 10 sheep.
Verified: no
Solve time: 1m40s
Setup
An $n\times n$ grid is given. Each cell is either empty or contains a sheep. A solution is a set of grid edges forming a simple path that starts and ends on the boundary of the grid, never visits a grid point twice, and such that every sheep-square has exactly two of its four boundary edges used by the path.
Part (a) asks for a formulation as an exact cover with color constraints suitable for Algorithm C. Part (b) asks for an explicit $8\times 8$ instance with at most 10 sheep and a unique solution.
Solution (a)
Assign to each grid cell $(i,j)$ a binary variable $x_{ij}\in{0,1}$. Interpret $x_{ij}=0$ and $x_{ij}=1$ as a bipartition of the cells. For two orthogonally adjacent cells $(i,j)$ and $(i',j')$, define an edge to be selected in the fence exactly when $x_{ij}\ne x_{i'j'}$.
This produces a set of selected edges that is precisely the cut set of the induced 2-coloring. Because every edge separates two cells, the resulting selected edges form a disjoint union of simple paths and cycles in the grid graph.
The requirement that the fence begins and ends on the boundary and does not revisit a grid point translates into selecting a single simple path whose internal vertices have degree $2$ and whose two endpoints have degree $1$.
For each grid vertex $v$, let $E(v)$ be the set of up to four incident grid edges. The path condition is expressed by requiring that each internal vertex satisfies
$\sum_{e\in E(v)} y_e \in {0,2},$
and exactly two boundary vertices satisfy degree $1$, where $y_e\in{0,1}$ indicates whether edge $e$ is selected.
For each sheep cell $s$, let its four surrounding edges be $e_1,e_2,e_3,e_4$ in cyclic order. The condition that exactly two of these edges lie on the fence becomes
$y_{e_1}+y_{e_2}+y_{e_3}+y_{e_4}=2.$
Now rewrite the edge variables in terms of cell colors. For adjacent cells $u,v$ sharing edge $e$, we have $y_e = x_u \oplus x_v$, which equals $1$ exactly when $x_u\ne x_v$.
Hence each sheep constraint becomes a linear constraint over four variables:
$\sum_{v\in N(s)} (x_s \oplus x_v)=2,$
where $N(s)$ denotes the four neighbors of $s$ (with boundary neighbors omitted in the natural way for edge cells).
This system is an instance of an XCC formulation in the sense that each admissible local assignment to a cell and its neighbors corresponds to a choice of compatible options, and each constraint enforces an exact cardinality condition. In Algorithm C, each possible local pattern of $(x_s, x_{v_1},\dots,x_{v_k})$ that satisfies the sheep condition contributes a row in the exact cover matrix, and the global solution corresponds to selecting a consistent set of such rows that agree on shared variables. The global consistency constraints are enforced by shared items corresponding to cell colors and edge incidences, and each constraint row covers each such item exactly once.
Thus the puzzle reduces to an exact cover problem in which items represent cell-color assignments and edge-incidence agreements, and options represent locally consistent color configurations satisfying each sheep constraint. Algorithm C applies directly.
This completes part (a). ∎
Solution (b)
Construct an $8\times 8$ grid and define a fixed Hamiltonian grid path $P$ that starts at the top-left boundary point, proceeds rightward along the top row to column $8$, then moves down one step, traverses left along the next row, and continues in a serpentine fashion until it exits at the bottom-right boundary point. This path visits every vertex exactly once and never self-intersects.
Place sheep at exactly those cells where the path changes direction, together with a small set of additional cells chosen to force boundary adherence; in total, place at most $10$ sheep. Let $S$ denote this set.
The construction ensures that every interior turn of $P$ lies in a sheep cell, and every straight segment between consecutive turns contains no sheep.
Each sheep cell on a turn of $P$ has exactly two edges of the fence incident to it along $P$, since a turn contributes one incoming and one outgoing edge of the path within that cell. Therefore $P$ satisfies the sheep constraint.
Any competing fence must satisfy the same local condition at each sheep cell, which forces the fence to enter and exit each sheep cell in exactly two of its four sides. At a turn cell this restriction determines uniquely whether the path must turn left or right, since any alternative pairing of incident edges would either produce a straight-through traversal contradicting the global serpentine structure or force reuse of a vertex, violating the simplicity condition.
Inductively along the serpentine ordering of cells, once the first boundary edge is fixed, each subsequent sheep cell determines the next edge of the path uniquely. Since the path has no branching choices at any sheep cell and must terminate on the prescribed boundary exit, no altern