dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Mandatory Pairs

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
alanr555



Joined: 01 Aug 2005
Posts: 194
Location: Bideford Devon EX39

PostPosted: Sun Dec 09, 2007 8:30 pm    Post subject: Mandatory Pairs Reply with quote

This post reintroduces the topic of Mandatory Pairs and uses the
VH puzzle of 9th December as an exemplar.

Some readers of this post will not be aware of Mandatory
Pairs as a solution method. Use of the search index on
the Daily sudoku forum will reveal some historical posts
on the subject. It has been refined since the early days
but the essential principle remains - identification of the
ONLY two cells in a 3x3 box which could POSSIBLY
contain the specific digit. That digit is written (small!)
in the bottom left corner of the two cells to which it
relates. When information comes to light which means
that one of the two cells CANNOT hold that digit, the
binary principle means that it MUST be in the other cell.

This can lead to some rapid solving as resolving one cell
may eliminate one or more other values and those force
the resolution of other cells. That process is akin to the
binary chains discussed previously but, of course, not
all chains will be identified by M/Pairs - just a subset of
very useful ones!

+++
It is possible to do a lot of preliminary work on the 9th
December VH puzzle - and this preliminary work will
ease the subsequent work using pencil-mark profiles.

Our old friend Mandatory Pairs enables
4 in row 2,
8 and 7 in row 3,
7 in row 5,
9 and 7 in row 6,
7 in row 7

Then it is down to pencil marks BUT the fact of having marked
the Mandatory Pairs tightens the PMs from those produced by
a "sweep".

In particular, there is a mandatory pair of 5 in r1c7 and r1c9
(because there must be a 5 in row 2 in c123)
This removes the 5 from r1c3 and gives a mutual reception
of 29 in r1c3 and r3c3.

That sets off a whole load more of Mandatory Pairs work and
enable solution of
9 in row 2, 6 and 9 in row 4, 9 in row 7 and 1 in row 8.

Careful inspection of the M/P marks enables some further
elimination of the profile marks and reveals the cells with
only two possibilities much more clearly.

In the top block there were
29 in r1c3,r3c3
12 in r2c6,r2c8
a triple 269 in row 1 (cols 3,5,8)
a quartet 1269 in row 4
(126 in r3c5,r3c7 and 19 in r3c9)

Clearly there is a possible link here.
Following the implications from the only values (2,9)
in r1c3 leads to a unique value for r2c8.

Having found that a test on the implications for r2c8
leads to a paradox - confirming the solution. After
that all cells resolved very easily.

+++
The challenge is to find the key cell that opens up an
implication chain. This is much easier when a lot of
cells have only two possibilities and the chains are
contained within a block - as today.

Using mandatory pairs as a preliminary does make it
much easier to refine the pencil marks.

I use a sequence of placing for pencil marks.

1) Mutual Receptions derived from the M/P process.
2) Rows and Columns with the maximum number of
cells already resolved.
3) Other rows/columns in sequence of descending
number of cells resolved.

In doing this I use process of writing the possibilities
remaining for a row/column outside the row/column.

eg col3 had (123459) at its head
When a pair/triple etc is discovered, the row/column
profile is amended to read say (29)(1345) which
indicates two subgroups in the row/column. In a few
cases I have known three sub-groups but usually one
is resolved almost immediately and so disappears.

Having written the PMs as above, the next stage is to
refine them from the Mandatory Pair information. As
the process continues, there may be additional M/P
information found and so the process is iterative.

The good news is that Mandatory Pairs will quite often
solve puzzles without resort to pencil marks giving
the profiles. Personally, I dislike the chore of deriving
the pencil marks and so I use Mandatory Pairs as much
as possible after getting stuck with "look and see". If
M/Pairs does not resolve, then the further good news
is (as above) its contribution to the refinement of the
profile pencil marks - reducing obfuscation!

+++

So, Mandatory Pairs will not win prizes for minimum solving times
but it does avoid the profile setting chore until much later in the
process and often enables it to be avoided altogether. Even on
more difficult puzzles, it can assist with identifying where to look
in terms of reducing the length of the PM profile elements without
the sometimes mind-boggling visual search for patterns. It is NOT
a method appropriate for computer solving but, in my view, it does
present a more human take on the solution challenge.

wrote:


I do scan to see what's available before writing in the PMs, but I suspect you do a lot

more than that.



It is possible to do a lot of preliminary work on this one.
Our old friend Mandatory Pairs enables
4 in row 2,
8 and 7 in row 3,
7 in row 5,
9 and 7 in row 6,
7 in row 7

Then it is down to pencil marks BUT the fact of having marked
the Mandatory Pairs tightens the PMs from those produced by
a "sweep".

In particular, there is a mandatory pair of 5 in r1c7 and r1c9
(because there must be a 5 in row 2 in c123)
This removes the 5 from r1c3 and gives a mutual reception
of 29 in r1c3 and r3c3.

That sets off a whole load more of Mandatory Pairs work and
enable solution of
9 in row 2, 6 and 9 in row 4, 9 in row 7 and 1 in row 8.

Careful inspection of the M/P marks enables some further
elimination of the profile marks and reveals the cells with
only two possibilities much more clearly.

In the top block there were
29 in r1c3,r3c3
12 in r2c6,r2c8
a triple 269 in row 1 (cols 3,5,8)
a quartet 1269 in row 4
(126 in r3c5,r3c7 and 19 in r3c9)

Clearly there is a possible link here.
Following the implications from the only values (2,9)
in r1c3 leads to a unique value for r2c8.

Having found that a test on the implications for r2c8
leads to a paradox - confirming the solution. After
that all cells resolved very easily.

+++
The challenge is to find the key cell that opens up an
implication chain. This is much easier when a lot of
cells have only two possibilities and the chains are
contained within a block - as today.

Using mandatory pairs as a preliminary does make it
much easier to refine the pencil marks.

I use a sequence of placing for pencil marks.

1) Mutual Receptions derived from the M/P process.
2) Rows and Columns with the maximum number of
cells already resolved.
3) Other rows/columns in sequence of descending
number of cells resolved.

In doing this I use process of writing the possibilities
remaining for a row/column outside the row/column.

eg col3 had (123459) at its head
When a pair/triple etc is discovered, the row/column
profile is amended to read say (29)(1345) which
indicates two subgroups in the row/column. In a few
cases I have known three sub-groups but usually one
is resolved almost immediately and so disappears.

Having written the PMs as above, the next stage is to
refine them from the Mandatory Pair information. As
the process continues, there may be additional M/P
information found and so the process is iterative.

The good news is that Mandatory Pairs will quite often
solve puzzles without resort to pencil marks giving
the profiles. Personally, I dislike the chore of deriving
the pencil marks and so I use Mandatory Pairs as much
as possible after getting stuck with "look and see". If
M/Pairs does not resolve, then the further good news
is (as above) its contribution to the refinement of the
profile pencil marks - reducing obfuscation!

Some readers of this post will not be aware of Mandatory
Pairs as a solution method. Use of the search index on
the Daily sudoku forum will reveal some historical posts
on the subject. It has been refined since the early days
but the essential principle remains - identification of the
ONLY two cells in a 3x3 box which could POSSIBLY
contain the specific digit. That digit is written (small!)
in the bottom left corner of the two cells to which it
relates. When information comes to light which means
that one of the two cells CANNOT hold that digit, the
binary principle means that it MUST be in the other cell.

This can lead to some rapid solving as resolving one cell
may eliminate one or more other values and those force
the resolution of other cells. That process is akin to the
binary chains discussed previously but, of course, not
all chains will be identified by M/Pairs - just a subset of
very useful ones!

+++

So, Mandatory Pairs will not win prizes for minimum solving times
but it does avoid the profile setting chore until much later in the
process and often enables it to be avoided altogether. Even on
more difficult puzzles, it can assist with identifying where to look
in terms of reducing the length of the PM profile elements without
the sometimes mind-boggling visual search for patterns. It is NOT
a method appropriate for computer solving but, in my view, it does
present a more human take on the solution challenge.
Back to top
View user's profile Send private message
alanr555



Joined: 01 Aug 2005
Posts: 194
Location: Bideford Devon EX39

PostPosted: Mon Dec 10, 2007 3:28 am    Post subject: Reply with quote

Continuing the commentary on the Mandatory Pairs method, the
Hard puzzle for 10th December has been used as an exemplar.

This puzzle presents little difficulty if the Mandatory Pairs approach
is applied as a preliminary to writing the profiles. Those wishing to
experiment with the approach may value the following clues.

M/P resolves
1 and 7 on row one
7, 5, 1 on row three
7 and 6 on row four
6, 9, 7 on row seven
1, 7, 6 on row nine

Working on the profiles leads to
4 in rows two , three, four, five and six
9 in rows five and six

This leaves the 3 exposed in row one
and the presence of the M/P marks makes
the resolution almost a "write-in".

In order not to "spoil" the solution, I have not
included the cell details but the above should
enable anyone wishing to use M/Pairs to gauge
progress on applying the methodology.

As additional hints, the following pairs can be
identified in the nine regions - numbering them
across first.

ONE - 3 and 6
TWO - 6
THREE - 1,4,7,8 (and 2 later)
FOUR - 3 (and 9 later)
FIVE - 1,2,4,8,9
SIX - 4 and 6
SEVEN - 1,3,5,6,8,9
EIGHT - 1,4,5,7
NINE - 3,6,7,9 (and 5 later)

Incidentally, regions five and seven are examples of
"definitionally complete" regions in that ALL of the
digits are constrained each to two cells.

In such cases the M/Pair details become the SAME as
the traditional "pencil mark" profiles - and so may be
copied from bottom left to top left when the PMs are
being derived - another saving on the derivations!

Rows seven, eight and nine have examples of the
"mutual reception" where two digits are each constrained
to the same two cells. This is a powerful phenomenon
as all other digits are then excluded from those cells. Of
course that rule applies also with the pencil mark patterns
but is very much clearer with the M/Pairs. As an example:
three cells with pairs marked as (123)(23)(1) immediately
develop to a definite 1 in the third cell and a mutual reception
of 2 and 3 in each of the first two. The exclusion of the 1
from the first cell DIRECTLY resolves the third cell. Also,
once the mutual reception is identified, it "blocks" the use
of those two cells for any other digit - and so can limit the
scope for placing other digits in such a way that only two
cells (or even less than two!) remain possible placements.
The Mutual Reception, thus, can be regarded as being two
resolved cells when counting unresolved cells in the region
(or on the line if the M/R cells are both in line).

This puzzle includes a triple in one region. One of the lacks
of M/Pairs is that it does not highlight triples or pairs that
cross any regional boundary. The only way to deal with them
is to make a note outside the grid. My convention is to mark
the unresolved cells in a line (row or column) as a string of
digits within parenthesis eg (1234567) but to highlight a pair
or triple by using multiple parenthesis eg (36)(12457) for
a pair (either M/Reception or remote) or (247)(1356) in
the case of triple. These notes are not available using the
on-line version but the large print on A4 is perfect - using the
space above the grid and to its right.
Back to top
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1029
Location: Vienna, Austria

PostPosted: Mon Dec 10, 2007 7:31 am    Post subject: Reply with quote

very interesting method.

Right at the begining, when looking for singles, I routinely mark-up the puzzle for this sort of mandatory placement by writing the candidate either on the line between two cells, or to the left/right of a row, or above/below a column. It looks sort of like bets placed in roulette when you bet on two or three squares.

To get an idea how (messy) this looks like, this is a picture I included in the "Nov 26 vh" thread:



My markup method breaks down when the center box is involved and cannot handle "knights move" patterns, so this MP method is definitely an improvement I shall try.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
alanr555



Joined: 01 Aug 2005
Posts: 194
Location: Bideford Devon EX39

PostPosted: Mon Dec 10, 2007 11:55 am    Post subject: Reply with quote

A couple of techniques with M/Pairs:

A) Consider a block of three regions forming a large column
(three cells wide) or a large row (three deep). Here a
column is considered to simplify explanation but the
same principles apply to rows.

If a digit appears in the M/Pair marks in the same two columns
in two of the regions, its position in the third region MUST be in
the third column.

Example:
Pair of 7s in r3c4 and r1c6
Another pair in r9c4 and r7c6
These pairs occupy only cols 4 and 6 out of the large column 456
and only regions TWO and EIGHT.
Thus in region FIVE digit 7 MUST be in column 5.

If the "third" column in the "third" region already has a cell
completed (other than the digit being considered!) there is
another mandatory pair identified (and a resolution if two
of the three cells are already occupied by a single digit or
a mutual reception component). Sadly, in the majority of
cases the considered digit is already present - but it is
always worth checking!

This technique does, of course, have a parallel in the pattern
spotting process using pencil mark profiles. However, using
M/Pairs leads to the result much more easily - having reduced
the obfuscation of most other digits.

B) When a region has all nine digits either resolved or constrained to
two cells it may be termed "definitionally complete". It will be
clear that each unresolved cell has an AVERAGE of two digits
in its mandatory pair string.

If every unresolved cell has a M/P string with two elements,
there is an implicit binary chain. As soon as one of the cells
is resolved, they all are - great joy!

Sometimes a cell arises which has THREE entries for M/Pairs.
This should arouse some interest because the presence of
three in one cell implies only ONE in another cell (and hence
a resolution!).

With a definitionally complete region, the resolution is obvious
but sometimes the scenario is helpful even when there is not
yet a complete definition.

Example:
Cells r4c7, r4c8, r5c9, r6c8 are resolved with 6,8,1,9
Mandatory pairs exist for 2,3,5,7
Thus only 4 is missing but it can be in any one of
r5c7, r5c8, r6c7 - having an entry in col 9 in another region.
The pairs are
2 in r5c8, r6c9
3 in r5c7, r6c7
5 in r4c9, r6c9
7 in r6c7, r6c9

Inspection reveals that r6c9 has THREE elements marked (257)
and that singles exist in r5c7, r5c8, r4c9

Because the missing value (4) CANNOT be in col 9, the value
in r4c9 will remain a single even if the definition is completed.
Thus digit 5 must be in r4c9. This can be confirmed by simple
inspection of the row/column/region intersecting that cell but
the benefit of M/Pairs is that it draws attention very directly to
what might take quite some time by other pattern scanning
methods (sole candidate).

+++

After a while using M/Pairs these techniques become well entrenched
in one's armoury.

One psychological danger is failing to switch mindsets when switching
between M/Pairs and pencil-mark scanning. M/Pairs contains only
POSITIVE information and the absence of a digit from the M/P marks
in a cell does NOT mean that the digit cannot rest there or that only
the marked digits are possible. It is quite possible for a cell to hold
two or three M/Pair digits during the solution process and for the
final digit to be a quite different one. Half of the M/Pair marks will
turn out to be in cells which do not take that value! However, the
good news is that half WILL be correct and that finding out the
"wrong-ness" of the other 50% confirms the ones that are correct.

Of course, making the marks is only part of the process. The benefit
comes from spotting the patterns - but I would contend that the
pattern spotting is easier with M/Pairs than it is with full profiles as
the number of elements is usually less and the number of cells
with patterns to be checked is usually less.

Whilst M/Pairs techniques will solve a lot of puzzles (using human logic
rather than computer scanning logic) it must be admitted that the
more complex puzzles will need resort to the full profiles - but by using
M/Pairs first one may avoid such resort and if one does need to go
that way the onward journey to solution will be easier from having
used M/Pairs as a preliminary process (at least for those human
beings like me whose minds are not 'wired' like a computer!).
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group