TAOCP 7.2.2.1 Exercise 59

Exercise 59. [30] [30] Solve the jigsaw sudokus in (34). How large is Algorithm X's search tree?

Verified: no
Solve time: 1m59s

Setup

Exercise 7.2.2.1.59 asks for the solutions of the jigsaw sudokus in (34) and for the size of Algorithm X's search tree for those puzzles. The data defining the puzzles in (34), namely the jigsaw region layouts and the given clues, are not included in the supplied section excerpt.

A jigsaw sudoku is determined by two pieces of information: the partition of the $9 \times 9$ grid into nine irregular regions, and the set of fixed clues. Without both of these, there is no unique exact-cover instance to construct, and therefore no unique Algorithm X search tree to count.

Solution

The missing diagram or table for (34) is required before the exercise can be solved. Once the contents of (34) are provided, the solution consists of encoding each puzzle as an exact cover problem with items representing the usual sudoku constraints together with the jigsaw region constraints, applying Algorithm X from Section 7.2.2.1, and counting the nodes visited in the resulting search tree.

The requested final quantities cannot be derived from the excerpt alone.

Verification

Different jigsaw layouts or clue sets produce different exact-cover matrices and different Algorithm X search trees. Therefore any numerical answer given without the data from (34) would not be determined by the stated problem.

Please provide the figure or the full text of item (34), and the complete solution can be derived.