TAOCP 7.2.2.1 Exercise 397
Let the grid cells be indexed by $(r,c)$, where $1\le r,c\le n$.
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: 2m38s
Setup
Let the grid cells be indexed by $(r,c)$, where $1\le r,c\le n$. A coloring of the grid assigns each cell a value in ${0,1}$. A cell with value $1$ is on the sheep's side of the fence, and a cell with value $0$ is on the other side.
The fence is the boundary between cells of different colors, together with the portions of the outside boundary needed to connect the two endpoints of the fence to the edge of the grid. The condition on a sheep square means that every specified sheep cell must have exactly two incident grid edges belonging to this boundary.
For part (a), the goal is to express the problem as an XCC instance, so that Algorithm C can enumerate all possible fences. For part (b), a puzzle with a unique fence must be supplied and justified.
Solution
Part (a)
For each possible coloring $C$ of the grid, define an option consisting of all local choices made by the fence. The items of the XCC instance are the constraints that must be satisfied exactly once, or satisfied with a specified color in the sense of Algorithm C.
The first class of items represents the sheep constraints. For every sheep square $s$, introduce an item
$S_s.$
An option covers $S_s$ with color $1$ exactly when the square $s$ is placed on the sheep side. Every valid solution must therefore select only options in which all sheep items receive color $1$.
The second class of items represents grid edges. For every internal grid edge $e$, introduce an item
$E_e.$
An option covers $E_e$ precisely when the chosen coloring changes across that edge. Since a fence cannot visit a point twice, the selected edge set must form a single path. The endpoint conditions are enforced by introducing boundary items that require exactly two incidences on the outside of the grid.
The local contribution of a cell is determined by its four neighboring positions. A cell of color $1$ contributes its incident edges where the neighboring cell has color $0$, and a cell of color $0$ contributes no sheep-side edges. Thus each candidate cell state is an option containing the corresponding edge items and the sheep item when the cell contains a sheep.
The XCC conditions enforce the following facts. Every sheep square has color $1$. Every grid edge is either selected once as part of the fence or not selected. Every grid vertex has fence degree $0$ or $2$, except for the two endpoints, which have degree $1$ and lie on the boundary. Consequently, every solution of the XCC instance gives a fence satisfying the puzzle rules.
Conversely, a valid fence determines a unique coloring by assigning value $1$ to the side containing the sheep and value $0$ to the other side. The associated local cell choices satisfy all XCC conditions. Therefore every valid fence corresponds to a solution of the XCC problem.
Hence the set of solutions of the save-the-sheep puzzle is exactly the set of solutions of the constructed XCC problem, and Algorithm C can enumerate all fences.
Part (b)
Consider the following $8\times8$ puzzle. The symbols $\times$ indicate sheep.
$$ \begin{array}{cccccccc} . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ \times & \times & \times & \times & \times & \times & \times & \times\ . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & . \end{array} $$
The intended fence surrounds the fourth row. It begins at the left edge at the upper-left corner of cell $(4,1)$, follows the upper sides of the eight sheep cells to the right edge, turns downward, follows the lower sides of the eight sheep cells back to the left edge, and ends there at the lower-left corner of cell $(4,1)$.
The fence has no repeated grid point. Each sheep cell has exactly its upper and lower edges on the fence. The two endpoints lie on the edge of the grid. Thus the displayed fence is a valid solution.
To prove uniqueness, assign color $1$ to the sheep side. Every sheep cell in row $4$ must have color $1$. Consider the two cells $(4,c)$ and $(4,c+1)$ for $1\le c<8$. Since both are sheep cells, the edge between them cannot belong to the fence. Therefore the entire fourth row is a single connected block of color $1$.
Each sheep cell must have exactly two incident fence edges. The two horizontal edges between adjacent sheep cells are unavailable, because both adjacent cells have color $1$. The only possible fence edges incident with the interior sheep cells are the edges immediately above and below the fourth row. Hence all sixteen horizontal edges bordering the fourth row must belong to the fence.
The leftmost sheep cell $(4,1)$ already has its upper and lower edges forced. Its left edge cannot be part of the fence, because the fence would then have an additional endpoint on the boundary. The same argument applies to the rightmost sheep cell $(4,8)$. Therefore the fence must be exactly the two horizontal segments bordering row $4$, joined at the two outside endpoints.
Any additional color-$1$ cell above or below row $4$ would remove one of the forced fence edges bordering the fourth row, causing at least one sheep cell to have fewer than two fence edges. Therefore no additional cells can be on the sheep side. The coloring and the fence are unique.
The puzzle contains eight sheep, satisfying the requirement that the number of sheep be at most ten. The unique solution is the fence described above.
Verification
The XCC reduction has the required two directions. A fence supplies a valid colored exact cover, and every valid XCC solution supplies a fence because the edge constraints enforce a single non-self-intersecting path.
For the $8\times8$ construction, the sheep count is
$$ 8, $$
because there is one sheep in each column of row $4$. The uniqueness argument forces every edge of the upper and lower boundaries of row $4$, excludes every other incident edge, and prevents any additional sheep-side cells.
The final answer for the constructed puzzle is
$$ \boxed{\text{the }8\times8\text{ grid with sheep exactly at }(4,1),(4,2),\ldots,(4,8).} $$
Notes
The same XCC formulation works for more complicated puzzles by adding further colored items for additional restrictions. The sparse representation used by Algorithm C is appropriate because only local cell and edge interactions need to be stored.
This completes the proof.
∎