TAOCP 7.2.2.1 Exercise 322

Section 7.2.2.1: Dancing Links

Exercise 322. [25] The polysticks provide us with another intriguing family of shapes that can be combined in interesting ways. An "$n$-stick" is formed by joining $n$ horizontal and/or vertical unit line segments together near grid points. For example, there are two disticks and five tristicks; and of course there's only one monostick. They're shown here in white, surrounded by the sixteen tetrasticks in black.

Polysticks introduce yet another twist into polyform puzzles, because we must not allow different pieces to cross each other when we pack them into a container. Extend exercise 265 to polysticks, so that Algorithm X can deal with them conveniently.

Verified: no
Solve time: 2m05s

Solution

Exercise 265 extends Algorithm X to packing problems by making each possible placement of a piece into the container an option, with items representing the conditions that must be satisfied exactly once. For ordinary polyform packing, the items are the cells of the container together with one item for each piece, so that a solution chooses one placement of every piece and covers every occupied cell once.

For polysticks, the same construction handles the segments, but the set of items must be enlarged because a valid packing forbids crossings of segments. A placement of a polystick consists of a finite set of unit horizontal and vertical segments. Let the container be a finite set of unit grid segments. For each possible placement $P$ of each available polystick, create one option. The option contains an item $s$ for every container segment $s$ occupied by $P$, and it contains an item $p$ identifying the particular polystick used.

These items alone forbid two pieces from sharing a complete unit segment, but they do not forbid a horizontal segment of one piece and a vertical segment of another piece from crossing at an interior grid point. Introduce an additional item for every possible interior crossing point of the container. A placement $P$ contains the crossing item corresponding to a grid point $v$ precisely when a segment of $P$ passes through $v$ without ending there.

The exact cover instance is obtained by replacing every placement option $P$ by the set

$$ {\text{piece item of }P} \cup {\text{segment items occupied by }P} \cup {\text{interior crossing-point items used by }P}. $$

The piece items force every polystick to be selected exactly once. The segment items force the selected placements to be edge-disjoint. The crossing-point items force the selected placements to be free of forbidden intersections.

To prove that this construction is equivalent to the original packing problem, first suppose a set of polystick placements gives a legal packing. Every piece occurs once, so every piece item occurs in exactly one selected option. Every container segment is used by at most one piece, so every segment item occurs in at most one selected option. Every crossing point is used as an interior point by at most one selected placement, because two such uses would produce a crossing. If the container formulation requires all container segments or all required boundary conditions to be filled, the corresponding items are included in the ordinary manner from exercise 265, and the selected options cover them exactly once. Hence the selected options form an exact cover.

Conversely, suppose a collection of options forms an exact cover of the constructed item set. The piece items imply that the collection contains exactly one placement of every required polystick. Since segment items occur exactly once, no two selected placements share a unit segment. Since crossing-point items occur exactly once, no two selected placements have segments crossing at an interior grid point. Thus the selected placements form a packing in which pieces do not overlap and do not cross.

The only modification required to Algorithm X is therefore the addition of the crossing-point items to the option database. The dancing-links representation and the operations $\operatorname{cover}$ and $\operatorname{uncover}$ remain unchanged, because Algorithm X depends only on the exact-cover incidence structure, not on the interpretation of the items. The polystick problem is consequently reduced to an ordinary exact cover problem with a larger set of items.