The New Sudoku Players' Forum

[alanr555]

[code]
Mandatory Pairs - Methodology
Погледај предходну тему :: Погледај следећу тему
Аутор Порука
alanr555

Придружио: 01 Авг 2005
Поруке: 30
Локација: Somerset BS23
Послао: Чет Окт 13, 2005 4:21 pm
Наслов: Mandatory Pairs - Methodology

--------------------------------------------------------------------------------

It has been suggested that many (human) solvers of Sudoku puzzles tend
to use overly complex methods. In particular when 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 switch 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 any ideas as to realistic
alternatives would be welcomed!).

Comments are invited.
A scale of challenges could then arise

a) Solve Easy without any "pencil marks"
b) Solve Mild without any pencil marks
c) Solve Difficult using Mandatory Pairs
d) Solve Fiendish using Mandatory Pairs

Which of these are achievable?
Should the references to easy/mild/difficult 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
0797-626-2406
(alanr777@waitrose.com)


Прикажи поруке из последњих: Све поруке1 Дан7 Дана2 Недеље1 Месец3 Месеца6 Месеци1 Година Прво нај старијеПрво нај новије

Надгледај ову тему за одговоре

Можете писати нове теме у овом форуму
Можете одговарати на теме у овом форуму
Можете мењати ваше порукеу овом форуму
Можете брисати ваше поруке у овом форуму
Можете гласати у овом форуму

Powered by phpBB © 2001, 2005 phpBB Group
This forum is translated in Serbian_cyrillic by: Damjanac Djordje
[/code][/code]

[Lummox JR]

From what I follow of this technique, I believe it is equivalent to hidden pairs. In a hidden pair, two digits can only occupy the same two positions in a box/column/row. Any other candidates appearing in those two cells can be eliminated.

This is just one of the many subset methods. There is also naked pairs, which says that if two cells in a box/column/row can only have two possible values, those digits can be eliminated in the rest of that box/column/row.

Of course you can get into triples and more, as well.

[alanr555]

[code]
> From what I follow of this technique, I believe it is equivalent to hidden > pairs. In a hidden pair, two digits can only occupy the same two
> positions in a box/column/row. Any other candidates appearing in those > two cells can be eliminated.

> This is just one of the many subset methods. There is also naked pairs, > which says that if two cells in a box/column/row can only have two
> possible values, those digits can be eliminated in the rest of that
> box/column/row.

> Of course you can get into triples and more, as well.

It is far MORE than just hidden pairs or naked pairs.
It is a method usable by HUMANS which can avoid the need to use
the full facility of candidate profiles.

It's particular advantage is the power of BINARY. Every entry MUST
have its partner. If not using "pencil marks", it can be very demanding
having to remember previously discovered patterns - or having to
work out again the scenario for a line, column or region. This method
severely reduces such need. Get the options down to "two in a box"
and record them - for use later in the solution process. This is not a
method guaranteed to reach a solution but it can prove to be a very
useful aid to human solution without resorting to the laborious search
for patterns in the candidate profiles.

My one recent addition to the method expounded in the main post is
that when the method appears to have captured the "obvious" or
easy resolutions, there is merit in marking OUTSIDE the grid for
each row and column (I do it when needed rather than systemically)
a string of digits still not placed on that row or column. There is no
place to record the similar string for the regions but somehow the
task of finding the missing items is easier for a 3x3 box than for a
9x1 row/column.

So thank you to the forum participant who expressed interest in the
method. Developing it fuelled my interest in Sudoku (which does not
involve always being at the leading edge) and has enabled me to
retain an interest in medium and easy puzzles.

Alan Rayner BS23 2QT
[/code]

[NorwegianViking]

Hello

I will try your methode. It sure looks interesting.
My first thought was also that it was covered by or overlapped other methodes, but it deserves to be tested/verified and compared to other methodes.
Thanks for taking the time to post such a detailed explanation. You clearly deserved a higher number of responses.

[Max Beran]

This very topic and approach has come up on this board a few times including quite recently.

See here for very similar.

Max Beran