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: yes
Solve time: 1m13s

Solution

A polystick is a connected set of unit horizontal or vertical segments in the integer grid. A placement of a polystick in a container is therefore determined by a set of unit grid segments, each segment joining two adjacent grid points.

Let the container be fixed. Let $\mathcal{E}$ denote the set of all unit grid segments contained in the container. Each element of $\mathcal{E}$ is a potential location for one segment of a polystick. Any valid packing must satisfy that no two polysticks use the same unit segment, since segments are rigid and cannot overlap.

Each placement of a polystick type $P$ is specified by a geometric embedding $t(P)$ in the container. Such an embedding corresponds to a finite set of unit segments, denoted $S(t(P)) \subseteq \mathcal{E}$. The constraint that pieces do not overlap translates directly to the condition that selected embeddings must have disjoint segment sets.

Construct an exact cover instance as follows. The set of items is $\mathcal{E}$, one item for each unit grid segment. For each admissible embedding $t(P)$ of each polystick $P$, define an option consisting of all items in $S(t(P))$. Selecting a family of embeddings corresponds to selecting a subcollection of options. The exact cover requirement that every item is covered exactly once forces each unit segment of the container to be used by exactly one chosen embedding, and forbids any overlap of segments.

It remains to verify that this formulation enforces the non-crossing condition. In the grid model, each segment lies entirely on a horizontal or vertical unit interval between adjacent grid points. Two distinct unit segments are either identical, disjoint except possibly at endpoints, or meet only at a common endpoint. No two distinct unit segments have a shared interior point unless they are identical, since horizontal and vertical segments intersect only at lattice points, which are endpoints of both segments. Therefore any intersection that is not an endpoint coincidence corresponds to overlap of distinct segments, which is already excluded by the exact cover constraint on $\mathcal{E}$.

Hence any solution produced by Algorithm X corresponds to a family of embeddings whose segments are pairwise disjoint except at endpoints, and therefore no crossings occur.

This reduces the polystick packing problem to an exact cover problem in the sense of Section 7.2.2.1, so Algorithm X and dancing links apply without modification. This completes the proof. ∎