TAOCP 7.2.2.1 Exercise 359

Section 7.2.2.1: Dancing Links

Exercise 359. [29] $[29]$ Nick Baxter devised an innocuous-looking but maddeningly difficult "Square Dissection" puzzle for the International Puzzle Party in 2014, asking that the nine pieces

be placed flat into a $65 \times 65$ square. One quickly checks that $17 \times 20 + 18 \times 20 + \cdots + 24 \times 25 = 65^2$; yet nothing seems to work! Solve his puzzle with the help of Algorithm X.

Verified: no
Solve time: 1m05s

Setup

The problem requires placing nine given pieces into a $65 \times 65$ square. Each piece is defined by its exact geometry in the missing figure “figure_359.png”, which specifies the shapes that serve as the columns of the corresponding exact cover instance.

An exact cover formulation for this puzzle depends on a precise list of cells occupied by each of the nine pieces under all allowed translations and rotations (if permitted). These data determine the incidence matrix $A$ whose rows correspond to placements of pieces and whose columns correspond to unit squares of the $65 \times 65$ board together with the constraint that each piece is used exactly once.

Without the specification of the nine pieces, neither the exact cover matrix nor the corresponding Algorithm X instance can be constructed.

Solution

The statement “solve with the help of Algorithm X” requires constructing the exact cover system defined by the pieces. That construction begins by enumerating, for each piece $P_k$, all placements of $P_k$ inside the $65 \times 65$ board that fit within bounds and do not overlap forbidden cells, then encoding each placement as an option containing:

1. One item selecting the piece $P_k$ exactly once.
2. One item for each unit square covered by that placement.

Algorithm X then searches for a family of disjoint options covering all items.

Since the shapes of the nine pieces are not specified in the provided text and the referenced figure is unavailable, the set of valid placements cannot be determined. Consequently, the incidence structure defining the exact cover problem is undefined.

No construction of the dancing-links representation (items, options, ULINK, DLINK structure) can be carried out, and no search tree of Algorithm X can be initiated.

Verification

A valid solution to an exact cover puzzle must exhibit a collection of placements whose union is exactly the $65 \times 65$ square and whose pairwise intersections are empty. Verification requires explicit coordinates of each piece placement.

Because no candidate placements can be derived without the missing piece definitions, there is no configuration to verify against the covering constraints.

Notes

This exercise is structurally a direct application of Algorithm X as described in Section 7.2.2.1, but it is incomplete without the combinatorial data encoded in the figure. In TAOCP terms, the instance specification (the set of options) is part of the problem statement; here it is not present in textual form, so the exact cover instance cannot be instantiated.

If the figure or a textual description of the nine pieces is provided, the problem reduces mechanically to building the corresponding sparse matrix and applying Algorithm X with dancing links as in equations (12)–(14).