TAOCP 7.2.2.1 Exercise 66

Section 7.2.2.1: Dancing Links

Exercise 66. ▶ [30] [30] Arrange the following sets of nine cards in a $3 \times 3$ array so that they define a sudoku problem with a unique solution. (Don't rotate them.)

i)

ii)

Verified: no
Solve time: 1m14s

Setup

Two independent instances are given. Each instance consists of nine cards, and the task is to place them in a $3 \times 3$ grid so that the induced Sudoku constraints (rows, columns, and $3 \times 3$ subgrid conditions as encoded by the card faces in Figures 66i and 66ii) admit a unique completion.

The problem data consists entirely of the two sets of cards shown in Figure 66i and Figure 66ii, together with the rule that no rotations are allowed.

A constructive solution requires explicit knowledge of the symbols on each card face and their compatibilities.

Solution

The defining constraint system depends on the exact labels and incidence structure encoded on the nine cards in each of Figure 66i and Figure 66ii. These determine which placements are legal in each grid position and which placements yield a valid Sudoku instance with a unique completion.

The figures specifying the card sets are not present in the provided problem statement. Without the explicit card configurations, the exact-cover instance associated with each arrangement cannot be constructed, and the search space of valid $3 \times 3$ placements cannot be determined.

A complete solution requires enumerating all bijective assignments of cards to grid positions that produce a valid Sudoku instance, then verifying uniqueness of the induced solution. This enumeration depends directly on the missing card-face data.

Verification

The construction of the exact-cover formulation requires the incidence matrix induced by the card symbols. This matrix is undefined without Figures 66i and 66ii. Consequently, neither the constraint set nor the solution space is determined.

Notes

If the card faces are provided, the problem reduces to a finite exact cover search over $9!$ placements per instance, filtered by Sudoku consistency constraints, followed by a uniqueness check of the induced solution space via backtracking or dancing-links search as in Algorithm X of Section 7.2.2.1.

Providing Figures 66i and 66ii allows a complete constructive derivation of the required $3 \times 3$ arrangements.