Editing Sudoku/Thorkil Naur (section)

== Basic reduction strategies: By field and by element ==

Two different basic reduction strategies are implemented for a
constraint set: Reduction by field and reduction by element.

Field reduction is based on the consideration of subsets of fields of
the constraint set to be reduced. For some subset of the fields, the
union of the elements that can be contained in any of the fields is
computed. If the number of elements in this union is less or equal to
the size of the subset, the subset is said to be reducing and the
elements of the union cannot be used outside this subset of fields.
Hence the elements of the union can be removed from all the other
fields of the constraint set.

As an obvious special case of this, if a single field can only
contain a single element, then that element can be excluded from all
the other fields.

Field reduction uses this idea repeatedly: The non-empty subsets of
the fields of the constraint set are considered in order of
increasing size. If a subset is found to be reducing, the element
union is excluded from the remaining fields of the constraint set and
field reduction is repeated on this remaining set of fields. Field
reduction is done by function sdkReduceByField.

(Technical note: sdkListLengthLE is used rather than comparison of
list lengths to improve performance.)

For element reduction, subsets of elements are considered. For some
subset of elements, the set of fields that can contain any of the
elements is computed. If the number of such fields equals the number
of elements in the subset, any additional elements recorded as
candidates for these fields can be excluded.

For example, consider the subset {1,2} of elements and assume that we
find that the only fields that may contain 1 or 2 have {1,2} and
{1,2,3} as candidate element sets. Then 1 and 2 must occupy precisely
these two fields and 3 can be excluded as a possibility for the
second field.

As for field reduction, element reduction uses this idea repeatedly,
considering at each step the shortest reducing element subset
(function sdkReduceByElement).