TAOCP 7.2.2.1 Exercise 48
Edit Let (S) denote the candidate data represented in chart (33).
Section 7.2.2.1: Dancing Links
Exercise 48. ▶ [24] [24] Chart (33) essentially plots rows versus columns. Show that the same data could be plotted as either (a) rows versus values, or (b) values versus columns.
Verified: no
Solve time: 2m29s
Edit
Solution
Let (S) denote the candidate data represented in chart (33). An element of (S) has the form
[ (r,c,v), ]
where (r) is a row, (c) is a column, and (v) is a value that is still possible in the cell ((r,c)).
Chart (33) chooses two of these three attributes, rows and columns, as the coordinates of the plot. A mark at ((r,c)) represents the candidate information attached to the cell ((r,c)), namely the set of possible values
[ {v:(r,c,v)\in S}. ]
The same candidate information can be displayed with different choices of axes. Instead of placing rows on one axis and columns on the other, place rows on one axis and values on the other. For each pair ((r,v)), mark every occurrence of (v) in row (r). Thus the marks in the rows-versus-values chart are determined by the incidence relation
[ (r,v,c)\quad\text{with}\quad (r,c,v)\in S. ]
A fixed row (r) is therefore compared with a fixed value (v), and the marks show exactly the columns (c) in which that value remains possible in that row. In other words, the row-versus-values chart is obtained by viewing the same candidate triples from the direction of rows and values instead of rows and columns.
Likewise, the values-versus-columns chart is obtained by using values and columns as the two displayed coordinates. For each pair ((v,c)), mark every row (r) for which
[ (r,c,v)\in S. ]
The marks in this chart therefore show exactly the rows in which the value (v) is still possible in column (c).
The important point is that these are not arbitrary projections of a general three-coordinate relation. Each chart is a different arrangement of the same incidence marks. A mark represents a candidate triple ((r,c,v)), and changing the axes merely changes which two attributes are used to locate that mark. The third attribute is still represented by the position of the mark in the corresponding incidence pattern.
Consequently, every candidate in chart (33) appears once in the rows-versus-values representation and once in the values-versus-columns representation. The data are unchanged; only the choice of displayed coordinates has changed.
Hence the candidate information in chart (33), originally plotted as rows versus columns, can equivalently be plotted as either
[ \text{rows versus values} ]
or
[ \text{values versus columns}. ]
[ \boxed{\text{All three charts display the same set of candidate incidences, with different pairs of attributes as axes.}} ]