TAOCP 7.2.2.1 Exercise 266

The utility program reads a description of a target shape and a set of polyominoes, then outputs a list of *options* for an exact cover solver.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 266. ▶ [25] Sketch the design of a utility program that will create sets of options by which an exact cover solver will fill a given shape with a given set of polyominoes.

Verified: no
Solve time: 1m29s

Solution

The utility program reads a description of a target shape and a set of polyominoes, then outputs a list of options for an exact cover solver. Each option corresponds to placing one polyomino (in a specific orientation and position) so that it lies completely inside the shape. The exact cover problem has two kinds of primary items:

  • Cell items - one for each unit square of the shape.
  • Polyomino items - one for each polyomino in the set (to enforce that every polyomino is used exactly once).

An option covers the cell items occupied by the placement and the polyomino item of the piece being placed. A solution to the exact cover problem is therefore a tiling of the shape by the given polyominoes.

1. Input format

The shape is given as a set of cells. A convenient representation is a rectangular grid of characters (e.g. . for empty, # for a cell) or an explicit list of integer coordinates ((x,y)). Each polyomino is given as a list of its cells relative to an arbitrary origin; the set of polyominoes may be accompanied by flags indicating whether reflections are allowed (free polyominoes) or only rotations (one‑sided polyominoes).

2. Data structures

  • Shape: a hash set (or a 2D boolean array) S containing all cell coordinates of the shape. Also maintain the bounding box ([x_{\min},x_{\max}]\times[y_{\min},y_{\max}]) for quick rejection of placements.
  • Item indexing: assign a unique integer ID to each cell in S (cell items) and to each polyomino (piece items). Store the mapping from coordinates to cell IDs for output.
  • Polyomino descriptions: for each piece, store its name and its list of relative cell coordinates ({(x_k,y_k)}).

3. Generating distinct orientations

For each polyomino (P) with cells ({(x_k,y_k)}), produce the set of its distinct orientations under the allowed symmetry group (rotations by (0^\circ,90^\circ,180^\circ,270^\circ) and, if free, reflection across the (x)-axis followed by rotations). For each transformation, translate the resulting cells so that their minimum (x) and (y) are zero, sort the cells lexicographically, and insert the canonical representation into a set to eliminate duplicates. The output is a list of oriented polyominoes, each with its own cell list ({(x_k,y_k)}) (already normalized to non‑negative coordinates) and its width (w = \max x_k + 1) and height (h = \max y_k + 1).

4. Generating placements

For each oriented polyomino (O) of piece (p):

  • For each translation ((dx,dy)) such that the translated cells ({(x_k+dx, y_k+dy)}) lie inside the shape’s bounding box:
    • Check whether every translated cell belongs to S. (With a hash set this is (O(|O|)) per translation.)
    • If all cells are present, create an option consisting of:
      • the cell item IDs of the translated cells,
      • the piece item ID of (p).
    • Output this option (e.g., as a line of item numbers or names).

To avoid redundant translations when the shape is sparse, one may instead iterate over all cells (c \in S) as a candidate for the polyomino’s reference cell (e.g., the cell that maps to ((0,0)) in the normalized orientation) and check whether the whole polyomino fits. This reduces the number of trials when the shape has many holes.

5. Output format

The program writes a list of options, one per line. Each line contains the item identifiers (or symbolic names) of the cells covered, followed by the piece identifier. This list can be directly converted to the memory layout used by Algorithm X (Table 1) by assigning LLINK/RLINK for the horizontal item list and building the vertical option lists with spacer nodes as described in the text.

6. Correctness and completeness

Every valid tiling corresponds to a set of options that covers every cell item exactly once and every piece item exactly once, i.e., an exact cover. Conversely, any exact cover selects disjoint placements that together cover the whole shape and use each piece exactly once, hence a tiling. The generation of orientations is exhaustive up to the allowed symmetries; the translation loop covers every position where the oriented polyomino fits inside the bounding box, and the membership test guarantees it lies inside the shape. Thus the utility produces precisely the set of options required.

Notes

  • The program can be made more efficient by precomputing for each oriented polyomino a “footprint” (e.g., a bitmask) to accelerate the membership test, especially when the shape is given as a dense grid.
  • If the polyomino set contains many pieces, the number of options may be huge; in practice one often adds a heuristic to choose the most constrained item first (minimum remaining values), which is exactly the MRV heuristic used in Algorithm Z.
  • The design extends directly to polycubes (3D) or other polyforms by generalizing the coordinate system and symmetry group.