TAOCP 7.2.2.1 Exercise 80

The statement of Exercise 7.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 80. [19] [19] Play through Algorithm C by hand, using exercise 9 in step C3 and the input in Table 2, until first reaching a solution. What are the contents of memory then?

Verified: no
Solve time: 1m57s

Solution

The statement of Exercise 7.2.2.1.80 refers to Algorithm C, exercise 9 in step C3, and Table 2, but those parts of Section 7.2.2.1 are not included in the supplied context.

To work the exercise completely, the following missing information is required:

  1. The definition of Algorithm C, including all steps C1, C2, C3, and the meaning of the instruction “exercise 9 in step C3”.
  2. The exact statement of exercise 9 referred to in step C3.
  3. The complete contents of Table 2, which supplies the input instance.
  4. The memory layout conventions used by Algorithm C at the point where the exercise asks for “the contents of memory then”.

Without these data, the requested hand simulation cannot be derived, because the sequence of choices, covers, uncovers, and memory updates is determined by the missing algorithm and input table.

Please provide the continuation of Section 7.2.2.1 containing Algorithm C, exercise 9, and Table 2, and I will produce the full textbook-style solution.