dailysudoku.com

[alanr555]

Code
In earlier contributions, Samgj has suggested that many (human) solvers of
Sudoku puzzles tend to use overly complex methods. In particular he wrote
of deriving a solution to "Medium" puzzles.

I have just spent a couple of weeks on vacation and took with me some
puzzles for solution. I found the compilation of the "Solution Grid" with
all the candidates indicated as superscripts to be tedious. That was the
method that I learned when looking at computer solutions but there "ought"
to be a simpler method for simpler puzzles - for humans!.

Generally "Easy" puzzles can be solved simply by inspection - with direct
writing of the solution in each cell. However there comes a level at which
one needs to resort to "pencil marks" or some other form of note taking as
the human brain (mine anyway!) does not have the resources to hold in short
term memory ALL the factors necessary to resolve each cell. My aim was to
devise a methodology which could work for other than the most complex cases.

During my vacation, I developed the "Mandatory Pairs" method and found that
it was able to resolve all the Easy, Mild and Difficult puzzles that I have
tackled from Wayne Gould's classification but that it fell short when faced
with the "Fiendish" category. I found similarly with the classifications of
other authors (eg Huckvale) but I cannot say that a fully scientific survey
has been undertaken.

Thus, I offer the method as a means of tackling puzzles with the intermediate
classifications (which all seem to differ between authors!) when one is not
in the mood for developing a full candidate profile. However, one merit of
Mandatory Pairs is that one can go part way with the method and then xx
to the full "Candidate Elimination" method later. Indeed, Mandatory Pairs
form a subset of the candidate data.

+++

Although there is only ONE objective in Sudoku, having an intermediate aim
can prove useful in working towards that overall objective.

The aim of Mandatory Pairs is:

"For each digit 1-9, to identify and record in each region a subset of cells
(with a maximum of TWO members in the subset) such that the said digit MUST
be placed in one of the members of that subset in the overall solution."

Of course, amending the word "TWO" to "ONE" would be equivalent to the full
objective of Sudoku. However, in practice, reducing the uncertainty to just
two of the nine cells in each region is valuable and, if recorded visually,
can lead to quicker resolution of the puzzle than searching for patterns
using the candidate elimination method.

Each subset with ONE member is a resolved cell! Each subset with TWO members
is called a "Mandatory Pair" as it is MANDATORY that one of the pair is the
correct solution. One of the principal values of identifying such pairs is
that information negating the possibility of one member being the solution
IMMEDIATELY promotes the OTHER member (its partner) to be a correct placement
in the overall solution.

It is already a convention that the top left corner of each cell can be used
as a "superscript" for candidate elimination. Thus the BOTTOM left corner of
each cell is used to record members of each Mandatory Pair. Users should note
that it is NOT necessary to record any linkage between the two members of the
pair - the link MUST be within a 3x3 region and so it is directly observable.

Four points arise

a) The number of subscript marks in any cell is NOT constrained (ie a cell
can be a partner in one, two, three or even more pairs. However as soon
as one of them is confirmed as the ACTUAL value for the cell, the others
will then be impossible and (the good point!) their partners are promoted
IMMEDIATELY to being resolved.

b) When a digit is confirmed, its partner MUST be removed from the subscript
markings. It is essential that such markings occur only in pairs and that
BOTH partners are expunged on resolution.

c) The eventual aim is, of course, to remove ALL the subscripts (unlike the
superscripts where the aim is to reduce the candidate list to one entry).

d) During inspection, it is essential to orient oneself to the "Mandatory
Pair" view. In particular the absence of a digit in a cell does NOT in
itself in any way convey any useful information.

+++

Many of the usual "direct inspection" techniques are used. In particular the
weirdly named "Slicing and Dicing" is an essential element and usually this
will reveal many "Mandatory Pairs". A possible methodology follows.

1) Form a Frequency table.

Write the digits 1-9 in a horizontal row and in parenthesis at the end
write the total number of filled cells in the initial puzzle.

Underneath each digit write the number of times that it occurs in the
original puzzle and then sum the frequencies to ensure that their total
matches the total number of cells already completed.

eg 123 456 789 (28)
325 334 332

Then the digits can be rewritten in the sequence of their frequency.

eg 3; 6; 14578; 29
It is useful to separate them into blocks of digits with same frequency.

2) a) Apply "Slicing and Dicing". This is an inspection of the interaction
between lines and columns within a group of three regions.

Where this technique reduces to one the number of cells in a region
in which the digit can be placed the technique is as per standard and
that single cell has been resolved.

Where the technique leaves three or more possible location for the
digit within a region then NO MARK is made.

Only if the number of possible locations within a region is reduced to
EXACTLY two should a (subscript) mark be made - in EACH of the two
cells remaining eligible for that digit.

Also, no marks should be made if a pair is found in a line (column or
row) but the members of the pair are not in the same region.

b) The above technique should be applied for each digit in the sequence
of the "highest frequency" (as derived above). This is because digits
with the highest frequency have the highest probability of interaction
and thus the resolution of cells. Digits with lower frequency depend
upon resolved cells (containing one of the other eight digits) in order
to reduce the number of possibilities for their placement - and so one
has a real incentive to resolve as many cells as soon as possible.

c) This technique usually resolves several cells and identifies several
Mandatory Pairs - especially if some of the tips and tricks listed
below are used in the process.

d) After checking each digit in turn, it is advisable to undertake a
"Line Check" as described in the next section - before returning to
use of this technique, which may reveal more Pairs by making use of
the greater restriction on possibilities after resolving more cells.

e) To assist with recording progress and to avoid time wasting, there is
a convention that when all NINE placements for a digit are found the
digit may be removed from the frequency ordered list of digits. There
is clearly no need to test it further! Additionally, a dot is placed
beneath each digit in the same list if for each of the nine regions
it is either resolved or a Mandatory Pair exists for that region.

3) Mandatory Pairs are only an aid to solution. Unlike candidate elimination
they do not lead inexorably to a solution. Thus there is still a lot of
scope for creativity in applying logic (rather than searching for patterns
in a solution grid). What the pairs do is a saving on the memory by giving
source information to the next logical step in a directly visual form.

Mandatory Pairs are very much concerned with what is happening inside the
region but Sudoku resolution depends upon use of information arising from
outside the region - in particular relating to the row or column (which
will generally be called a "line").

a) Lines should normally be inspected in the sequence of greatest filled
length (eg a line with 8 resolved must have the ninth resolved and a
line with 7 resolved leaves only two to be tested). Usually lines with
fewer than five resolved cells are unlikely to reveal much information.

b) Sometimes a line inspection will reveal a pair of cells which must each
have one of the same two values. These are NOT a mandatory pair - unless
the pair falls entirely within one region. The temptation needs to be
resisted to mark them in any way in the subscripts. However, using such
knowledge in conjunction with the region contents may be very useful.

c) After applying line checks (or other creative techniques!) a return to
the techiques in section (2) above should enable further progress to be
made.

d) As well as line checks, it is useful to keep an eye on the progress
within a region. After seven cells have been resolved in a region a
further mandatory pair MUST exist (of the mutual reception type which
is described below) and even after six are resolved it is likely that
useful information will arise from inspection of the region as a whole.

4) Some useful attributes of Mandatory Pairs should be noted:

a) If a Mandatory Pair is in a line (row or column) that fact precludes
any other cell in the same line having that digit. In particular if
a cell in another region in the same line DOES have that digit as part
of its pair for such other region, that member immediately becomes an
impossibility - and its partner is IMMEDIATELY resolved. Otherwise the
existence of a Mandatory Pair in a line is a very useful way to reduce
the possibilities for that digit when looking at the other two regions
which traverse that line.

b) If Mandatory Pairs for the same digit in two regions in the same broad
column occupy the same two actual columns, the placement of the digit
in the third region of the same broad column MUST be in the actual
column not occupied by the original pairs. This may be sufficient for
another pair to be generated or (quite often) to resolve a cell.

NB: This rule applies also for rows and "broad rows" of regions.
A "broad column" has a width of three columns starting in the first,
fourth or seventh column and contains 27 cells containing the whole
of three regions. A "broad row" is defined similarly.

c) If two cells within a region contain the same two digits they are
deemed to be in "Mutual Reception" and no other Mandatory Pair digit
may use either cell. This "forcing out" of another digit may be enough
to promote its partner to resolved status (if the cell is one of two)
or to generate another Pair (if the cell is one of three).

If there is ALREADY another digit present and generation of a new pair
creates a mutual reception between the new digit and one of the old
ones, the partner of the other "old" one is immediately resolved.

(eg three cells contain 34,4,3. If a new pair is generated as '2' in
first two of these cells they become 342,42,3. There is now a mutual
reception 42 for the first two cells. This means that the 3 in 342 is
impossible and the '3' in the third cell is promoted to be resolved.)

d) If two cells are in Mutual Reception (as above) they can be counted
as "resolved" when looking at the other cells unresolved. For example
a region with six cells resolved and a mutual reception counts as
eight and the remaining cell is immediately resolved. If the region has
five resolved and a mutual reception, the other two unresolved cells
can be immediately transformed into a second mutual reception.

e) Having spotted that a subscript value is impossible, it is necessary to
set its partner as resolved and to eliminate BOTH partners from the
subscripts. It is essential NOT to be tempted to take the impossibility
of the original as conveying anything about any digit which happens to
occupy the same cell.

(eg two cells contain 34 and 4. If other information makes the 4 of the
34 impossible then the second '4' is resolved. However, this does not
say anything about the '3' in the 34 cell.)

That said two cells in "mutual reception" are both resolved as soon as
either one of them is resolved or eliminated as a possibility. Also it
is possible for a "chain" to lead back to the original.

(eg five cells in a region have 34; 567; 45; 36; 7 in their subscripts.
If the 4 in the 34 becomes impossible
- 4 in the third cell is resolved and 5 is eliminated.
- 5 in the 567 is resolved and the 6 and 7 become impossible.
- 6 in 36 is resolved and 3 becomes impossible
- 7 in the fifth cell is resolved
- As 3 in 36 is impossible the 3 in the first cell is resolved.
However if the cells had been 34; 57; 45; 3; 7 then the values for
4, 5 and 7 would be resolved but 3 would still not be - the pair in
the first and fourth cells would remain, waiting new information.)

5) If the use of Mandatory Pairs does not resolve the whole puzzle, it is still
likely that it will have resolved some of the puzzle and have made the task
of compiling the candidate profile somewhat easier.

a) Every candidate profile MUST contain the digits in the mandatory pair
for the cell. If they do not then the human solver has missed out in
terms of using Mandatory Pairs comprehensively.

b) Where a "mutual reception" exists, the candidate profile should be
identical to the Mandatory Pair value for the two cells. This also
will affect the profile of every line (row/column), if any, that
passes through the two mutual reception cells.

c) It is a user option to remove ALL the Mandatory Pair data once the
candidate profiles have been compiled and checked. To do so would
mean only one set of digits in each cell. However, it may be that a
reference to Mandatory Pairs would be useful once the "crunch point"
has been passed using the candidate elimination methods and so some
users may prefer to retain the Mandatory Pair data for use later.

Conclusion:

Mandatory Pairs has a number of merits for puzzles of an intermediate level
(ie not incredibly easy or needful of 'advanced' techniques) in that there
is still the focus on creative logic rather than scanning for patterns in
candidate profiles. However, it cannot claim in any way to meet the needs
of the more advanced puzzles for which candidate profiling would seem to be
the ONLY workable method (although I would welcome any ideas as to realistic
alternatives!).

Comments are invited.
A scale of challenges could then arise

a) Solve easy without any "pencil marks"
b) Solve Medium without any pencil marks
c) Solve Hard using Mandatory Pairs
d) Solve Very Hard using Mandatory Pairs

Which of these are achievable?
Should the references to easy/medium/hard etc be replaced by criteria with
the candidate score or the number of cells completed initially?

Many in this forum are concerend with extending the frontiers of solution
into ever more arcane territory. This is valid as a purpose but also needed
are the forces of consolidation so that we do not all need to be pioneers
and use pioneering techniques when we are nowhere near the frontier.

Thank you for reading this far and considering the ideas.

Alan Rayner BS23 2QT
/code